Busca de cost uniforme

En ciència de la computació, la busca de cost uniforme (BCU) és un algoritme de busca no informada utilisat per a recórrer sobre grafos el camí de cost mínim entre un nodo raïl i un nodo destine. La busca comença pel nodo raïl i continua visitant el següent nodo que té menor cost total des de la raïl. Els nodos són visitats d'esta manera fins que el nodo destine és alcançat.

Típicament, l'algoritme implica l'expansió de nodos per mig de l'adició, a una coa en prioritat, de tots els nodos veïns no expandits que estan conectats a l'últim nodo analisat. En la coa, cada nodo s'associa en el seu cost total des de la raïl, a on se'ls dona major prioritat als camins de cost mínim. El nodo en el cap de la coa és expandit, adicionando els seus nodos veïns en el cost total des de la raïl fins al nodo respectiu. La busca de cost uniforme és completa i òptima si el cost de cada pas excedix algun llímit eps positiu. El temps per al cas pijor i la complexitat espacial és O(b^{1 + C*/ε}), a on C* és el cost de la solució òptima i b és el factor de ramificació. Quan tots els costs entre els nodos són iguals, açò es convertix en O(b^{d + 1}).

Relació en atres algoritmes

l'algoritme de Dijkstra, que és potser més conegut, pot considerar-se com una variant de Busca de Cost Uniforme, a on no hi ha un estat meta (goal) i el processament continua fins que tots els nodos han segut eliminats de la coa en prioritat, és dir, fins que els camins més curts a tots els nodos (no només un nodo objectiu) s'han determinat. De la mateixa manera que en l'algoritme de Dijkstra, BCU garantisa que (si tots els pesos de les arestes són no negatius) el camí més curt a un nodo particular, s'ha trobat una volta que el nodo s'extrau de la coa en prioritat.

La Busca de Cost Uniforme és un cas particular del algoritme de busca A* si la heurística d'este últim és una funció constant (per tant ya no seria una busca informada sino cega). Si A* s'utilisa en una heurística monòtona, llavors es pot convertir en una Busca de Cost Uniforme restant de cada cost d'aresta a la disminució en el valor heurístic a lo llarc d'eixa aresta. Busca Primer a lo Ample (BPA o BFS en anglés) és un cas especial de BCU quan els costs de les arestes són positius i idèntics. BPA visita primer el nodo en la llongitut del camí més curt (número de nodos) des del nodo raïl, en canvi, UCS primer visita el nodo en la ruta més curta en cost (sumixca dels pesos de les arestes) des del nodo raïl.

Busca de Cost Uniforme és una variant de l'algoritme Busca Primer el Millor.

Pseudocode de Busca de Cost Uniforme

procedure UniformCostSearch(Graph, root, goal)
  node := root, cost = 0
  frontier := priority queue containing node only
  explored := empty set
  do
    if frontier is empty
      return failure
    node := frontier.pop()
    if node is goal
      return solution
    explored.add(node)
    for each of node's neighbors n
      if n is not in
        frontier if n is not in
          explored frontier.add(n)
        else if n is in explored with higher cost
          replace existing node with n

Procés d'expansió mostrant el conjunt "explored" i la coa en prioritat "frontier":
root: A
goal: G

Pas	“frontier” (nodos i els seus costs)	Ampliar*	“explored”: conjunt de nodos
1	{(A,0)}	A	∅
2	{(D,3),(B,5)}	D	{A}
3	{(B,5),(I,5),(F,5)}	B	{A,D}
4	{(I,5),(F,5),(C,6)}	I	{A,D,B}
5	{(F,5),(C,6)}**	F	{A,D,B,I}
6	{(C,6),(G,8)}	C	{A,D,B,I,F}
7	{(G,8)}	G	{A,D,B,I,F,C}
8	∅

* nodo a expandir en el pròxim pas.
* B no s'afig a la frontera (frontier) perque es troba en el conjunt explorat (explored).
Camí trobat: A-D-F-G.