**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**).