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
Alții au mai descărcat și
Capitolul 1 Introducere 1.1 Concepte de baza Când s-a vorbit prima data de Inteligenţa Artificială (AI – Artificial Intelligence) în 1956, totul...
I. Obiective 1 De ce utilizarea tehnicilor de IA sunt importante? Inteligenţa artificială este un domeniu important din punct de vedere economic,...
In cadrul Inteligentei Artificiale, problemele de invatare, ocupa un loc aparte. Aceste preocupari se constituie intr-o directie distincta de...
1. ASPECTE GENERALE PRIVIND DOMENIUL INTELIGENTEI ARTIFICIALE Inteligenta artificiala (IA) s-a nascut în urma cu aproximativ 45 de ani, ca domeniu...
1. Istoria inteligentei artificiale Evolutia stiintei calculatoarelor si comporatarea umana a stimulat interesele rationarii pe masina, deoarece...
1. Introducere Tot mai larga circulaţie de care se bucură termenul de "inteligenţă artificială" este pe deplin justificată: devine din ce în ce în...
Inteligenţa artificială 1• Concepte de baza Inteligenţa Artificială poate fi definită ca simularea inteligenţei umane procesată de maşini, în...
1.1. Introducere Termenul de inteligenţă artificială a fost folosit pentru prima dată în 1956 de omul de ştiinţă american John McCarthy. Până...
Te-ar putea interesa și
Conceptul de evoluţie a fost propus de savantul englez Charles Darwin în 1859 în celebra sa carte “Originea speciilor prin selecţie naturală”....
Capitolul unu:Un sistem expert este un sistem bazat pe cunostinte care se bazeaza pe avantajul memoriilor sau capacitatiilor de memorii mari ale...
CAPITOLUL I INTRODUCERE Gramaticile eco-matriceale stratificate sunt un nou model al sistemelor paralele n-dimensionale care permit reprezentarea...
Capitolul 1 Obiective şi context Inteligenţa artificială (IA) este un domeniu care reţine din ce în ce mai mult atenţia economiştilor,...
1.1. Introducere Termenul de inteligenţă artificială a fost folosit pentru prima dată în 1956 de omul de ştiinţă american John McCarthy. Până...
Capitolul 1 INTRODUCERE ÎN INFORMATICA AGRARĂ 1.1. Definiţii şi noţiuni de bază Calculatorul a reuşit să preia multe sarcini pe care la început...
Capitolul 1 Ce este inteligenta artificiala? Dezvoltarea spectaculoasa a calculatoarelor in ultimii treizeci de ani a permis cercetarilor in...