Blind search vs heuristic search, best-first search

All of the methods described so far are called blind-search procedures  because they do not use any specific information about the problem to be solved, i.e, the search process just continues until it happens on a solution: it is not directed in some way to the goal. The advantage of blind-search procedures is that they are easy to implement and may find a solution quickly for small problems. The obvious disadvantage of these methods is that they may be led astray, expanding a lot of nodes that are not part of the solution path. For example, when traversing a tree in depth-first order we dive into the left most branch, this is fine if we happen to find a solution there. But suppose the goal node is located in a different part of the tree, e.g., at the right most branch. In this case we will have searched the entire tree before getting on the right track. It would have been much better if we had known in advance which way to go. But of course, this is impossible; if we had known this we would never have to search  for a solution. Still, there may be situations where we do not know exactly where to go, but can give an estimate of how far a node is removed from the goal node and hence determine if it is on the (best) solution path. Using this information it is possible to improve the efficiency of the search process. Here, we have introduced the idea of using a heuristic .

A heuristic is a rule of thumb, a technique that improves the efficiency of a search process, possibly by sacrificing claims to completeness [Rich 1983, 35]. This means that, like all rules of thumb, heuristics may lead the search in the most promising way, finding a solution quickly, but also that they may take a wrong turn (but still leading to the goal) or lead to deadends. A good way to use heuristic information is by means of a heuristic function  that evaluates every node that is being generated, i.e. that determines the goodness or badness of a node. Using a heuristic function it will be possible to conduct the search in the most profitable direction, by suggesting which path to follow first when more than one is available.

We will define a heuristic function f(n)  being the sum of two components g(n)  and h(n) :

f (n) = g(n) + h(n)

Function g(n) is the same as the one described in section [*]: a measure of the cost of getting from the initial state to the current node. The function h(n) is an estimate of the additional cost of getting from the current node to a goal state. Put differently, h(n) is the function in which the real heuristic knowledge is imbedded. Using f(n) we are able to order the set of nodes waiting for expansion, by convention this will be done this in increasing  order. An algorithm can then be used to select the node having the smallest f(n) value next for expansion. One of the methods that uses this technique is the best-first search method  or A* algorithm .

It is important to keep in mind that most heuristics are imperfect and that, inevitably, the search process will be affected by this. In general, a search algorithm is called admissible  if for any graph it terminates in an optimal path to a goal whenever a path exists. Using a heuristic function to conduct the search process we cannot always make this claim because the behaviour of the search will depend on how accurately the function evaluates nodes. If we use a perfect heuristic function we are guaranteed to find an optimal solution, but heuristics having this property are hard to find. Furthermore, the difficulty of computing the function's result affects the total computational effort of the search process. Also, it may be less important to find a solution whose cost is absolutely minimal than to find a solution of reasonable cost within a reasonable amount of time. In this case one may prefer a heuristic function that evaluates nodes more accurately in most cases, but sometimes overestimates the distance to the goal, thus resulting in an inadmissible algorithm. Most of the time we need to make this sort of compromise: the efficiency of the search process needs to be improved at the sacrifice of admissibility (see Barr(1981), p.65/66, Nilsson(1971), p.59ff.)