Problem solving as search
Uninformed search
I/ Breath-first search
II/ Depth-first search
Depth-first search is not optimal and incomplete.
"Incomplete" means it can start down an infinite path and never return to try other possibilities.
Informed search
I/Best-first search approach
1. Greedy best-first search
"Greedy" means at each step it tries to get as close to the goal node as it can.
2. A* search
A* search tries to minimize the total estimated solution cost.
f(n)=g(n) + h(n)
h(n) represents the heuristic cost from the considering node to the goal.
g(n) represents the cost from the current node to the considering node.
A* search is both complete and optimal.
A* search is optimal if h(n) is an admissible heuristic. That means h(n) never overestimates the cost to reach the goal.
A* tends to run out of space faster than out of time as it keeps all the previous generated nodes.
Reference
Stuart Russel and Peter Norvig "Artificial intelligence: a modern approach", 2nd Ed, 2003.
