ALGORITHMS - BEST - FIRST

Best first search is an intelligent search algorithm which makes use of a heuristic to rank the nodes based on the estimated cost from that node to the goal. First, the initial node is placed in an open list, then it is checked for goal conditions. If it is not a goal state, it is removed from the open list (making the open list momentarily empty), and its child nodes are put in the open list. The heuristic is applied to these child nodes, and the node that is estimated to be the best is then taken out of the open list and evaluated. If it is not a goal, the node is placed in the closed list, its children are put in the open list, and the heuristic is used to select the node in the open list that now appears to be the best in the list. This continues until a goal is found or the open list is empty.

A simple case of the best first search is the greedy best first search, where the heuristic simply chooses the node that appears to be closest to the goal node from the current node. This will provide the best solution sometimes, but may cause problems in others-for instance, when plotting a trip on a map, two points may seem very close together when only distance is taken into account, but actually traveling between them may require additional time or may even be impossible. This heuristic is called greedy because, in a sense, it greedily grabs at the best solution without attempting to calculate the long term costs. Its salient characteristic is that in its attempt to get to the goal, it starts from the current node, not the start node, to choose a path towards the goal.

UNIFORM COST SEARCH

While breadth first search guarantees to find the solution with the least number of steps, this property becomes less useful for scenarios where all steps are not equal (on a map, for instance, traveling from San Francisco to San Jose and traveling from San Francisco to Chicago may both be a 'step', but certainly do not have the same cost--in miles, or dollars!). In this case, a uniform cost search is used instead. Uniform cost searches always expand the node with the lowest total path cost from the initial node. Thus, they are always optimal (since any cheaper solution would already have been found.) Their salient characteristic is the fact that they start from the initial start node when they calculate the path cost in the search.

Fig.1 (picture from http://www.cs.sunysb.edu/~skiena/combinatorica/animations/anim/dijkstra.gif)

An example of an implementation of a uniform cost search is Djikstra's Algorithm (Fig. 1).