Problem Solving by Searching Notes

Main Components of a Search Solution

A problem graph: Contains the start node (S) and the goal node (G).
A tree: Results from traversing the graph towards the goal.
A strategy: Describes how the graph will be traversed to reach G.
A fringe: A data structure storing possible states (nodes) to explore from the current state.
A solution plan/path: The sequence of nodes from S to G.
Cost of the solution: The total path cost.

Visiting and Expanding Nodes/States

Visiting a node (state): Selecting a node to examine.
Expanding (Exploring) a node (state): Exploring the adjacent (child) nodes of the selected node.

Searching for Paths

Searching for a path involves finding a route from one vertex to another.
Objectives:
- Find any path.
- Minimize path length (number of edges).
- Minimize path cost (sum of edge weights).
Example questions:
- What is the shortest path from MIA to SFO?
- Which path has the minimum cost?

Search Strategies

Uninformed search (Blind search strategies):
- No information about which non-goal state is better.
- Blind search.
- Only know if a state is a goal state or not.
- Examples: Breadth-First Search, Depth-First Search, Uniform Cost Search.
Informed search (Heuristic search strategies):
- Uses information about the problem to guide the search.
- Expands nodes that seem closer to the goal first.
- Examples: A* search, Best First Search (Greedy Algorithm).

Uninformed Search Strategies

Various blind strategies:
- Breadth-first search
- Depth-first search
- Uniform-cost search

Breadth-First Search (BFS)

Expands the shallowest unexpanded node.
Fringe: Nodes waiting in a queue to be explored.
Implementation:
- Fringe is a First-In-First-Out (FIFO) queue; new successors go at the end of the queue.

Depth-First Search (DFS)

Expands the deepest unexpanded node.
Implementation:
- Fringe = Last In First Out (LIFO) Stack, i.e., put successors at front

Comparing DFS and BFS

Feature	Breadth-First Search (BFS)	Depth-First Search (DFS)
Traversal Strategy	Explores all neighbors level by level	Explores as far as possible along each branch
Data Structure	Queue (FIFO)	Stack (LIFO) or recursion
Time Complexity	$O(V + E)$
$O(V + E)$
Space Complexity	$O(V)$ (due to queue)	$O(V)$ (due to stack/recursion)
Completeness	Complete (guarantees solution if exists)	Not always complete (may get stuck in infinite path)
Optimality	Optimal (finds shortest path in unweighted graphs)	Not optimal (may find longer paths)
Suitable For	Shortest path, level-order traversal, peer-to-peer	Topological sort, solving puzzles, cycle detection
Traversal Order	A → B → C → D → E (level-order)	A → B → D → E → C (deep-first)
Handling Infinite Graphs	Needs mechanism to avoid revisiting nodes	Prone to getting stuck unless visited nodes are tracked
Implementation	Iterative (using queue)	Recursive or iterative (using stack)

Cost-Sensitive Search

BFS finds the shortest path in terms of the number of actions but not necessarily the least-cost path.

Uniform Cost Search (UCS)

Finds the least-cost path from a start node to a goal node in a weighted graph.
Guarantees optimal solution if step costs are non-negative.
Explores nodes with the lowest cumulative cost to find the path from the source node to the goal node with Breadth-First Search.
Nodes are expanded, starting from the root, according to the minimum cumulative cost.
Implemented using a Priority Queue.

UCS Algorithm Steps

Insert the root node into the priority queue.
Remove the element with the highest priority.
If the removed node is the goal node:
- Print total cost and stop the algorithm.
Else:
- Enqueue all the children of the current node to the priority queue, with their cumulative cost from the root as priority, and add the current node to the visited list.

Informed Search Strategies

Use domain-specific knowledge to find solutions more efficiently than uninformed methods.
$g(n)$ : The cost of the path from the start node to node n.
$h(n)$ : Heuristic function that estimates the cost of the cheapest path from n to the goal.

Best First Search (Greedy Search)

Expands the node that is closest to the goal, based on the heuristic function.
Evaluates nodes using the heuristic function: $f(n) = h(n)$
$h(n)$ : Estimated cost from the state at node n to a goal state.

A* Search

Combines features of Uniform Cost Search with Best First Search.
Sorts the queue by estimated total cost of the completion of a path: $f(n) = g(n) + h(n)$
- $g(n)$ : Cost so far to reach n.
- $h(n)$ : Estimated cost from n to the goal (heuristic).
- $f(n)$ : Estimated total cost of the path through n to the goal.

Evaluation of Search Strategies

Search algorithms are commonly evaluated according to the following four criteria:
- Completeness: Does it always find a solution if one exists?
- Time complexity: How long does it take as a function of the number of nodes?
- Space complexity: How much memory is needed to perform the search?
- Optimality: Does it guarantee the least-cost solution?

Measuring Performance of a Search Algorithm

Time and space complexity are measured in terms of:
- b - max branching factor of the search tree
- d - depth of the least cost solution
- m - max depth of the state space (may be infinity)

Performance of Search Algorithms

Criterion	Breadth-First	Depth-First	Uniform-Cost	Iterative Deepening	Best First	A*
Complete?	Yes a	No	Yes a, b	Yes a	No	Yes
Time	$O(b^d)$	$O(b^m)$	$O(b^{1+[C*]})$	$O(b^d)$	$O(b^m)$	$O(b^m)$
Space	$O(b^d)$	$O(b*m)$	$O(b^{1+[C*]})$	$O(b*d)$	$O(b^m)$	$O(b^m)$
Optimal?	Yes c	No	Yes c	Yes c	No	Yes e

a complete if b is finite
b complete if step costs > ∈ for positive ∈
c optimal if step costs are all identical
e if the heuristic is admissible, A* with a good heuristic can find optimal solutions for many problems in reasonable time

Problem Solving by Searching Notes

Main Components of a Search Solution

Visiting and Expanding Nodes/States

Searching for Paths

Search Strategies

Uninformed Search Strategies

Breadth-First Search (BFS)

Depth-First Search (DFS)

Comparing DFS and BFS

Cost-Sensitive Search

Uniform Cost Search (UCS)

UCS Algorithm Steps

Informed Search Strategies

Best First Search (Greedy Search)

A* Search

Evaluation of Search Strategies

Measuring Performance of a Search Algorithm

Performance of Search Algorithms