Problem solving as search

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.