Blind Search Algorithms: DFS

Uninformed Search

• Uninformed search algorithms do not use problem domain knowledge.
• Algorithms have no additional information about the states.
• These algorithms generate successors and can distinguish a goal state from a non-goal state.

Blind Search Algorithms

• Principal blind search algorithms: Depth First Search (DFS) and Breadth First Search (BFS).
• Common properties include searching along the most promising path with the aim to find some solution to a problem.

Depth First Search (DFS)

• Depth First Search attempts to plunge as deeply into a tree as quickly as possible.
• If a choice exists, the leftmost branch gets selected.

Implementing Blind Search Algorithms

• Two lists are maintained: "Open" and "Closed".
• Open List contains all nodes still being explored or expanded.
• Closed List contains nodes that have already been explored.

Pseudocode for DFS

• Begin with the start state in the "Open" list, which is maintained as a stack.
• While the "Open" list is not empty, remove the first item, calling it "X".
• If "X" is the goal, return success.
• Otherwise, generate immediate descendants of "X", put "X" on the "Closed" list, and place children not yet encountered in "Open".
• Return "Goal not Found" if goal is not found.

Breadth First Search (BFS)

• BFS visits nodes level by level from the top of the tree to the bottom, going from left to right.

Pseudocode for BFS

• Begin with the start state in the "Open" list, which is maintained as a queue.
• While the "Open" list is not empty, remove the first item, calling it X.
• If X is the goal, return success.
• Otherwise, generate immediate descendants of X, put X on the Closed List, and place children not yet encountered in Open.
• Return Goal not Found if goal is not found.

Missionaries and Cannibals Problems

• Involves 3 missionaries, 3 cannibals, and 1 boat that can accommodate 1 or 2 people.
• Cannibals should never outnumber missionaries on either side of the river or on the boat.

Measuring Problem-Solving Performance

• Metrics include completeness, optimality, time complexity, and space complexity.

Completeness

• Guarantees finding a solution if one exists.

Optimality

• Provides the lowest cost path among all solutions.

Time Complexity

• Measures how long it takes to find a solution.
• Measures number of nodes generated or expanded during the search.

Space Complexity

• Measures the memory required to perform the search.
• Measures maximum number of nodes stored in memory.

Complexity

• Expressed in three parameters: branching factor, depth and maximum length.
• Branching Factor (b) of a node - Number of branches emanating from it.
• Depth (d) of the shallowest goal node.
• Maximum length of any path (m) in the state space.

DFS vs. BFS

• DFS is preferred when the tree is deep, the branching factor is not excessive, and solutions occur relatively deep in the tree.
• BFS is preferred when the branching factor is not excessive (reasonable b), the solution occurs at a reasonable level in the tree (reasonable d), and no path is excessively deep.

DFS

• Search gets lost in a long path, therefore the search is incomplete.
• Search Path length is 8, PathLength (BFS) is 4, therefore DFS is not optimal.
• Time and Space Complexity: bm + 1 nodes, O(bm) complexity

BFS

• Completeness determined if b is finite.
• Optimality determined if path cost is non-increasing function of the depth of the node.
• BFS first searches b children of the root, then b² grandchildren..... bd nodes at level d.
• Finds shallowest goal node quickly.
• Time Complexity: T(n) = b + b2 + b3 + ..... (bd-1 - b) = O(bd+1)
• Space Complexity: S(n) = T(n) + 1 =O(bd+1)

Other Blind Search Algorithms

• Depth Limited Search: Variation of DFS where nodes at depth L are treated as if they have no successors. Solves the infinite-path problem.

DFS with Iterative Deepening (DFS-ID)

• Depth First Search with Iterative Deepening combines modest space requirements of DFS and does not pursue lengthy paths.
• Searches continues with depth bound increasing by one in each iteration
• Time Complexity O(bd)
• Space Complexity O(bd)
• Completeness determined if b is finite
• Optimality if paths are non-decreasing function of a node's depth

Bidirectional Search

• Search searches forward from the initial state and backwards from goal state simultaneously.
• Keeps track of 2 frontiers and 2 tables of reached states.
• Requires backward reasoning.
• When 2 frontiers collide, a solution occurs.

Bidirectional Best-First Search Algorithm

• Uses two frontiers: forward and backward.
• The node to be expanded has a minimum evaluation function value across either frontier.