aspecte teoretice termen de predare -...

Tema 2 Metode de căutare neinformată și informată

Laura Dioşan 1 Inteligenţă artificială, 2016-2017

Rezolvarea problemelor de căutare

Obiective Formularea problemelor ca probleme de căutare şi identificarea modalităţilor de rezolvare a lor.

Specificarea, proiectarea şi implementarea metodelor de căutare.

Aspecte teoretice

Rezolvarea problemelor ca proces de căutare

Tipuri de probleme de căutare.

Modalităţi de rezolvare a problemelor de căutare construirea progresivă a soluţiei:

- Stabilirea componentelor problemei

o Stare iniţială

o Stare finală

o Operatori (funcţii succesor)

o Soluţie

- Definirea spaţiul de căutare

- Stabilirea strategiei de identificare a soluţiei în spaţiul de căutare

Termen de predare Cerința C1 - pe loc (in cadrul laboratorului 2)

Cerința C2 - laborator 3

Cerinţe

C1. Subalgoritmi de căutare Implementați (în Python) câte un subalgoritm pentru fiecare din cerințele următoare. Codul

corespunzător unui subalgoritm poate fi notat cu maxim 5 puncte. Sub-algoritmii trebuie să

respecte specificarea dată și vor fi evaluați cu ajutorul a 5 aserțiuni. Fiecare aserțiune corectă

valoarează 1 punct.

1. subalgoritm distanțaMotyka:

Descriere: determină distanța Motyka între 2 vectori de numere întregi

Input: 2 vectori de numere întregi (de aceeași lungime)

Output: distanța Motyka

Exemplu:

In: [2,4,1], [1,2,3]

Out: 0.4

Punctaj: 5p pentru cod și 5x1p pentru aserțiuni

2. subalgoritm distanțaRuzicka:

Descriere: determină distanța Ruzicka între 2 vectori de numere întregi

Input: 2 vectori de numere întregi (de aceeași lungime)

Output: distanța Ruzicka

Exemplu:

In: [2,4,1], [1,2,3]

Out: 0.44




3. subalgoritm distanțaEditare:

Descriere: determină distanța de editare între 2 vectori de caractere

Input: 2 vectori de caractere

Output: distanța de editare

Exemplu:

In: [a,b,c,d], [e,b,d]

Out: 2


4. subalgoritm DFS:

Descriere: parcurge în adâncime un arbore ternar (fără a folosi o stivă)

Input: rădăcina unui arbore ternar cu numere întregi în noduri

Output: un vector cu numerele din arbore

Exemplu:

In: rădăcina arborelui:

6

/ | \

4 2 7

/ \

3 5

Out: [6,4,3,5,2,7]

Punctaj: 15p pentru cod și 5x3p pentru aserțiuni 5. subalgoritm adiacență:

Descriere: Determină matricea de adiacență asociată unui arbore ternar

Input: rădăcina unui arbore ternar cu numere întregi în noduri

Output: Matricea de adiacență

Exemplu:

In: rădăcina arborelui:

1

/ | \

2 3 4

/ \

5 6

Out: [[0 1 1 1 0 0]

[1 0 0 0 1 1]

[1 0 0 0 0 0]

[1 0 0 0 0 0]

[0 1 0 0 0 0]

[0 1 0 0 0 0]]




C2. Probleme de căutare Specificaţi, proiectaţi şi implementaţi o aplicaţie care să rezolve una dintre următoarele

probleme. Aplicaţia trebuie să respecte diagrama din Figura 1 şi să permită:

- Încărcarea datelor problemei (probleme cu date deja definite de către programator,

probleme cu date definite de utilizator)

- Alegerea şi parametrizarea metodei de rezolvare a problemei

- Afişarea soluţiei identificate

- Precizarea performanţelor metodei de rezolvare alese

Figura 1 Diagrama de clase

