Uniform cost search
From Mathematics
Uniform cost search is a tree search algorithm related to breadth-first search. Whereas breadth-first search determines a path to the goal state that has the least number of edges, uniform cost search determines a path to the goal state that has the lowest weight.
[edit] Algorithm
Let 
be a tree with weighted edges and let 
be the weight of path 
in 
. For convenience, let 
be the root of the tree and 
denote the end vertex of a path in . [1]. With that said, let 
, the set of known paths starting with , be 
. It should be noted that the weight of 
is zero.
- If there exists in such that minimizes and is a goal state of , i.e., a leaf, stop. is the path of minimal cost to the goal.
- Otherwise, identify in where minimizes and expand . In other words, add to all paths formed by adding one of the child vertices of (if any) to . Remove from ; it is considered 'visited', and failure to remove it may result in non-termination of the search.
- Repeat first step.
[edit] Additional Details
It's worth observing that uniform cost search assumes that no edges have negative weight. If any edges have negative weight, then it is possible that a path begins with a vertex whose edge to its parent has a high positive weight, which will exclude it from consideration by the search. This action might be faulty, though, because the total weight of might be minimal overall, due to negative weights further on in the path. When there are negative weights in the search tree, more expensive algorithms such as the Floyd-Warshall algorithm must be used.
[edit] Notes
- ↑ This mapping might have been named
, but the author could not pass up the opportunity to use something that sounds like 'T.P.'.
