pau sanchez

Comparativa BFS - UCS

Veure tots els algorismes
uniform cost search

BFS - UCS Comparative

Desenvolupador - Algorismes - ligència Artificial

Veure codi font

Descripció

S'explora a fons l'algoritme BFS fent la comparativa d'efectivitat posant els nodes expandits de nou a la frontera o sense posar-los..

Es duen a terme dos sub-experiments: el primer sobre un graf aleatori de 1000 nodes i 400 arestes aprox. (Depèn de les arestes que necessiti l'algoritme per connectar el graf aleatòriament). Es repeteix l'experiment 1000 vegades generant nodes de sortida-arribada aleatoris per demostrar que el BFS que no introdueix de nou els nodes expandits a la frontera, a més de ser igual de vàlid és també més òptim tenint en compte el cost, ja que necessita menys iteracions per trobar el resultat òptim.

El segon experiment es duu a terme utilitzant un graf predefinit que té forma de cub. En aquest cas més reduït, s'aprecia amb més facilitat el que passa realment durant l'execució dels dos algorismes.

Per la seva banda, s'explora a fons l'algoritme UCS i en aquest cas es demostra que l'algorisme que no torna a introduir els nodes a la frontera dóna un resultat erroni, retornant camins no òptims en determinats casos. Per dur a terme la demostració final es compara l'algoritme UCS vàlid amb un altre algorisme per força bruta usant la tècnica del Backtracking, demostrant que en aquest cas, tots dos tornen sempre camins de cost mínim, és a dir, camins òptims.

Llenguatges i detalls tècnics

El llenguatge utilitzat per al desenvolupament de l'experiment és Python, utilitzant la llibreria Networkx per a grafs a més de la llibreria matplotlib per representar els resultats de forma gràfica.