Fiecare dintre probleme trebuie rezolvată cu cele 2 tehnici precizate (dar se pot adăuga şi tehnici

noi) – o tehnică neinformată şi o tehnică informată:

- breadth-first search (BFS)

- depth-first search (DFS)

- greedy best-fisrt search (GBFS)

Fiecare din cele 2 tehnici vor putea fi dezvoltate astfel:

varianta 1. pe baza unui tool deja existent.

Punctaj: 15p pentru cod, 10p pentru interfață și 5x3p pentru aserțiuni varianta 2. pe baza codului complet scris de către student.

Punctaj: 30p pentru cod, 10p pentru interfață și 5x6p pentru aserțiuni

Sisteme disponibile care implementează tehnici de căutare neinformată şi informată:

1. AIMA http://code.google.com/p/aima-java/

2. FAIF http://faif.sourceforge.net/index.html

3. BOOST http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/table_of_contents.html

1. Problema reginelor pe tabla de şah – tehnici de rezolvare: BFS, GBFS

Dându-se o tablă de şah cu nxm căsuţe, să se determine numărul maxim de regine care pot fi

http://code.google.com/p/aima-java/

http://faif.sourceforge.net/index.html

http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/table_of_contents.html



amplasate pe tablă astfel încât acestea să nu se atace reciproc. În Figura 2 sunt prezentate 2

exemple de rezolvare (corectă şi incorectă) a problemei pentru n = 5 şi m = 6.

R R

R R

R R

R R

R R

Figura 2 a) configuraţie validă; b) configuraţie invalidă pentru problema reginelor pentru o tablă cu 5x6 căsuţe

2. Jocul Sudoku – tehnici de rezolvare: BFS, GBFS

Dându-se un joc Sudoku (un puzzle logic reprezentat pe o tablă cu nxn căsuţe; unele căsuţe

conţin deja câte un număr, altele trebuie completate cu alte numere din {1,2,…,n} astfel încât

pe fiecare linie, fiecare coloană şi fiecare pătrăţel cu latura egală cu √n pătrăţele şă conţină

doar numere diferite), să se determine o modalitate corectă de completare a căsuţelor libere.

Figura 3 a) joc Sudoku cu 4x4 căsuţe; b) joc Sudoku cu 9x9 căsuţe

3. Jocul criptaritmeticii – tehnici de rezolvare: DFS, GBFS

Dezvoltaţi un algoritm care să rezolve eficient oricare dintre problemele de criptaritmetica

prezentate în Figura 4 ştiind că:

- Fiecare literă reprezintă o cifră hexazecimală;

- Rezultatul operaţiei artimetice trebuie să fie corect atunci când literele sunt înlocuite

cu cifre;

- Numerele nu pot începe cu cifra 0;

- Fiecare problem poate avea o singură soluţie. SEND+ TAKE+ EAT+ NEVER –

MORE= A THAT= DRIVE=

MONEY CAKE= APPLE RIDE

KATE

Figura 4 Probleme de criptaritmetică

4. Forme geometrice – tehnici de rezolvare: DFS, GBFS

Se consideră mai multe forme geometrice (ca cele date în Figura 5). Să se găsească un mod

de aranjare a acestor forme pe o tablă dreptunghiulară de nxm căsuţe astfel încât tabla să fie

acoperită cat mai uniform cu forme, toate formele să fie utilizate fără a se suprapune între ele.

Figura 5 a) Forme geometrice; b) tabla de joc 4 x 4 c) o solutie

5. Problema ordonării obiectelor – tehnici de rezolvare: DFS, GBFS

2 6 8 5

5 8 9 7

7 4 2 8

3 7 4 1 5

6 8 5

8 2 1 3

8 6 2 1

9 8 3 6

7 3 6 9

3 2

1 4

1 2 4

3 2 1



Să se ordoneze o listă de obiecte (de exemplu, o listă de numere întregi) utilizând un operator

