Finding an optimal solution, uniform-cost search

It should be noted that for some problems we are not interested in finding any  solution, but rather the optimal  or best  one. What 'best' means depends on the problem at hand, but for now we will call a solution path optimal if it contains the least possible number of nodes leading to the goal node. Later on we will refine our definition to include a different, but related type of problems. In the case of a depth-first search we cannot guarantee that the best solution will be found. This is because every branch is examined seperately, so if the search process finds a goal node in one branch it will terminate. But it may well be that a better solution is located in a different branch. Breadth-first search on the other hand is guaranteed to find the shortest path, because it expands all nodes on one level before advancing to the next.

For some problems, however, finding the best solution does not mean finding the shortest path, but rather the cheapest  path. This is true for instance when we need to find the shortest path from one city to another. In this case there may be several routes that can be used to get from city A to city B, visiting other cities along the way. Now suppose the cities are nodes in a search tree, clearly what we want is not the smallest number of nodes (cities) that make up a path from A to B, but the shortest route. To solve problems like this one we need to associate costs  with the arcs in the tree (in this case the costs will represent the distances between the cities). The object is to find a path having the least cost.

A more general version of the breadth-first method, called the uniform-cost search method  is guaranteed to find a path of minimal cost from the start node to a goal node. Instead of expanding paths of equal length like the breadth-first method, this method expands paths of equal cost. To compute the cost of a path to a node we will use the function g(n) . The cost associated with a node will consist of the cost associated with its parent plus the cost of getting from the parent to this node. Using this method to order the set of nodes we are sure the uniform-cost method expands nodes in order of increasing g(n).

One should note that the graph search technique that we described earlier must be modified when we are looking for an optimal solution. We said that during a graph search every node that is generated twice can simply be thrown away. If we would use this technique in a uniform-cost search we could never guarantee to find the cheapest path. As said, in a graph there may be multiple paths leading to the same node. But each of these has its own (possibly different) cost. So if we throw away a node without paying attention to this fact we may be missing a better solution without ever noticing. Therefore, the graph search procedure must be modified in the following way: every time a new node is generated we check whether it already exists in the graph. If not, we add it. If it does, we compare the cost of the old node and the cost of the newly generated node. If the old node is better (cheaper) nothing has to be done, if it is worse we change its cost and direct its pointer to the parent on the least costly path that has just been found.