Search Algorithm: Based on Tree

Backtracking Algorithm

Assume that b is the number of possible actions per state and D is the maximum depth of tree.

Time: O(b^D)
Memory: O(D)

Depth-first Search (DFS)

Time: O(b^D) in the worst case
Memory: O(D)

• backtracking algorithm + stop the algorithm when find the first end state
• Assume Cost(s,a) = 0 (All edge points are 0)

Breadth-first Search (BFS)

Assume that solution has d actions
Time: O(b^d)
Memory: O(b^d)

• Assume Cost(s,a) = c (c >= 0)
• explore all nodes in order of increasing depth

DFS with Iterative Deepening (DFS-ID)

Time: O(b^d)
Memory: O(d)

• Assume Cost(s,a) = c (c >= 0)
• Modify DFS to stop at a max depth

Summary