Búsqueda de costo uniforme
En ciencia de la computación, la búsqueda de costo uniforme (BCU) es un algoritmo de búsqueda no informada utilizado para recorrer sobre grafos el camino de costo mínimo entre un nodo raíz y un nodo destino. La búsqueda comienza por el nodo raíz y continúa visitando el siguiente nodo que tiene menor costo total desde la raíz. Los nodos son visitados de esta manera hasta que el nodo destino es alcanzado.
Típicamente, el algoritmo implica la expansión de nodos mediante la adición, a una cola con prioridad, de todos los nodos vecinos no expandidos que están conectados al último nodo analizado. En la cola, cada nodo se asocia con su costo total desde la raíz, donde se les da mayor prioridad a los caminos de costo mínimo. El nodo en la cabeza de la cola es expandido, adicionando sus nodos vecinos con el costo total desde la raíz hasta el nodo respectivo. La búsqueda de costo uniforme es completa y óptima si el costo de cada paso excede algún límite eps positivo.[1] El tiempo para el caso peor y la complejidad espacial es O(b1 + C*/ε), donde C* es el costo de la solución óptima y b es el factor de ramificación. Cuando todos los costos entre los nodos son iguales, esto se convierte en O(bd + 1).[2]
Relación con otros algoritmos
editarEl algoritmo de Dijkstra, que es quizás más conocido, puede considerarse como una variante de Búsqueda de Costo Uniforme, donde no hay un estado meta (goal) y el procesamiento continúa hasta que todos los nodos han sido eliminados de la cola con prioridad, es decir, hasta que los caminos más cortos a todos los nodos (no sólo un nodo objetivo) se han determinado. Al igual que en el algoritmo de Dijkstra, BCU garantiza que (si todos los pesos de las aristas son no negativos) el camino más corto a un nodo particular, se ha encontrado una vez que el nodo se extrae de la cola con prioridad.
La Búsqueda de Costo Uniforme es un caso particular del algoritmo de búsqueda A* si la heurística de este último es una función constante (por tanto ya no sería una búsqueda informada sino ciega). Si A* se utiliza con una heurística monótona, entonces se puede convertir en una Búsqueda de Costo Uniforme restando de cada costo de arista a la disminución en el valor heurístico a lo largo de esa arista. Búsqueda Primero a lo Ancho (BPA o BFS en inglés) es un caso especial de BCU cuando los costos de las aristas son positivos e idénticos. BPA visita primero el nodo con la longitud del camino más corto (número de nodos) desde el nodo raíz, en cambio, UCS primero visita el nodo con la ruta más corta en costo (suma de los pesos de las aristas) desde el nodo raíz.
Búsqueda de Costo Uniforme es una variante del algoritmo Búsqueda Primero el Mejor.
Pseudocode de Búsqueda de Costo Uniforme
editarprocedure 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
Proceso de expansión mostrando el conjunto "explored" y la cola con prioridad "frontier":
root: A
goal: G
| Paso | “frontier” (nodos y sus costos) | Ampliar* | “explored”: conjunto de nodos |
|---|---|---|---|
| 1 | {(A,0)} | A | ∅ |
| 2 | {(D,3),(B,5)} | D | {A} |
| 3 | {(B,5),(E,5),(F,5)} | B | {A,D} |
| 4 | {(E,5),(F,5),(C,6)} | E | {A,D,B} |
| 5 | {(F,5),(C,6)}** | F | {A,D,B,E} |
| 6 | {(C,6),(G,8)} | C | {A,D,B,E,F} |
| 7 | {(G,8)} | G | {A,D,B,E,F,C} |
| 8 | ∅ |
* nodo a expandir en el próximo paso.
* B no se añade a la frontera (frontier) porque se encuentra en el conjunto explorado (explored).
Camino encontrado: A-D-F-G.
Referencias
editar- ↑ Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, ISBN 0-13-790395-2
- ↑ Stuart Russell; Peter Norvig (2010). Artificial Intelligence: A Modern Approach (3 edición). Prentice Hall. ISBN 978-0-13-604259-4.
Datos: Q10787701
