La búsqueda de coste uniforme o Uniform-Cost Search (UCS) en inglés, es una estrategia de búsqueda no informada o ciega.
Este tipo de búsqueda a diferencia de breadth first search (BFS) y Depth First Search (DFS) tiene un atributo más llamado coste, el cual contiene el coste de cada nodo. Este coste afectará al resultado final.
EL VIAJERO (escenario)
![](https://i0.wp.com/www.apascualco.com/wp-content/uploads/2019/09/viajero.jpg?resize=244%2C253)
Supongamos que somos un viajero y queremos ir desde (A)sturias a (B)arcelona , nuestro método de transporte es el tren, nos da miedo volar.
Este método nos da una limitación, sobre la conexión de algunas ciudades, o bien porque hay un incidente en las vías o que el billete es demasiado caro, por eso facilitaremos un grafo de conexiones entre ciudades.
También tenemos una lista de ciudades, donde podemos descansar y cada una esta a una distancia concreta (coste). Nos interesa ir del punto A al punto B recorriendo la menor cantidad de kilómetros, superando las limitaciones del transporte y el lugar de descanso.
GRÁFO DE CONEXIÓN
![](https://i0.wp.com/www.apascualco.com/wp-content/uploads/2019/10/travelgraph.jpg?resize=640%2C404)
ESPACIO DE ESTADOS
Nuestro espacio, esta delimitado por la cantidad de ciudades y sus conexiones, en este caso hemos eliminado la conexión Santander to Oviedo, para ver la reacción de nuestro algoritmo de búsqueda, no informada.
Es bastante interesante y podéis «trastear» con él mediante los test que vienen en el código. Una de las pruebas que hice y podéis ver en el test, es modificar una conexión y ver cómo el resultado es diferente. Bastante interesante, aunque quiero hacer mas pruebas y ver el limite en la búsqueda.
Ejemplo de cuidad y conexiones en este grafo: Barcelona { zaragoza, 312;valencia, 220} y así sucesivamente.
El algoritmo que encontraréis en mi github (uno de mis githubs), podéis ver como vamos sumando la distancia en cada «camino», que estamos recorriendo.
IMPLEMENTACIÓN
![](https://i0.wp.com/www.apascualco.com/wp-content/uploads/2019/09/java-icon.jpeg?resize=51%2C51)