# Uniform cost search

667pages on
this wiki

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.

## AlgorithmEdit

Let $T = (V,E)$ be a tree with weighted edges and let $w(p)$ be the weight of path $p$ in $T$. For convenience, let $r$ be the root of the tree and $t(p)$ denote the end vertex of a path $p$ in $T$. [1]. With that said, let $K$, the set of known paths starting with $r$, be $\{(r)\}$. It should be noted that the weight of $(r)$ is zero.

1. If there exists $p$ in $K$ such that $p$ minimizes $w(p)$ and $t(p)$ is a goal state of $T$, i.e., a leaf, stop. $p$ is the path of minimal cost to the goal.
2. Otherwise, identify $p$ in $K$ where $p$ minimizes $w(p)$ and expand $t(p)$. In other words, add to $K$ all paths formed by adding one of the child vertices of $t(p)$ (if any) to $p$. Remove $p$ from $K$; it is considered 'visited', and failure to remove it may result in non-termination of the search.
3. Repeat first step.

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 $p$ 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 $p$ 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.
1. This mapping might have been named $e(p)$, but the author could not pass up the opportunity to use something that sounds like 'T.P.'.