DOCUMENTACIÓ HILL CLIMBING


Descripció

Característiques:

Per cada node visitat genera els seus fills i escull el millor segons la funció heurística. Si un node no té fills, l'algorisme acaba. No hi ha backtracking.

Problemes que presenta la cerca "Hill Climbing":

Aquest problemes són especialment crítics en el "Hill Climbing", ja que no pot desfer part del principi de solució i continuar. Cada decisió que pren és definitiva i no es pot tornar enrera.

Exemple d'ordre d'exploració i evolució de la llista de nodes:

Pseudocodi

Algorisme hill_climbing (node node_inicial)

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