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)
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
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
