What is Heuristic Search?

Classic search algorithms such as breadth-first search, depth-first search and uniform-cost search search only based on information that has already been provided by the problem. Those algorithms will traverse the whole search tree until they hit a solution, or else exhaust the graph. These are also called uninformed search algorithms or blind search algorithms. Uninformed search algorithms work well on small search graphs, but become unreliable or even intractable when the problem is more complex.

For these sorts of problems, we use heuristic search (informed search). Unlike classic search algorithms, heuristic search algorithms can use the knowledge beyond the problem definition itself to try paths by order of ‘promise,’ so to find solutions efficiently. To get this extra information, heuristic search algorithms use a heuristic function h(n). Heuristic search algorithms also employ an evaluation function to help decide which nodes to explore first.

We will introduce two heuristic search algorithms: Greedy best-first search and A-search. Greedy best-first search is a basic informed search algorithm that always expands the node that appears to be closest to goal. A-search is one of the most famous informed search algorithm that combines the greedy best-first search with the uniform-cost search.