Seminar 01 Metode de căutare neinformate și informate [611567]

Seminar 01 Metode de căutare neinformate și informate

Laura Dioșan 1 Inteligență artificial ă, 201 7-2018
Rezolvarea problemelor cu ajutorul met odelor de căutare


Obiective
Formularea problemelor ca probleme de optimizare și identificare modalităților de rezolvare a
lor. Specificarea, proiectarea și implementarea metodelor de căutare neinformată și informată .


Aspecte teoretice
Rezolvarea problemelor ca proces de căuta re
Tipuri de probleme de căutare .
Modalități de rezolvare a problemelor de căutare  Identificarea soluției potențiale optime:
– Stabilirea componentelor problemei
o Condiții (constrângeri) pe care trebuie să le satisfacă (parțial sau total) soluția
o Funcție de evaluare a unei soluții potențiale  identificareaa optimului
– Definirea s pațiul de căutare
– Stabilirea strategiei de identificare a soluției optime în spațiul d e căutare

Probleme abordate

1. Scurta prezentare a DFS, BFS, Greedy pe un arbore ”sintetic” cu adancime maxima 3
a. ordinea de vizitare a nodurilor în cele 3 cazuri
b. diferența majoră între DFS/BFS si Greedy (în cazul DFS/BFS nu avem costuri pe
muchiile arborelui, în cazul Greedy avem costuri si putem prioritiza cumva vizitarea
nodurilor)
2. Exemple de probleme – pentru fiecare problem ă ar trebui discutate următoarele aspecte
 cum modelăm stările spațiului de căutare
 cum creăm arborele aferent spațiului de căutare (ce reprezentare folosim, dacă se
reține tot arborele sau doar ”logica” lui)
 în ce ordine vizităm nodurile

1. Exemple de aplicare a strategiilor de căutare neinformate în jocul Tic Tac Toe.
 Crearea arborelui corespunzător spațiului de căutare (doar primele nivele)
 Parcurgerea arborelui conform strategiilor BFS, DFS

Seminar 01 Metode de căutare neinformate și informate

Laura Dioșan 2 Inteligență artificial ă, 201 7-2018

2. Rezolvarea problemei rucsacului.
Enunț: se dă un rucsac de capacitate M și n obiecte, fiecare având o anumită greutate
(wi, i = 1,2,…,n) și o anumită utilitate (u i, i=1,2,…,n). Să se umple rucsacul cu obiecte
astfel încât utilitatea obiectelor din rucsac să fie cât mai mare, iar greutatea obiectel or
selectate să nu depășească capacitatea rucsacului.

BFS …
DFS …
Greddy: O posibilă e uristică: alegem obiectele în ordinea descrescătoare a raportului
ui/wi.

Instanța 1: M = 10, n = 3 – greedy găsește soluția
A B C
wi 8 4 6
ui 3 4 6
După ordonare C, B, A

Alegem obiectul C  Uobiecte_alese = 6, W obiecte_alese =6, loc gol = 4

Seminar 01 Metode de căutare neinformate și informate

Laura Dioșan 3 Inteligență artificial ă, 201 7-2018
Alegem obiectul B  Uobiecte_alese = 10, W obiecte_alese =10, loc gol = 0

Instanța 2: M = 5, n = 3 – greedy nu găsește soluția
A B C
wi 4 3 2
ui 7 5 3
După ordonare A, B, C

Alegem obiectul A  Uobiecte_alese = 7, W obiecte_alese =4, loc gol = 1  nu mai încap alte
obiecte, dar soluția optimă este dată de alegerea lui B și C (U = 9, W = 5, loc gol = 0)

3. Problema comisului voiajor
DFS
BFS
Greedy: o posibilă euristică e cel mai apropiat vecin .

4. Problema broscuțelor.
Enunț: 2 șiruri de broscuțe (un șir cu n broscuțe roșii și un șir cu n broscuțe verzi) care se
deplasează pe aceeași direcție, dar în sensuri opuse, se întâlnesc la un moment dat.
Șirurile de broscuțe se opres c astfel încât între ele rămâne un singur loc liber. Broscuțele
vor să treaca unele în locul altora (cele roșii în locul celor verzi și invers) dar pot efectua
doar 2 tipuri de sărituri: „săritură simplă în față pe un loc gol” și „săritură dublă în față
peste o altă broscuță (de aceeași culoare sau de culoare diferită) pe un loc gol”.
Identificați succesiunea de mutări necesare inversării șirurilor de broscuțe.

Instanța 1: n = 3
Configurația inițială: RRR_VVV
Configurația finală: VVV_RRR
Spațiul de căutare (incomplet) poate fi reprezentat astfel:

RRR_VVV
RR_RVVV

RRRV_VV
R_RRVVV
RRVR_VV

RR_VRVV

_RRRVVV
RRV_RVV

RRVRV_V

RRVRVV_
_RRVRVV
R_RVRVV

RRV_RVV

R_VRRVV

RRVVR_V

RRV_VRV

RRVRVV_

_RRVRVV
RVR_RVV

R_VRRVV

RRVVR_V
_RVRRVV
RV_RRVV
RRVV_RV
RRVVRV_
R_VRVRV
RRVV_RV

RV_RRVV
RVRVR_V
_RVRRVV
RV_RRVV
RRVV_RV
RRVVRV_

Seminar 01 Metode de căutare neinformate și informate

Laura Dioșan 4 Inteligență artificial ă, 201 7-2018
RRRVV_V RRRVVV_

Euristici: f(n) = g(n)+h(n)
g(n) – nr de nivele parcurse în arborele de căutare până la nodul n
h(n) – nr de diferente între configurația broscuțelor fin nodul n și configurația finală
de ex. Pt nodul n = RRV_RVV, g(n) = 3 h(n) = 5 (2 broscuțe – una verde și una roșie – sunt
deja la locul lor)