Differences

This shows you the differences between two versions of the page.

--- public:t-622-arti-13-1:lab_2_-_formulating_search_problems [2013/01/31 10:17] – [Tasks] stephan
+++ public:t-622-arti-13-1:lab_2_-_formulating_search_problems [2024/04/29 13:33] (current) – external edit 127.0.0.1
@@ Line 16: / Line 16: @@
 **All of this can be done on paper (or in a text file). You don't actually have to program it! Just write down pseudo-code.**
-. Estimate the memory requirement for you state data structure (in bytes relative to //c// and //r//). What does that mean for breadth-first search, depth-first search and iterative deepening search? What is the largest board (//c// x //r//) that you could solve using each of the two algorithms assuming you have 2GB of memory available.
+. Estimate the memory requirement for you state data structure (in bytes relative to //c// and //r//). Suppose you want to solve the game by searching the state space. How does the size of your data structure influence the applicability of breadth-first search, depth-first search and iterative deepening search? What is the largest board (//c// x //r//) that you could solve using each of the three algorithms assuming you have 2GB of memory available? For the sake of simplicity, you can assume a square board, i.e. //c//=//r//.
-. For each of functions above, determine its (worst-case) time complexity in terms of //c// and //r//.
+. For each of functions above (legal moves, successor state, ...), determine its (worst-case) time complexity in terms of //c// and //r//.