inteligenta artificiala: strategii de cautare

Click here to load reader

Post on 26-Jun-2015

813 views

Category:

Documents

12 download

Embed Size (px)

DESCRIPTION

Inteligenta artificiala2. Strategii de cautareFlorin LeonUniversitatea Tehnica „Gh. Asachi” Iaşi Facultatea de Automatică şi Calculatoare http://florinleon.byethost24.com/curs_ia.htmFlorin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmStrategii de căutare1. 2. 3. 4. Rezolvarea problemelor prin căutare Căutarea neinformată (oarbă) Căutarea informată (euristică) Concluzii2Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htmS

TRANSCRIPT

Inteligen artificial 2. Strategii de cutare Florin Leon Universitatea Tehnic Gheorghe Asachi din Iai Facultatea de Automatic i Calculatoare http://florinleon.byethost24.com/curs_ia.htm Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm2 Strategii de cutare 1. Rezolvarea problemelor prin cutare 2. Cutarea neinformat (oarb) 3. Cutarea informat (euristic) 4. Concluzii Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm3 Strategii de cutare 1. Rezolvarea problemelor prin cutare 2. Cutarea neinformat (oarb) 3. Cutarea informat (euristic) 4. Concluzii Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm4 Probleme de cutare 15 puzzle Turnurile din Hanoi Labirinturi8 regine Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm5 Probleme de cutare reale PlanificareGsirea rutelor Programarea telescoapelorNavigarea roboilor militari Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm6 Alte aplicaii Gsirea rutelor Rezervarea biletelor pentru avioane, trenuri etc. Reele de calculatoare Distribuia coletelor potale Asemntoare problemei comis-voiajorului Proiectarea instalaiilor, VLSI Proiectarea cablurilor i evilor ntr-o cldire, ntr-o main Conectarea pinilor circuitelor electronice, cu scopulde a minimiza aria i de a maximiza viteza prin minimizarea lungimii conexiunilor Crearea medicamentelor Gsirea substanelor celor mai potrivite care permit substanei active s se cupleze la zona dorit Jocuri video Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm7 Componentele unei probleme de cutare Starea iniial Starea scop O mulime de operatori Funcia de evaluare pentru cutarea informat Ct de departe este fiecare stare de starea scop Conine cunotine despre fiecare problem n parte Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm8 Formalizarea unei probleme de cutare Q este o mulime finit de stri S _ Q este o mulime nevid de stri iniiale G _ Q este o mulime nevid de stri scop succs : Q (Q) reprezint mulimea de stri care pot fi atinse din starea s ntr-un singur pas Funcia primete o singur stare ca argument i returneazo mulime de stri ca rezultat cost : Q2 R+ reprezint costul de a ajunge din starea sn starea s Funcia primete 2 stri i returneaz un numr pozitiv cost(s,s ) este definit doar cnd s e succs(s) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm9 Definiii Spaiu de cutare (spaiul problemei) Mulimea tuturor strilor care pot fi atinse prin aplicarea operatorilor disponibili Soluie Seria de operatori care transform starea iniial ntr-ostare scop Metod de rezolvare a unei probleme O procedur pentru gsirea unei soluii Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm10 Rezolvarea unei probleme prin cutare Stare iniial Stare scop Spaiul de cutare (spaiul problemei) Soluie Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm11 Soluia O soluie este o cale care leag nodul iniial de oricare din nodurile scop I G Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm12 Soluia O soluie este o cale care leag nodul iniial de oricare din nodurile scop Costul cii este suma costurilor arcelor care formeaz calea O soluie optim este soluia de cost minim Unele problemenu au soluie! I G Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm13 Existena soluiei 12 14 11 15 10 13 9 5678 4321 12 15 11 14 10 13 9 5678 4321 ? 1000 $ Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm14 Dimensiuneaspaiului de cutare 8-puzzle 9! = 362.880 stri 15-puzzle 16! ~ 2 1013 stri 24-puzzle 25! ~ 1025 stri Doar jumtate din aceste stri pot fi atinse dintr-o stare dat Dar ntr-o abordare simpl acest lucru nu se cunoate dinainte Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm15 Cutarea n spaiul problemei Deseori construirea unei reprezentri complete a grafului de cutarenu este fezabil sau este prea costisitoare Algoritmul de rezolvare trebuie s construiasc soluia prin explorarea unei poriuni restrnse a grafului Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm16 Cutarea n spaiul problemei Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm17 Cutarea n spaiul problemei Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm18 Cutarea n spaiul problemei Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm19 Cutarea n spaiul problemei Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm20 Cutarea n spaiul problemei Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm21 Cutarea n spaiul problemei Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm22 Reprezentarea Care este spaiul problemei? Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm23 Costul unui pas orizontal / vertical = 1 Costul unui pas diagonal = \2Abordarea 1 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm24 Soluia optim Aceast cale este cea mai scurt n spaiul discretizat, dar nu i n spaiul iniial continuu Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm25 Abordarea 2 Costul unui pas: lungimea segmentului Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm26 Abordarea 2 Costul unui pas: lungimea segmentului Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm27 Soluia Cea mai scurt cale n acest spaiu estecea mai scurt i n spaiul iniial Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm28 Misionarii i canibalii 3 misionari, 3 canibali, 1 barc Barca poate duce 2 persoane Dac sunt mai muli canibali dect misionari, i mnnc 5 operatori: 1C, 1M, 2C, 2M, CM Alternativ: persoanele individuale (27 de operatori) Reprezentare: numrul de persoane pe primul mal i barca Starea iniial: (3, 3, 1) Starea scop: (0, 0, 0) O reprezentare mai bun reduce spaiul de cutare Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm29 Presupuneri Mediul este static Mediul este discret (sau discretizabil) Mediul este accesibil (observabil) Mediul este determinist Multe din aceste presupuneri pot fi nlturate i cutarea tot rmne o metod important de rezolvare a problemelor Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm30 Noduri i stri Un nod este o structur de date n program O stare este o configuraie a problemei Un nod are: Stare Nod printe Operatorul care a fost aplicat pentru a-l genera Adncime Cost (al cii parcurse din starea iniial) Dou noduri diferite pot conine aceeai stare! Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm31 Frontiera arborelui de cutare Frontiera (engl. fringe) este mulimea tuturor nodurilor care nu au fost nc expandate 1 2 34 56 7 8 1 2 34 56 7 8 1 2 34 56 78 1 3 56 8 1 3 4 56 7 8 2 47 2 1 2 34 56 7 8 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm32 Strategia de cutare Frontiera este implementat ca o list Ordonarea nodurilor n frontier definete strategia de cutare De exemplu tratarea listei ca o coad sauca o stiv Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm33 Msuri de performan Completitudine Un algoritm este complet dac gsete o soluie atunci cnd exist una Dar dac nu exist o soluie? Optimalitate Un algoritm este optim dac returneaz o soluie de cost minim cnd problema are soluii Complexitate Msoar timpul i volumul de memorie necesare algoritmului Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm34 Strategii de cutare 1. Rezolvarea problemelor prin cutare 2. Cutarea neinformat (oarb) 3. Cutarea informat (euristic) 4. Concluzii Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm35 Cutarea neinformat Raionamentul const n explorarea alternativelor Cutarea n lime (engl. breadth-first search) Cutarea bidirecional Cutarea n adncime (engl. depth-first search) Cutarea limitat n adncime (engl. depth-limited search) Cutarea iterativ n adncime (engl. iterative deepening search) Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm36 Cutarea n lime Nodurile noi sunt inserate la sfritul frontierei (lista e o coad) FRONTIERA = (1) 23 45 1 67 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm37 Cutarea n lime Nodurile noi sunt inserate la sfritul frontierei FRONTIERA = (2, 3) 23 45 1 67 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm38 Cutarea n lime Nodurile noi sunt inserate la sfritul frontierei FRONTIERA = (3, 4, 5) 23 45 1 67 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm39 Cutarea n lime Nodurile noi sunt inserate la sfritul frontierei FRONTIERA = (4, 5, 6, 7) 23 45 1 67 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm40 Parametri importani Numrul maxim de succesori ai oricrei stri Factorul de ramificare (engl. branching factor)b al arborelui de cutare Lungimea minim ( cost) a cii ntre starea iniial i o stare scop Adncimea (engl. depth) d a celui mai superficial nod scop din arborele de cutare Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm41 Evaluarea performanelor Cutarea n lime este: Complet Optim dac un pas are costul 1 Numrul de noduri generate (cazul cel mai defavorabil) 1 + b + b2 + + bd=(bd+1-1)/(b-1)=O(bd) Complexitatea de timp i de spaiu este O(bd) Numrul de n