Inteligență artificială - capitolul 1-strategii de căutare

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.

Universitatea Petrol-Gaze,Ploiesti