de interschimbare a 2 obiecte din listă.

6. Problema comisului voiajor – tehnici de rezolvare: BFS, GBFS

Dându-se o hartă a oraşelor din Europa şi a distanţelor între ele (precum cea din Figura 6), să

se găsească cel mai scurt drum de la Bucureşti la Paris ştiind că distanţele între oraşe sunt

date în Tabel 1 şi Error! Reference source not found..

Figura 6 Harta oraşelor din Europa

Tabel 1 Distanţele între oraşele din harta din Figura 6

Tabel 2 Distanţele directe între Bucureşti şi celelalte oraşe din harta din Figura 6

7. Problema misionarilor şi canibalilor – tehnici de rezolvare: DFS, GBFS

Trei misionari şi trei canibali se află pe malul stâng al unui râu. Ei vor să treacă pe maul drept

cu ajutorul unei bărci care într-o cursă poate transporta doar 2 persoane. Numărul canibalilor

nu poate depăşi numărul misionarilor aflaţi pe unul dintre maluri pentru că misionarii ar fi

mâncaţi de canibali. Să se găsească o modalitate de traversare a misionarilor şi canibalilor pe

malul celălalt.

8. Problema traversării râului – tehnici de rezolvare: BFS, GBFS



Pe malul unui râu se află un adult, doi copii şi o mică barcă. Oamenii vor să traverseze râul

cu barca şi să ajungă pe celălalt mal. Barca poate transporta fie doi copii, fie un singur copil,

fie un singur adult. Să se găsească o modalitate de traversare a râului.

9. Problema puzzle-ului glisant – tehnici de rezolvare: BFS, GBFS

Se dă un puzzle pătrat cu nxn căsuţe care conţine numerele 1,2,…, nxn-1 (o căsuţă este goală)

aşezate într-o ordine iniţială. Să se găsească o modalitate de mişcare a numerelor astfel încât

ele să ajungă într-o ordine finală (dată) ştiind că un număr se poate deplasa în căsuţa liberă

doar dacă este vecin cu ea pe vertical sau pe orizontală. În

Figura 7 sunt prezentate 2 exemple de puzzle-uri (cu ordinea iniţială şi ordinea finală).

Figura 7 a) puzzle gilsant cu n=2; b) puzzle glisant cu n=3 (OI – ordinea iniţială, OF – ordinea finală)

10. Problema fermierului – tehnici de rezolvare: BFS, GBFS

Un fermier, o capră, un lup şi o varză se află pe malul unui râu şi doresc să treacă pe malul

celălalt cu ajutorul unei brci. Să se găsească o ordine de traversare ştiind că:

În barcă încap doar doi “călători”;

Lupul şi capra nu pot rămâne doar ei pe acelaşi mal (pentru că lupul ar mânca-o

pe capră);

Varza şi capra nu pot rămâne doar ele pe acelaşi mal (pentru ca varza ar fi âncată

de capră).

11. Problema săriturilor pe cuburi – tehnici de rezolvare: DFS, GBFS

Să se identifice o modalitate de coborâre de pe o piramidă formată din 1+22+32+…+n2 cuburi

de aceeaşi dimensiune, dar care au associate diferite scoruri, astfel încât punctajul acumulat

de-a lungul drumului parcurs să fie maxim. Piramida de cuburi este format astfel: un cub este

plasat pe alte 4 cuburi astfel încât fiecare sfert al cubului de sus se sprijină pe câte un cub (din

cele 4) de jos. Coborârea de pe un nivel pe altul presupune efectuarea unui salt de pe un cub

ci de pe nivelul i pe un cub ci+1 de pe nivelul i+1 (cubul cel mai de sus este plasat pe nivelul

1, cubul cel mai de jos este plasat pe nivelul n), cubul ci sprijinindu-se pe cubul ci+1 (a se

vedea şi desenul din Figura 8).

Figura 8 Piramida de cuburi

