Searching algorithm is one of main areas of artificial intelligence. I introduce some basic algorithms and ideas to evaluate them.
Four properties to compare searching algorithms
Complete
Whether it always finds a solution if one exists.
i.e.
- BFS
- Uniform-cost search (if cost is positive)
are 'complete' searching algorithms because they can check every node in a map.
Time Complexity
Number of nodes generated or expanded.
Space
Maximum number of nodes in memory.
Optimality
Whether it always finds least-cost solution
Measures
Time and space complexity are measured in terms of
- maximum branching factor of the search tree (mentioned by
b) - depth of the least-cost solution (
d) - maximum depth of the state space (
m)
Searching Algorithms
- Breadth-first search
- Uniform-cost search
- Depth-first search
- Depth-limited search
- Iterative deepening search
Breadth-first search (BFS)
Complete?
Yes (if b is finite)
Time?
1 + b + b^2 + b^3 + ... + b(b^d-1)= O(b^{d+1})
Sum up to power of d+1 not d because you can detect finishing state when the node get enqueued from the queue. That means that you have to check upto nodes located at next level of the least cost node.
Space?
O(b^{d+1})
Keep every nodes in the fringe in a queue. Worst case is the most expanded deepest level, which has b^(d+1) nodes on it.
=> Space is the big problem about BFS. It can easily generate nodes at 100MB/sec so 24 hours = 8460GB for example.
Optimal?
Yes if cost is constanct per step, like cost = 1 per step.
But not optimal in general.
Uniform-cost search
Expand least-cost unexpanded node.
Implementation
fringe = queue ordered by path cost, lowest first.
If step costs all equal, it's equibalent to bfs.
Complete?
Yes
Time?
If C is destination cost and each step gets ε closer to the goal, the number of steps you need to take is given by C/ε+1. The reason for the +1 is that you start at distance 0 and end at C/ε, so you take steps at distances
0, ε, 2ε, 3ε, ..., (C/ε)ε
And there are 1+C/ε total steps here. Therefore, there are 1+C/ε layers, and so the toal number of states you need to expand is $O(b^{1+C/ε})$.
Space?
same logic as above $O(b^{1+C/ε})$
so depends on number of nodes with less cost than targetted solution's cost.
Optimal?
Yes, because nodes expand in increasing order of g(n) where g(n) is cost taken upto node n.
Depth-first search (DFS)
Complete?
No, it may falil in infinite-depth spaces with loops. Need to modify to avoid repeated states along path so that it becomes finite space.
Time?
$O(b^m)$. It will be terrible if m is larger than d. But if solutions are dense(m is small), may be much faster than breadth-first.
Space?
$O(bm)$. its liniear space.
=> This is better than bfs.
Optimal?
No.
Iterative deepening search
Iterate depth-limited search from root until it finds the solution.
Complete?
Yes
Time?
$O(b^d)$
Space
$O(bd)$
Optimal?
Yes, if step cost = 1 (constant). Can be modified to explore uniform-cost tree.
IDS does better because other nodes at depth d are not expanded.
BFS can be modified to apply goal test when a node is generated. (instead of when node is enqueued.)
=> it takes benefits from both of bfs and dfs. Like bfs, it is optimal, and like dfs, it have space complexity of linear.
Imformed search algorithms
Greedy Search
Evalation function h(n) (h from heuristic)
=> estimate of cost from n to the closest goal.
Greedy search expands the node that appears to be closest to goal.
Complete?
No, can get stuck in loops
Time?
$O(b^m)$, but good heuristic can give dramatic improvement.
Space?
$O(b^m)$, keeps all nodes in memory
Optimal?
No.
=> Greedy algorithm considers only heuristic distance from current node to goal, not thinking about how much cost it has taken to current node.
=> So A* search is here.
A* search
Idea: Avoid expanding paths that are already expensive.
Evaluation function f(n) = g(n) + h(n)
g(n) = cost so far to reach n
h(n) = estimated cost to goal from n
f(n) = estimated total cost of path through n to goal
A* search uses an admissible heuristic
i.e., h(n) <= h*(n) where h*(n) is the true cost from n. Also require h(n) >= 0, so h(G) = 0 for any goal G.
Theorem: A* search is optimal.
Dominate
If there is two heuristic values h1 and h2 (both admissible) and h2(n) >= h1(n) for all, then h2 dominates h1 and is better for search.
Planning to solve problems by implementing every algorithm above for each.