b'\n_START_ARTICLE_\nB\xc3\xbasqueda de costo uniforme\n_START_PARAGRAPH_\nEn ciencia de la computaci\xc3\xb3n, la b\xc3\xbasqueda de costo uniforme (BCU) es un algoritmo de b\xc3\xbasqueda no informada utilizado para recorrer sobre grafos el camino de costo m\xc3\xadnimo entre un nodo ra\xc3\xadz y un nodo destino. La b\xc3\xbasqueda comienza por el nodo ra\xc3\xadz y contin\xc3\xbaa visitando el siguiente nodo que tiene menor costo total desde la ra\xc3\xadz. Los nodos son visitados de esta manera hasta que el nodo destino es alcanzado._NEWLINE_T\xc3\xadpicamente, el algoritmo implica la expansi\xc3\xb3n de nodos mediante la adici\xc3\xb3n, a una cola con prioridad, de todos los nodos vecinos no expandidos que est\xc3\xa1n conectados al \xc3\xbaltimo nodo analizado. En la cola, cada nodo se asocia con su costo total desde la ra\xc3\xadz, donde se les da mayor prioridad a los caminos de costo m\xc3\xadnimo. El nodo en la cabeza de la cola es expandido, adicionando sus nodos vecinos con el costo total desde la ra\xc3\xadz hasta el nodo respectivo. La b\xc3\xbasqueda de costo uniforme es completa y \xc3\xb3ptima si el costo de cada paso excede alg\xc3\xban l\xc3\xadmite eps positivo.\xe2\x80\x8b El tiempo para el caso peor y la complejidad espacial es O(b1 + C*/\xce\xb5), donde C* es el costo de la soluci\xc3\xb3n \xc3\xb3ptima y b es el factor de ramificaci\xc3\xb3n. Cuando todos los costos entre los nodos son iguales, esto se convierte en O(b\xe1\xb5\x88 \xe2\x81\xba \xc2\xb9).\xe2\x80\x8b\n_START_SECTION_\nRelaci\xc3\xb3n con otros algoritmos\n_START_PARAGRAPH_\nEl algoritmo de Dijkstra, que es quiz\xc3\xa1s m\xc3\xa1s conocido, puede considerarse como una variante de B\xc3\xbasqueda de Costo Uniforme, donde no hay un estado meta (goal) y el procesamiento contin\xc3\xbaa hasta que todos los nodos han sido eliminados de la cola con prioridad, es decir, hasta que los caminos m\xc3\xa1s cortos a todos los nodos (no s\xc3\xb3lo 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\xc3\xa1s corto a un nodo particular, se ha encontrado una vez que el nodo se extrae de la cola con prioridad._NEWLINE_La B\xc3\xbasqueda de Costo Uniforme es un caso particular del algoritmo de b\xc3\xbasqueda A* si la heur\xc3\xadstica de este \xc3\xbaltimo es una funci\xc3\xb3n constante (por tanto ya no ser\xc3\xada una b\xc3\xbaqueda informada sino ciega). Si A* se utiliza con una heur\xc3\xadstica mon\xc3\xb3tona, entonces se puede convertir en una B\xc3\xbasqueda de Costo Uniforme restando de cada costo de arista a la disminuci\xc3\xb3n en el valor heur\xc3\xadstico a lo largo de esa arista. B\xc3\xbasqueda Primero a lo Ancho (BPA o BFS en ingl\xc3\xa9s) es un caso especial de BCU cuando los costos de las aristas son positivos e id\xc3\xa9nticos. BPA visita primero el nodo con la longitud del camino m\xc3\xa1s corto (n\xc3\xbamero de nodos) desde el nodo ra\xc3\xadz, en cambio, UCS primero visita el nodo con la ruta m\xc3\xa1s corta en costo (suma de los pesos de las aristas) desde el nodo ra\xc3\xadz._NEWLINE_B\xc3\xbasqueda de Costo Uniforme es una variante del algoritmo B\xc3\xbasqueda Primero el Mejor.'