12. Problema plimbării prin triunghi – tehnici de rezolvare: DFS, GBFS

Să se identifice o modalitate de traversare de la vârf la bază a unui triunghi formată din

3 2 1

1 2 3

4 7 3 1 2

1 5 8 3 4 5

6 2 6 7 8

OI OF OI OF



1+2+3+…+n pătrate de aceeaşi dimensiune, dar care au associate diferite scoruri, astfel încât

punctajul acumulat de-a lungul drumului parcurs să fie maxim. Triunghiul este format din

mai multe nivele, fiecare nivel conţinând un anumit număr de pătrate. Pătratul cel mai de sus

este plasat pe nivelul 1, pătratele cele mai de jos se află pe nivelul n. Traversarea constă în

operaţii de coborâre şi/sau deplasare. Coborârea de pe un nivel pe altul presupune efectuarea

unui salt de pe un pătrat pi,j de pe nivelul i pe un pătrat pi+1,j de pe nivelul i+1, situate pe

aceeaşi coloană j (a se vedea şi desenul din Figura 8). Deplasarea (la stânga sau la dreapta)

presupune efectuarea unor paşi de pe un pătrat pij aflat pe nivelul i, coloana j pe un alt pătrat

vecin aflat tot pe nivelul i, dar pe coloana j-1 sau j+1.

9

5 7 2

5 8 2 4 1

6 3 1 9 4 3 2

4 5 7 2 3 4 5 1 9

Figura 9 Triunghiul de pătrate

13. Problema labirintului – tehnici de rezolvare: DFS, GBFS

Pentru realizarea unui sistem de iluminare, culoarele unui labirint dreptunghiular (a se vedea

Figura 10) au fost împărţite în pătrate, fiecare pătrat având un anumit cost. Să se determine

toate posibilităţile de ieşire din labirint şi cel mai ieftin drum de ieşire din labirint pornind

dintr-o locaţie interioară labirintului (dată).

3 1

1 6 9 4 3

9 7 7 1 5

4 7 3 6 2 7

5 5 8

4 5 2

2 8 3 7 8 1

8 4

Figura 10 Exemplu de labirint

14. Problema firului de telefon – tehnici de rezolvare: DFS, GBFS

Într-o clădire de birouri cu mai multe etaje se doreşte instalarea unei linii telefonice (prin

cablu). Ştiind că nu este posibilă instalarea cablului în fiecare birou (neexistând sufficient

cablu) să se identifice o modalitate optimă de distribuire a cablului în birouri astfel încât

numărul de angajaţi care pot vorbi la telefon din biroul lor să fie maxim. Se mai cunosc

următoarele informaţii:

la fiecare etaj se află acelaşi număr de birouri;

în fiecare birou există un număr de angajaţi;

cablul porneşte din biroul cel mai din stânga situat la parter şi se termină în biroul

cel mai din dreapta de la ultimul etaj;

cablul poate fi tras dintr-un birou în altul doar dacă cele 2 birouri sunt vecine (pe

orizontală sau pe verticală).

15. Problema ceasurilor – tehnici de rezolvare: DFS, GBFS

Într-un aeroport pe un perete există 9 ceasuri care indică ora corespunzătoare diferitelor oraşe



de pe glob. Ceasurile sunt plasate ca într-o matrice cu 3 linii şi 3 coloane. Ca urmare a unei

pene de current, ceasurile s-au dereglat şi trebuie reglate din nou. Pentru reglaj există 2

butoane care permit următoarele modificări:

Acţionarea în sus a primului buton creşte cu o unitate ora indicată de toate

ceasurile de pe o linie, iar acţionarea în jos va reduce cu o unitate ora indicată de

toate ceasurile de pe o linie;

Acţionarea în sus a celui de-al doilea buton creşte cu o unitate ora indicată de

toate ceasurile de pe o coloană, iar acţionarea în jos va reduce cu o unitate ora

