Extras din curs
Strategia de cautare pe nivel în spatiul starilor
Strategia de cautare pe nivel (în latime, breadth-first search) este o strategie de cautare neinformata.
Strategia de cautare pe nivel începe expandarea cu nodul radacina, apoi expandeaza toate nodurile generate de radacina si continua expandarea cu toti succesorii acestora etc.
Implementarea strategiei de cautare pe nivel se realizeaza particularizând strategia generala de cautare prin implementarea listei FRONTIERA sub forma de coada.
Algoritm
1. initializeaza listele FRONTIERA {} si TERITORIU {}
2. daca FRONTIERA={} atunci
întoarce INSUCCES /*nu exista solutie*/
3. elimina primul nod S din FRONTIERA si insereaza-l în TERITORIU
4. expandeaza nodul S
4.1. genereaza toti succesorii directi Sj ai nodului S
4.2. pentru fiecare succesor Sj (1djdn) al lui S executa
4.2.1. stabileste legatura Sj ’ S
4.2.2. daca Sj este stare finala atunci
i. solutia este (Sj, S, ..., Si)
ii. întoarce SUCCES /* a fost gasita solutia */
4.2.3. daca Sj FRONTIERA TERITORIU atunci
/*evita reconsiderarea unei stari anterior generate*/
insereaza Sj în FRONTIERA, la sfârsit
5. repeta de la pasul 2
sfârsit
În cazul în care solutia exista, algoritmul întoarce solutia cale de lungime minima.
Caracteristici
Cautarea pe nivel este completa.
Cautarea pe nivel este optimala.
Complexitatea strategiei este exponentiala.
Aplicatia 1 – PROBLEMA COMIS-VOIAJORULUI
Enunt
Un comis-voiajor trebuie sa viziteze n orase conectate, astfel încât, plecând din orasul i sa treaca prin toate orasele o singura data si sa se reîntoarca în orasul i.
Starile problemei
Starea initiala
n reprezinta numarul de orase ce trebuie parcurse.
m reprezinta numarul de drumuri (un drum uneste doua orase).
ai,j reprezinta matricea drumurilor, unde .
si reprezinta orasul de plecare.
Starea finala
drumul parcurs de comis-voiajor.
Operatori
Se foloseste un operator de adaugare la configuratia curenta a unui oras care nu a fost deja vizitat si care este vecin cu ultimul oras al configuratiei.
Arborele de cautare
Pentru harta oraselor din figura 1.1 si orasul de plecare 2, o parte a arborelui de cautare este cel din figura 1.2.
Preview document
Conținut arhivă zip
- Inteligenta Artificiala - Capitolul 1-Strategii de Cautare.doc