DOCUMENTACIÓ BEST FIRST

Hi ha 4 variants: A, A*, AO i AO*. Els algorismes A* i AO* utilitzen la funció formada per cost+heurística per a decidir quin node és el millor. I els AO i AO* poden les branques que no els portaran a cap solució.

Així com l'heurística és una estimació, el cost, en canvi, és real. La poda també ve definida per un criteri exacte, només quan sabem segur que un node no portarà a cap solució, és quan podem.

Cal tenir en compte, que segons el problema a resoldre, la poda és factible o no. Donat un node, i amb només la informació d'aquest estat, no sempre sabem si serà possible arribar a una solució.

Descripció

Característiques:

Per cada node visitat, genera els seus fills. Sempre escull la millor solució parcial segons la informació heurística, tant si és d'un nivell o d'un altre.

La cerca AO* és la més eficient de les estudiades en aquest projecte. Si la poda no és possible l'A* serà l'algorisme que generalment trobi la solució en el mínim nombre de passos. Els problemes del màxim local i del pla que hi havia al hill climbing, també són importants al best first, però aquí disposem del backtracking per a desfer un mal camí.

Exemple d'ordre d'exploració i evolució de la llista de nodes per l'algorisme A:

Exemple d'ordre d'exploració i evolució de la llista de nodes per l'algorisme A*:

Exemple d'ordre d'exploració i evolució de la llista de nodes per l'algorisme AO:

Exemple d'ordre d'exploració i evolució de la llista de nodes per l'algorisme AO*:

Pseudocodi

A la funció fills li passem dos booleans: cost i poda. Si cost és cert, al valor de l'heurística de cada node li sumarem el cost. I si poda és cert, eliminarem els fills que sabem segur que no ens portaran a la solució. Aquests booleans defineixen l'algorisme:

Algorisme

Cost

Poda

A

fals

fals

A*

cert

fals

AO

fals

cert

AO*

cert

cert

Algorisme best_first (node node_inicial, booleà cost, booleà poda)

FiAlgorisme

/* Llista ordenada segons el valor de l'heurística */

TAD llista ()

/* Crea una nova llista buida */

Funcio llista_buida (): llista

FiFuncio

/* Retorna CERT si llista està buida */

Funcio buida (llista l): boolean

FiFuncio

/* Retorna el millor node de la llista (el primer) */

Funcio millor (llista l): node

FiFuncio

/* Afegeix un node a la llista ordenadament */

Funcio afegir_elem (llista l, node n): llista

FiFuncio

/* Treu el millor node de la llista (el primer) */

Funcio treure_millor (llista l): llista

FiFuncio

/* Afegeix els nodes de la llista l2 a la llista l1 ordenadament */

Funcio afegir_llista (llista l1, llista l2): llista

FiFuncio

FiTAD

Inici Anterior