indicată de toate ceasurile de pe o coloană.

Să se regleze corect ceasurile folosind cât mai puţin cele 2 butoane.

16. Problema şoricelului – tehnici de rezolvare: DFS, GBFS

În Figura 11 se dă un labirint de dimensiune 5x5 căsuţe în care pot să existe curse pentru

şoricei şi o “comoară” din brânză. Într-un colţ al labirintului se află un şoricel flămând care

simte mirosul brânzei, dar nu ştie unde este poziţionată aceasta. Ajutaţi-l pe şoricel să ajungă

la “comoara” de brânză astfel încât să nu fie prins într-una din curse ştiind că el se poate

deplasa fie pe orzontală, fie pe verticală.

Figura 11 Excursia şoricelului

17. Problema şantierului de construcţii – tehnici de rezolvare: DFS, GBFS

O firmă de construcţii are 4 excavatoare (A-D) cu care trebuie să finalizeze 4 proiecte

(W,X,Y,Z). Excavatoarele nu sunt foarte eficiente din punct de vedere al consumului de

motorină şi de aceea firma de cosntrucţii este nevoită să minimizeze costurile cu

combustibilul. Ajutaţi firma de construcţii să planifice excavatoarele pe proiecte ştiind că un

excavator poate lucra la un singur proiect o dată şi că implicarea unui excavator într-un

proiect presupune un anumit cost dat în Figura 12.

Figura 12 Costurile asociate excavatoarelor şi proiectelor corespunzătoare.

18. Problema colorării hărţilor – tehnici de rezolvare: BFS, GBFS

Se dă o hartă cu mai multe ţări (precizându-se care ţări se învecinează) şi 3 culori diferite. Să



se identifice o modalitate de colorare a hărţilor astfel încât 2 ţări vecine să nu fie colorate cu

aceeaşi culoare.

19. Problema partiţionării cadourilor – tehnici de rezolvare: DFS, GBFS

Doi fraţi au primit într-o cutie mai multe pungi cu bomboane, fiecare pungă conţinând un

anumit număr de bomboane şi vor să le împartă frăţeşte între ei astfel încât fiecare să

primeasca acelaşi număr de bomboane. Ajutaţi-I pe cei doi fraţi să identifice o modalitate de

împărţire a pungilor cu bomboane.

20. Problema Jocul întâlnirilor – tehnici de rezolvare: BFS, GBFS

Trei băieţi, trei fete şi şapte scaune joacă următorul joc: copii se aşează pe 6 din cele 7 scaune

disponibile, iniţial toţi băieţii unul lângă altul, apoi un scaun liber, apoi toate fetele (unele

lângă altele) – a se vedea şi Figura 13. Jocul permite efectuarea a 2 tipuri de mutări:

a. O persoană se poate muta pe un scaun vecin dacă acesta este liber, ceea ce

presupune un cost de o unitate;

b. O persoană poate sări peste una sau două personae până la un scaun liber, ceea ce

presupune un cost egal cu numărul de personae peste care a fost efectuat saltul.

Să se identifice o modalitate de mutare a persoanelor astfel încât să se formeze perechi băiat-

fată plasate pe scaune vecine – a se vedea Figura 14.

Figura 13 Jocul întâlnirilor – configuraţia iniţială

Figura 14 Jocul întâlnirilor – configuraţia finală

21. Problema lui Frobenius (problema schimbului de monezi) – tehnici de rezolvare:

BFS, GBFS

Se dau n monezi de valori întregi m1, m2, ..., mn astfel încât mi>1, pentru i =1,2,..,n şi

cmmdc(m1,m2,...,mn) = 1. Să se găsească cel mai mare număr întreg NF (numărul lui

Froebenius) care nu pote fi exprimat ca o combinaţie liniară a celor n monezi (NF =

a1m1+a2m2+...anmn).

aspecte teoretice termen de predare -...

Documents