Uninformed Search Strategies (Russell Norvig)
As outlined in Russell Norvig Chapter 03: Solving Problems by Searching
Definition
An uninformed search algorithm is given no clue about how close a state is to the goal(s). (p. 94)
Summary and Comparison
RN make the following general observation (p. 95):
In general,exponential-complexity search problems cannot be solved by uninformed search for any but the smallest instances.
They present several uninformed search algorithms:
And compare them against the criteria presented in Search Algorithms (Russell Norvig).
The comparisons are for tree-like searches that don’t check for repeated states, for graph searches which do check, the main difference is that depth-first search is complete for finite state spaces, and the space and time complexities are bound by the size of the state space (\(|V| + |E|\)).
In the following table:
b is the branching factor.
m is the maximum depth of the search tree.
d is the depth of the shallowest solution (which is m if no solution).
l is the depth limit.
\(C^*\) is the cost of the optimal solution (\(C^*\) is used throughout the book, the star meaning ‘optimal’, ie the optimal value for C)
\(\epsilon\) is a lower bound on the cost of each action, with \(\epsilon > 0\).
| Complete? | Optimal cost? | Time | Space | |
|---|---|---|---|---|
| Breadth-first | Yes | Yes | \(O(b^d)\) | \(O(b^d)\) |
| Uniform-cost | Yes | Yes | \(O(b^{1+ \left \lfloor{C^* / \epsilon}\right \rfloor})\) | \(O(b^{1+ \left \lfloor{C^* / \epsilon}\right \rfloor})\) |
| Depth-first | No | No | \(O(b^m)\) | \(O(bm)\) |
| Depth-limited | No | No | \(O(b^l)\) | \(O(bl)\) |
| Iterative-deepening | Yes | Yes | \(O(b^d)\) | \(O(bd)\) |
| Bidirectional | Yes | Yes | \(O(b^{d/2})\) | \(O(b^{d/2})\) |
The following caveats are added:
All ‘complete’ searches are complete only if b is finite, adn the state space has a solution or is finite.
Uniform-cost search is complete only if all action costs are \(\geq \epsilon > 0\).
BFS, Iterative deepening, and bidirectional searches are optimal cost only if action costs are all identical.
Bidirectional search is complete and optimal cost if both directions are breadth-first or uniform-cost.