pau sanchez

BFS - UCS Comparative

See all algorithms
uniform cost search

BFS - UCS Comparative

Developer - Algorithms - Artificial Intelligence

View source code

Description

Se explora a fondo el algoritmo BFS haciendo la comparativa de efectividad poniendo los nodos expandidos de nuevo en la frontera o sin ponerlos.

Se llevan a cabo dos sub-experimentos: el primero sobre un grafo aleatorio de 1000 nodos y 400 aristas aprox. (depende de las aristas que necesite el algoritmo para conectar el grafo aleatoriamente). Se repite el experimento 1000 veces generando nodos de salida-llegada aleatorios para demostrar que el BFS que no introduce de nuevo los nodos expandidos en la frontera, además de ser igual de válido es también más optimo teniendo en cuenta el coste, ya que necesita menos iteraciones para dar con el resultado óptimo.

El segundo experimento se lleva a cabo usando un grafo predefinido que tiene forma de cubo. En este caso más reducido, se aprecia con más facilidad lo que sucede realmente durante la ejecución de los dos algoritmos.

Por su lado, se explora a fondo el algoritmo UCS y en este caso se demuestra que el algoritmo que no vuelve a introducir los nodos en la frontera da un resultado erróneo, devolviendo caminos no óptimos en determinados casos. Para llevar a cabo la demostración final se compara el algoritmo UCS válido con otro algoritmo por fuerza bruta usando la técnica del Backtracking, demostrando que en este caso, ambos devuelven siempre caminos de coste mínimo, es decir, caminos óptimos.

Languages and techniques

El lenguaje utilizado para el desarrollo del experimento es Python, utilizando la librería Networkx para grafos además de la librería Matplotlib para representar los resultados de forma gráfica.