Ia Lect 3
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Ia Lect 3 as PDF for free.
More details
- Words: 2,728
- Pages: 43
Inteligenta Artificiala Universitatea Politehnica Bucuresti Anul universitar 2005-2006
Adina Magda Florea http://turing.cs.pub.ro/ia_06
Curs nr. 3 Strategii de rezolvare a problemelor
Problema satisfacerii restrictiilor Strategii de cautare in jocuri
1. Problema satisfacerii restrictiilor {X1,...,X n }
R j ⊂ Di1 ×...× Di j
{D1,...,D n }
{R 1,...,R k }
Gradul unei variabile Aritatea unei restrictii Gradul problemei Aritatea problemei
Xi1,...,X i j {(X1 , x j ),...,(X n , x j )} 1
n
2.1 Instante ale CSP Determinarea unei solutii sau a tuturor solutiilor CSP totala CSP partiala CSP binara – graf de restrictii CSP – problema de cautare, in NP Sub-clase de probleme cu timp polinomial Reducerea timpului (reducerea sp. de cautare)
Algoritm: Backtracking nerecursiv 1. Initializeaza FRONTiERA cu {Si} /* Si este starea initiala */ 2. daca FRONTIERA = { } atunci intoarce INSUCCES /* nu exista solutie /* 3. Fie S prima stare din FRONTIERA 4. daca toate starile succesoare ale lui S au fost deja generate atunci 4.1.Elimina S din FRONTIERA 4.2.repeta de la 2 5. altfel 5.1.Genereaza S', noua stare succesoare a lui S 5.2.Introduce S' la începutul listei FRONTIERA 5.3.Stabileste legatura S’→ S 5.4.Marcheaza în S faptul cã starea succesoare S' a fost generata 5.5.daca S' este stare finala atunci 5.5.1. Afiseaza calea spre solutie urmarind legaturile S’→ S .. 5.5.2. întoarce SUCCES /* s-a gasit o solutie */ 5.6.repeta de la 2 sfarsit.
2.2 Notatii
X1, …, XN variabilele problemei, N fiind numarul de variabile ale problemei, U - intreg care reprezinta indicele variabilei curent selectate pentru a i se atribui o valoare F - vector indexat dupa indicii variabilelor, in care sunt memorate selectiile de valori facute de la prima variabila si pana la variabila curenta
adevarat daca exista restrictia R U1 U 2 (F[U1 ], F[U 2 ]) Relatie (U1 , F[U1 ], U 2 , F[U 2 ]) = R U1 U 2 ⊂ D U 1 × D U 2 fals in caz contrar
Algoritm:
Backtracking recursiv
BKT (U, F) pentru fiecare valoare V a lui XU executa 1. F[U] ← V 2. daca Verifica (U,F) = adevarat atunci 2.1. daca U < N atunci BKT(U+1, F) 2.2. altfel 2.2.1. Afiseaza valorile din vectorul F /* F reprezinta solutia problemei */ 2.2.2. intrerupe ciclul sfarsit.
Verifica (U,F) 1. test ← adevarat 2. I ← U - 1 3. cit timp I > 0 executa 3.1. test ← Relatie(I, F[I], U, F[U]) 3.2. I ← I - 1 3.3. daca test = fals atunci intrerupe ciclul 4. intoarce test sfarsit.
2.3 Imbunatatirea performantelor BKT Algoritmi de imbunatatire a consistentei reprezentarii
Consistenta locala a arcelor sau a cailor in graful de restrictii
Algoritmi hibrizi
Imbunatatesc performantele rezolvarii prin reducerea numarului de teste. Tehnici prospective: - Algoritmul de cautare cu predictie completa - Algoritmul de cautare cu predictie partiala - Algoritmul de cautare cu verificare predictiva Tehnici retrospective: - Algoritmul de backtracking cu salt - Algoritmul de backtracking cu marcare - Algoritmul de backtracking cu multime conflictuala
Utilizarea euristicilor
Algoritmi de imbunatatire a consistentei reprezentarii
Propagarea restrictiilor D X1 = D X2 = D X3 = {a, b,c}
X 1 R = {(a,b),(b,c)} 12
R 13= {(a,c),(c,b)}
X2
X1
R 12= {(a,b)}
R 13= {(a,c)} X3 (a)
X2
R 23= {b,c)} X3 (b)
2.4 Propagarea locala a restrictiilor
Combinatia de valori x si y pentru variabilele Xi si Xj este permisa de restrictia explicita Rij(x,y).
Un arc (Xi, Xj) intr-un graf de restrictii orientat se numeste arc-consistent daca si numai daca pentru orice valoare x ∈ Di, domeniul variabilei Xi, exista o valoare y ∈ Dj, domeniul variabilei Xj, astfel incat Rij(x,y). Graf de restrictii orientat arc-consistent
Algoritm: AC-3: Realizarea arc-consistentei pentru un graf de restrictii. 1.
Creeaza o coada Q ← { (Xi, Xj) | (Xi, Xj) ∈ Multime arce, i≠j}
2.
cat timp Q nu este vida executa 2.1. Elimina din Q un arc (Xk, Xm) 2.2.
Verifica(Xk, Xm)
2.3.
daca subprogramul Verifica a facut schimbari in domeniul variabilei Xk
atunci Q ← Q ∪ { (Xi, Xk) | (Xi, Xk)∈Multime arce, i≠k,m} sfarsit. Verifica (Xk, Xm) pentru fiecare x ∈ Dk executa 1.
daca nu exista nici o valoare y ∈ Dm astfel incat Rkm(x,y) atunci elimina x din Dk
Cale-consistenta
O cale de lungime m prin nodurile i0,…,im ale unui graf de restrictii orientat se numeste m-caleconsistenta daca si numai daca pentru orice valoare x ∈ Di0, domeniul variabilei i0 si o valoare y ∈ Djm, domeniul variabilei im, pentru care Ri0im(x,y), exista o secventa de valori z1∈ Di1 … zm-1 ∈ Dim-1 astfel incat Ri0i1(x,z1), …, Rim-1im(zm-1,y) Graf de restrictii orientat m-arc-consistent Graf minim de restrictii n-cale-consistenta Comentarii
Complexitate
N - numarul de variabile a - cardinalitatea maxima a domeniilor de valori ale variabilelor e - numarul de restrictii. Algoritmului de realizare a arc-consistentei - AC-3: complexitate timp este O(e*a3); complexitate spatiu: O(e+N*a) S-a gasit si un algoritm de complexitate timp O(e*a2) – AC-4 Algoritmul de realizare a 2-cale-consistentei - PC-4: complexitatea timp O(N3*a3)
2.5 CSP fara bkt - conditii
Graf de restrictii ordonat Latimea unui nod Latimea unei ordonari a nodurilor Latimea unui graf de restrictii RAC
A
B RCB
C
Niv 3 C Niv 2 A Niv 1 B
A C B
B A C
Teoreme
Daca un graf de restrictii arc-consistent are latimea egala cu unu (i.e. este un arbore), atunci problema asociata grafului admite o solutie fara backtracking. Daca un graf de restrictii 2-cale-consistent are latimea egala cu doi, atunci problema asociata grafului admite o solutie fara backtracking.
d-consistenta
Fiind data o ordonare d a variabilelor unui graf de restrictii R, graful R este d-arc-consistent daca toate arcele avand directia d sint arcconsistente. Fie un graf de restrictii R, avind ordonarea variabilelor d cu latimea egala cu unu. Daca R este d-arc-consistent atunci cautarea dupa directia d este fara backtracking.
d-consistenta Algoritm: Realizarea d-arc-consistentei unui graf de restrictii cu ordonarea variabilelor (X1,…,XN) pentru I ← N la 1 executa 1. pentru fiecare arc (Xj, Xi) cu j < i executa 1.1. Verifica(Xj, Xi) sfarsit.
Complexitatea timp: O(e*a2)
2.6 Tehnici prospective
Conventii Notatii: U, N, F (F[U]), T (T[U] … XU), TNOU adevarat daca R U1 U 2 (L1 , L 2 ) Relatie(U1, L1, U2, L2) = în caz contrar fals
Verifica_Inainte Verifica_Viitoare Predictie completa Predictie partiala Verificare predictiva
Algoritm:
Backtracking cu predictie completa
Predictie(U, F, T) pentru fiecare element L din T[U] executa 1. F[U] ← L 2. daca U < N atunci //verifica consistenta atribuirii 2.1 TNOU ← Verifica_Inainte (U, F[U], T) 2.2 daca TNOU ≠ LINIE_VIDA atunci TNOU ← Verifica _Viitoare (U, TNOU) 2.3 daca TNOU ≠ LINIE_VIDA atunci Predictie (U+1, F, TNOU) 3. altfel afiseaza atribuirile din F sfarsit
Verifica_Inainte (U, L, T) 1. TNOU ← tabela vida 2. pentru U2 ← U+1 pana la N executa 2.1 pentru fiecare element L2 din T[U2] executa 2.1.1 daca Relatie(U, L, U2, L2) = adevarat atunci introduce L2 in TNOU[U2] 2.2 daca TNOU[U2] este vida atunci intoarce LINIE_VIDA 3. intoarce TNOU sfarsit
Verifica_Viitoare (U, TNOU) daca U+1 < N atunci 1. pentru U1 ← U+1 pana la N executa 1.1 pentru fiecare element L1 din TNOU[U1] executa 1.1.1 pentru U2 ← U+1 pana la N, U2≠U1 executa i. pentru fiecare element L2 din TNOU[U2] executa - daca Relatie (U1, L1, U2, L2) = adevarat atunci intrerupe ciclul //dupa L2 ii. daca nu s-a gasit o valoare consistenta pentru U2 atunci - elimina L1 din TNOU[U1] - intrerupe ciclul // dupa U2 1.2 daca TNOU[U1] este vida atunci intoarce LINIE_VIDA 2. intoarce TNOU sfarsit
BKT cu predictie partiala
Se modifica Verifica_Viitoare pasii marcati cu rosu
Verifica_Viitoare (U, TNOU) daca U+1 < N atunci 1. pentru U1 ← U+1 pana la N - 1 executa 1.1 pentru fiecare element L1 din TNOU[U1] executa 1.1.1 pentru U2 ← U1+1 pana la N executa i. pentru fiecare element L2 din TNOU[U2] executa - daca Relatie (U1, L1, U2, L2) = adevarat atunci intrerupe ciclul //dupa L2 ii. daca nu s-a gasit o valoare consistenta pentru U2 atunci - elimina L1 din TNOU[U1] - intrerupe ciclul // dupa U2 1.2 daca TNOU[U1] este vida atunci intoarce LINIE_VIDA 2. intoarce TNOU sfarsit
BKT cu verificare predictiva
Se elimina apelul Verifica_Viitoare(U, TNOU) in subprogramul Predictie
Algoritm:
Backtracking cu verificare predictiva
Predictie(U, F, T) pentru fiecare element L din T[U] executa 1. F[U] ← L 2. daca U < N atunci //verifica consistenta atribuirii 2.1 TNOU ← Verifica_Inainte (U, F[U], T) 2.2 daca TNOU ≠ LINIE_VIDA atunci TNOU ← Verifica _Viitoare (U, TNOU) 2.2 daca TNOU ≠ LINIE_VIDA atunci Predictie (U+1, F, TNOU) 3. altfel afiseaza atribuirile din F sfarsit
2.7 Tehnici retrospective
Backtracking cu salt D ={escarpeni, pantofi de tenis} Pf
Pantofi {(escarpeni, albã)} D ={verde, albã}
Cãmãºi
(pantofi de tens, gris) (pantofi tenis, alba) {(escarpeni, gri), (pantofi de tenis, jeans)} Pantaloni
D ={gri, bleu, jeans}
C
Pt
{(verde, gri), (verde, jeans), (albã, jeans), (albã, bleu)}
Pantofi Pantaloni Cãmãºi
escarpeni jeans
1 bleu verde
pantofi de tenis
gri 2
(a)
1
jeans
albã verde
bleu
gris 1
albã
(b) verde
alba
verde
alba
Algoritm: Backtracking cu salt BacktrackingCuSalt(U, F, Nivel) /* NrBlocari, NivelVec, I, test, Nivel1 – var locale */
1. NrBlocari ← 0, I ← 0, Nivel ← U 2 pentru fiecare element V a lui XU executa 2.1 F[U] ← V 2.2 test, NivelVec[I] ← Verifica (U, F) 2.3 daca test = adevarat atunci 2.3.1 daca U < N atunci i. BacktrackingCuSalt (U+1, F, Nivel1) ii. daca Nivel1 < U atunci salt la sfarsit 2.3.2 altfel afiseaza valorile vectorului F // solutia 2.4 altfel NrBlocari ← NrBlocari + 1 2.5 I ← I + 1 3. daca NrBlocari = numar valori ale lui X[U] si toate elementele din NivelVec sunt egale atunci Nivel ← NivelVec[1] sfarsit
Verifica (U, F) 1. test ← adevarat 2. I ← U-1 3. cat timp I>0 executa 3.1 test ← Relatie(I, F[I], U, F[U]) 3.2 daca test = fals atunci intrerupe ciclul 3.3 I ← I –1 4. NivelAflat ← I 5. intoarce test, NivelAflat sfarsit
2.8 Euristici
Ordonarea variabilelor Ordonarea valorilor Ordonarea testelor
3. Strategii de cautare in jocuri
Jocuri ce implică doi adversari
jucator adversar
Jocuri in care spatiul de cautare poate fi investigat exhaustiv Jocuri in care spatiul de cautare nu poate fi investigat complet deoarece este prea mare.
3.1 Minimax pentru spatii de cautare investigate exhaustiv
Jucator – MAX Adversar – MIN Principiu Minimax Etichetez fiecare nivel din AJ cu MAX (jucator) si MIN (adversar) Etichetez frunzele cu scorul jucatorului Parcurg AJ
daca nodul parinte este MAX atunci i se atribuie valoarea maxima a succesorilor sai; daca nodul parinte este MIN atunci i se atribuie valoarea minima a succesorilor sai.
Spatiu de cautare Minimax (AJ)
MAX
A/3
MIN
MAX
B/3
E/3
F / 12
C/2
G/8
H/2
I/4
D/2
J/6
K / 14
L/5
M/2
Spatiu de cautare Minimax (AJ) Nim cu 7 bete MIN
7/1
MAX
MIN
MAX
MIN
MAX
6-1/1
5-1-1/0
5-2/1
4-2-1/1
4-1-1-1/0
4-3/1
3-2-2/0
3-2-1-1/1
3-1-1-1-1/0
3-3-1/1
2-2-2-1/0
2-2-1-1-1/1
2-1-1-1-1-1/0
Algoritm:
Minimax cu investigare exhaustiva
Minimax( S ) 1. pentru fiecare succesor Sj al lui S (obtinut printr-o mutare opj) executa val( Sj ) ← Minimax( Sj ) 2. aplica opj pentru care val( Sj ) este maxima sfarsit Minimax( S ) 1. daca S este nod final atunci intoarce scor( S ) 2. altfel 2.1 daca MAX muta in S atunci 2.1.1 pentru fiecare succesor Sj al lui S executa val( Sj ) ← Minimax( Sj ) 2.1.2
intoarce max( val( Sj ), ∀j )
2.2 altfel { MIN muta in S } 2.2.1 pentru fiecare succesor Sj al lui S executa val( Sj ) ← Minimax( Sj ) 2.2.2
intoarce min( val( Sj ), ∀j )
3.2 Minimax pentru spatii de cautare investigate pana la o adancime n
Principiu Minimax Algoritmul Minimax pana la o adancime n nivel(S) O functie euristica de evaluare a unui nod eval(S)
Algoritm:
Minimax cu adancime finita n
Minimax( S ) 1. pentru fiecare succesor Sj al lui S (obtinut printr-o mutare opj) executa val( Sj ) ← Minimax( Sj ) 2. aplica opj pentru care val( Sj ) este maxima sfarsit Minimax( S ) { intoarce o estimare a starii S } 0. daca S este nod final atunci intoarce scor( S ) 1. daca nivel( S ) = n atunci intoarce eval( S ) 2. altfel 2.1 daca MAX muta in S atunci 2.1.1 pentru fiecare succesor Sj al lui S executa val( Sj ) ← Minimax( Sj ) 2.1.2 intoarce max( val( Sj ), ∀j ) 2.2 altfel { MIN muta in S } 2.2.1 pentru fiecare succesor Sj al lui S executa val( Sj ) ← Minimax( Sj ) 2.2.2 intoarce min( val( Sj ), ∀j ) sfarsit
Exemplu de functie de evaluare Jocul de Tic‑Tac‑Toe (X si O) Functie de estimare euristica eval( S ) - conflictul existent in starea S. eval( S ) = numarul total posibil de linii castigatoare ale lui MAX in starea S - numarul total posibil de linii castigatoare ale lui MIN in starea S. Daca S este o stare din care MAX poate face o miacare cu care castiga, atunci eval( S ) = ∞ (o valoare foarte mare) Daca S este o stare din care MIN poate castiga cu o singura mutare, atunci eval( S ) = -∞ (o valoare foarte mica).
eval(S) in Tic-Tac-Toe
X
X are 6 linii castigatoare posibile
O are 5 linii castigatoare posibile
O
eval( S ) = 6 - 5 = 1
3.3 Algoritmul taierii alfa‑beta
Este posibil sa se obtină decizia corecta a algoritmului Minimax fara a mai inspecta toate nodurile din spatiului de cautare pana la un anumit nivel. Procesul de eliminare a unei ramuri din arborele de cautare se numeste taierea arborelui de cautare (pruning).
Algoritmul taierii alfa‑beta
Fie α cea mai buna valoare (cea mai mare) gasita pentru MAX si β cea mai buna valoare (cea mai mica) gasita pentru MIN. Algoritmul alfa‑beta actualizeaza α si β pe parcursul parcurgerii arborelui si elimina investigarile subarborilor pentru care α sau β sunt mai proaste. Terminarea cautarii (taierea unei ramuri) se face dupa doua reguli:
Cautarea se opreste sub orice nod MIN cu o valoare β mai mica sau egala cu valoarea α a oricaruia dintre nodurile MAX predecesoare nodului MIN in cauza. Cautarea se opreste sub orice nod MAX cu o valoare α mai mare sau egala cu valoarea β a oricaruia dintre nodurile MIN predecesoare nodului MAX in cauza.
Tăierea alfa-beta a spaţiului de căutare
MAX
A/3
MIN
MAX
C/≤2
B/3
E/3
F / 12
G/8
H/2
I/4
D/2
J/6
K / 14
L/5
M/2
Algoritm: Alfa-beta MAX(S, α, β) { intoarce valoarea maxima a unei stari. } 0. daca S este nod final atunci intoarce scor( S ) 1. daca nivel( S ) = n atunci intoarce eval( S ) 2. altfel 2.1 pentru fiecare succesor Sj al lui S executa 2.1.1 α ← max(α, MIN(Sj, α, β)) 2.1.2 daca α ≥ β atunci intoarce β 2.2 intoarce α sfarsit MIN(S, α, β) { intoarce valoarea minima a unei stari. } 0. daca S este nod final atunci intoarce scor( S ) 1. daca nivel( S ) = n atunci intoarce eval( S ) 2. altfel 2.1 pentru fiecare succesor Sj al lui S executa 2.1.1 β ← min(β, MAX(Sj, α, β)) 2.1.2 daca β ≤ α atunci intoarce α 2.2 intoarce β sfarsit
3.4 Jocuri cu elemente de sansa
Jucatorul nu cunoaste miscarile legale ale oponentului 3 tipuri de noduri: MAX MIN Sansa (chance nodes)
• 36 rez pt 2 zaruri • 21 noduri distincte • Zaruri egale - > 1/36 • Zaruri diferite -> 1/18
Valoarea estimata pt noduri sansa • SumaSj suc S[ P(Sj)*Minimax(Sj)] •
• Functia de evaluare
Noduri de decizie
MAX Zar MIN
1/36
1/18
Noduri sansa
Zar MAX
1/36
1/18
43
Adina Magda Florea http://turing.cs.pub.ro/ia_06
Curs nr. 3 Strategii de rezolvare a problemelor
Problema satisfacerii restrictiilor Strategii de cautare in jocuri
1. Problema satisfacerii restrictiilor {X1,...,X n }
R j ⊂ Di1 ×...× Di j
{D1,...,D n }
{R 1,...,R k }
Gradul unei variabile Aritatea unei restrictii Gradul problemei Aritatea problemei
Xi1,...,X i j {(X1 , x j ),...,(X n , x j )} 1
n
2.1 Instante ale CSP Determinarea unei solutii sau a tuturor solutiilor CSP totala CSP partiala CSP binara – graf de restrictii CSP – problema de cautare, in NP Sub-clase de probleme cu timp polinomial Reducerea timpului (reducerea sp. de cautare)
Algoritm: Backtracking nerecursiv 1. Initializeaza FRONTiERA cu {Si} /* Si este starea initiala */ 2. daca FRONTIERA = { } atunci intoarce INSUCCES /* nu exista solutie /* 3. Fie S prima stare din FRONTIERA 4. daca toate starile succesoare ale lui S au fost deja generate atunci 4.1.Elimina S din FRONTIERA 4.2.repeta de la 2 5. altfel 5.1.Genereaza S', noua stare succesoare a lui S 5.2.Introduce S' la începutul listei FRONTIERA 5.3.Stabileste legatura S’→ S 5.4.Marcheaza în S faptul cã starea succesoare S' a fost generata 5.5.daca S' este stare finala atunci 5.5.1. Afiseaza calea spre solutie urmarind legaturile S’→ S .. 5.5.2. întoarce SUCCES /* s-a gasit o solutie */ 5.6.repeta de la 2 sfarsit.
2.2 Notatii
X1, …, XN variabilele problemei, N fiind numarul de variabile ale problemei, U - intreg care reprezinta indicele variabilei curent selectate pentru a i se atribui o valoare F - vector indexat dupa indicii variabilelor, in care sunt memorate selectiile de valori facute de la prima variabila si pana la variabila curenta
adevarat daca exista restrictia R U1 U 2 (F[U1 ], F[U 2 ]) Relatie (U1 , F[U1 ], U 2 , F[U 2 ]) = R U1 U 2 ⊂ D U 1 × D U 2 fals in caz contrar
Algoritm:
Backtracking recursiv
BKT (U, F) pentru fiecare valoare V a lui XU executa 1. F[U] ← V 2. daca Verifica (U,F) = adevarat atunci 2.1. daca U < N atunci BKT(U+1, F) 2.2. altfel 2.2.1. Afiseaza valorile din vectorul F /* F reprezinta solutia problemei */ 2.2.2. intrerupe ciclul sfarsit.
Verifica (U,F) 1. test ← adevarat 2. I ← U - 1 3. cit timp I > 0 executa 3.1. test ← Relatie(I, F[I], U, F[U]) 3.2. I ← I - 1 3.3. daca test = fals atunci intrerupe ciclul 4. intoarce test sfarsit.
2.3 Imbunatatirea performantelor BKT Algoritmi de imbunatatire a consistentei reprezentarii
Consistenta locala a arcelor sau a cailor in graful de restrictii
Algoritmi hibrizi
Imbunatatesc performantele rezolvarii prin reducerea numarului de teste. Tehnici prospective: - Algoritmul de cautare cu predictie completa - Algoritmul de cautare cu predictie partiala - Algoritmul de cautare cu verificare predictiva Tehnici retrospective: - Algoritmul de backtracking cu salt - Algoritmul de backtracking cu marcare - Algoritmul de backtracking cu multime conflictuala
Utilizarea euristicilor
Algoritmi de imbunatatire a consistentei reprezentarii
Propagarea restrictiilor D X1 = D X2 = D X3 = {a, b,c}
X 1 R = {(a,b),(b,c)} 12
R 13= {(a,c),(c,b)}
X2
X1
R 12= {(a,b)}
R 13= {(a,c)} X3 (a)
X2
R 23= {b,c)} X3 (b)
2.4 Propagarea locala a restrictiilor
Combinatia de valori x si y pentru variabilele Xi si Xj este permisa de restrictia explicita Rij(x,y).
Un arc (Xi, Xj) intr-un graf de restrictii orientat se numeste arc-consistent daca si numai daca pentru orice valoare x ∈ Di, domeniul variabilei Xi, exista o valoare y ∈ Dj, domeniul variabilei Xj, astfel incat Rij(x,y). Graf de restrictii orientat arc-consistent
Algoritm: AC-3: Realizarea arc-consistentei pentru un graf de restrictii. 1.
Creeaza o coada Q ← { (Xi, Xj) | (Xi, Xj) ∈ Multime arce, i≠j}
2.
cat timp Q nu este vida executa 2.1. Elimina din Q un arc (Xk, Xm) 2.2.
Verifica(Xk, Xm)
2.3.
daca subprogramul Verifica a facut schimbari in domeniul variabilei Xk
atunci Q ← Q ∪ { (Xi, Xk) | (Xi, Xk)∈Multime arce, i≠k,m} sfarsit. Verifica (Xk, Xm) pentru fiecare x ∈ Dk executa 1.
daca nu exista nici o valoare y ∈ Dm astfel incat Rkm(x,y) atunci elimina x din Dk
Cale-consistenta
O cale de lungime m prin nodurile i0,…,im ale unui graf de restrictii orientat se numeste m-caleconsistenta daca si numai daca pentru orice valoare x ∈ Di0, domeniul variabilei i0 si o valoare y ∈ Djm, domeniul variabilei im, pentru care Ri0im(x,y), exista o secventa de valori z1∈ Di1 … zm-1 ∈ Dim-1 astfel incat Ri0i1(x,z1), …, Rim-1im(zm-1,y) Graf de restrictii orientat m-arc-consistent Graf minim de restrictii n-cale-consistenta Comentarii
Complexitate
N - numarul de variabile a - cardinalitatea maxima a domeniilor de valori ale variabilelor e - numarul de restrictii. Algoritmului de realizare a arc-consistentei - AC-3: complexitate timp este O(e*a3); complexitate spatiu: O(e+N*a) S-a gasit si un algoritm de complexitate timp O(e*a2) – AC-4 Algoritmul de realizare a 2-cale-consistentei - PC-4: complexitatea timp O(N3*a3)
2.5 CSP fara bkt - conditii
Graf de restrictii ordonat Latimea unui nod Latimea unei ordonari a nodurilor Latimea unui graf de restrictii RAC
A
B RCB
C
Niv 3 C Niv 2 A Niv 1 B
A C B
B A C
Teoreme
Daca un graf de restrictii arc-consistent are latimea egala cu unu (i.e. este un arbore), atunci problema asociata grafului admite o solutie fara backtracking. Daca un graf de restrictii 2-cale-consistent are latimea egala cu doi, atunci problema asociata grafului admite o solutie fara backtracking.
d-consistenta
Fiind data o ordonare d a variabilelor unui graf de restrictii R, graful R este d-arc-consistent daca toate arcele avand directia d sint arcconsistente. Fie un graf de restrictii R, avind ordonarea variabilelor d cu latimea egala cu unu. Daca R este d-arc-consistent atunci cautarea dupa directia d este fara backtracking.
d-consistenta Algoritm: Realizarea d-arc-consistentei unui graf de restrictii cu ordonarea variabilelor (X1,…,XN) pentru I ← N la 1 executa 1. pentru fiecare arc (Xj, Xi) cu j < i executa 1.1. Verifica(Xj, Xi) sfarsit.
Complexitatea timp: O(e*a2)
2.6 Tehnici prospective
Conventii Notatii: U, N, F (F[U]), T (T[U] … XU), TNOU adevarat daca R U1 U 2 (L1 , L 2 ) Relatie(U1, L1, U2, L2) = în caz contrar fals
Verifica_Inainte Verifica_Viitoare Predictie completa Predictie partiala Verificare predictiva
Algoritm:
Backtracking cu predictie completa
Predictie(U, F, T) pentru fiecare element L din T[U] executa 1. F[U] ← L 2. daca U < N atunci //verifica consistenta atribuirii 2.1 TNOU ← Verifica_Inainte (U, F[U], T) 2.2 daca TNOU ≠ LINIE_VIDA atunci TNOU ← Verifica _Viitoare (U, TNOU) 2.3 daca TNOU ≠ LINIE_VIDA atunci Predictie (U+1, F, TNOU) 3. altfel afiseaza atribuirile din F sfarsit
Verifica_Inainte (U, L, T) 1. TNOU ← tabela vida 2. pentru U2 ← U+1 pana la N executa 2.1 pentru fiecare element L2 din T[U2] executa 2.1.1 daca Relatie(U, L, U2, L2) = adevarat atunci introduce L2 in TNOU[U2] 2.2 daca TNOU[U2] este vida atunci intoarce LINIE_VIDA 3. intoarce TNOU sfarsit
Verifica_Viitoare (U, TNOU) daca U+1 < N atunci 1. pentru U1 ← U+1 pana la N executa 1.1 pentru fiecare element L1 din TNOU[U1] executa 1.1.1 pentru U2 ← U+1 pana la N, U2≠U1 executa i. pentru fiecare element L2 din TNOU[U2] executa - daca Relatie (U1, L1, U2, L2) = adevarat atunci intrerupe ciclul //dupa L2 ii. daca nu s-a gasit o valoare consistenta pentru U2 atunci - elimina L1 din TNOU[U1] - intrerupe ciclul // dupa U2 1.2 daca TNOU[U1] este vida atunci intoarce LINIE_VIDA 2. intoarce TNOU sfarsit
BKT cu predictie partiala
Se modifica Verifica_Viitoare pasii marcati cu rosu
Verifica_Viitoare (U, TNOU) daca U+1 < N atunci 1. pentru U1 ← U+1 pana la N - 1 executa 1.1 pentru fiecare element L1 din TNOU[U1] executa 1.1.1 pentru U2 ← U1+1 pana la N executa i. pentru fiecare element L2 din TNOU[U2] executa - daca Relatie (U1, L1, U2, L2) = adevarat atunci intrerupe ciclul //dupa L2 ii. daca nu s-a gasit o valoare consistenta pentru U2 atunci - elimina L1 din TNOU[U1] - intrerupe ciclul // dupa U2 1.2 daca TNOU[U1] este vida atunci intoarce LINIE_VIDA 2. intoarce TNOU sfarsit
BKT cu verificare predictiva
Se elimina apelul Verifica_Viitoare(U, TNOU) in subprogramul Predictie
Algoritm:
Backtracking cu verificare predictiva
Predictie(U, F, T) pentru fiecare element L din T[U] executa 1. F[U] ← L 2. daca U < N atunci //verifica consistenta atribuirii 2.1 TNOU ← Verifica_Inainte (U, F[U], T) 2.2 daca TNOU ≠ LINIE_VIDA atunci TNOU ← Verifica _Viitoare (U, TNOU) 2.2 daca TNOU ≠ LINIE_VIDA atunci Predictie (U+1, F, TNOU) 3. altfel afiseaza atribuirile din F sfarsit
2.7 Tehnici retrospective
Backtracking cu salt D ={escarpeni, pantofi de tenis} Pf
Pantofi {(escarpeni, albã)} D ={verde, albã}
Cãmãºi
(pantofi de tens, gris) (pantofi tenis, alba) {(escarpeni, gri), (pantofi de tenis, jeans)} Pantaloni
D ={gri, bleu, jeans}
C
Pt
{(verde, gri), (verde, jeans), (albã, jeans), (albã, bleu)}
Pantofi Pantaloni Cãmãºi
escarpeni jeans
1 bleu verde
pantofi de tenis
gri 2
(a)
1
jeans
albã verde
bleu
gris 1
albã
(b) verde
alba
verde
alba
Algoritm: Backtracking cu salt BacktrackingCuSalt(U, F, Nivel) /* NrBlocari, NivelVec, I, test, Nivel1 – var locale */
1. NrBlocari ← 0, I ← 0, Nivel ← U 2 pentru fiecare element V a lui XU executa 2.1 F[U] ← V 2.2 test, NivelVec[I] ← Verifica (U, F) 2.3 daca test = adevarat atunci 2.3.1 daca U < N atunci i. BacktrackingCuSalt (U+1, F, Nivel1) ii. daca Nivel1 < U atunci salt la sfarsit 2.3.2 altfel afiseaza valorile vectorului F // solutia 2.4 altfel NrBlocari ← NrBlocari + 1 2.5 I ← I + 1 3. daca NrBlocari = numar valori ale lui X[U] si toate elementele din NivelVec sunt egale atunci Nivel ← NivelVec[1] sfarsit
Verifica (U, F) 1. test ← adevarat 2. I ← U-1 3. cat timp I>0 executa 3.1 test ← Relatie(I, F[I], U, F[U]) 3.2 daca test = fals atunci intrerupe ciclul 3.3 I ← I –1 4. NivelAflat ← I 5. intoarce test, NivelAflat sfarsit
2.8 Euristici
Ordonarea variabilelor Ordonarea valorilor Ordonarea testelor
3. Strategii de cautare in jocuri
Jocuri ce implică doi adversari
jucator adversar
Jocuri in care spatiul de cautare poate fi investigat exhaustiv Jocuri in care spatiul de cautare nu poate fi investigat complet deoarece este prea mare.
3.1 Minimax pentru spatii de cautare investigate exhaustiv
Jucator – MAX Adversar – MIN Principiu Minimax Etichetez fiecare nivel din AJ cu MAX (jucator) si MIN (adversar) Etichetez frunzele cu scorul jucatorului Parcurg AJ
daca nodul parinte este MAX atunci i se atribuie valoarea maxima a succesorilor sai; daca nodul parinte este MIN atunci i se atribuie valoarea minima a succesorilor sai.
Spatiu de cautare Minimax (AJ)
MAX
A/3
MIN
MAX
B/3
E/3
F / 12
C/2
G/8
H/2
I/4
D/2
J/6
K / 14
L/5
M/2
Spatiu de cautare Minimax (AJ) Nim cu 7 bete MIN
7/1
MAX
MIN
MAX
MIN
MAX
6-1/1
5-1-1/0
5-2/1
4-2-1/1
4-1-1-1/0
4-3/1
3-2-2/0
3-2-1-1/1
3-1-1-1-1/0
3-3-1/1
2-2-2-1/0
2-2-1-1-1/1
2-1-1-1-1-1/0
Algoritm:
Minimax cu investigare exhaustiva
Minimax( S ) 1. pentru fiecare succesor Sj al lui S (obtinut printr-o mutare opj) executa val( Sj ) ← Minimax( Sj ) 2. aplica opj pentru care val( Sj ) este maxima sfarsit Minimax( S ) 1. daca S este nod final atunci intoarce scor( S ) 2. altfel 2.1 daca MAX muta in S atunci 2.1.1 pentru fiecare succesor Sj al lui S executa val( Sj ) ← Minimax( Sj ) 2.1.2
intoarce max( val( Sj ), ∀j )
2.2 altfel { MIN muta in S } 2.2.1 pentru fiecare succesor Sj al lui S executa val( Sj ) ← Minimax( Sj ) 2.2.2
intoarce min( val( Sj ), ∀j )
3.2 Minimax pentru spatii de cautare investigate pana la o adancime n
Principiu Minimax Algoritmul Minimax pana la o adancime n nivel(S) O functie euristica de evaluare a unui nod eval(S)
Algoritm:
Minimax cu adancime finita n
Minimax( S ) 1. pentru fiecare succesor Sj al lui S (obtinut printr-o mutare opj) executa val( Sj ) ← Minimax( Sj ) 2. aplica opj pentru care val( Sj ) este maxima sfarsit Minimax( S ) { intoarce o estimare a starii S } 0. daca S este nod final atunci intoarce scor( S ) 1. daca nivel( S ) = n atunci intoarce eval( S ) 2. altfel 2.1 daca MAX muta in S atunci 2.1.1 pentru fiecare succesor Sj al lui S executa val( Sj ) ← Minimax( Sj ) 2.1.2 intoarce max( val( Sj ), ∀j ) 2.2 altfel { MIN muta in S } 2.2.1 pentru fiecare succesor Sj al lui S executa val( Sj ) ← Minimax( Sj ) 2.2.2 intoarce min( val( Sj ), ∀j ) sfarsit
Exemplu de functie de evaluare Jocul de Tic‑Tac‑Toe (X si O) Functie de estimare euristica eval( S ) - conflictul existent in starea S. eval( S ) = numarul total posibil de linii castigatoare ale lui MAX in starea S - numarul total posibil de linii castigatoare ale lui MIN in starea S. Daca S este o stare din care MAX poate face o miacare cu care castiga, atunci eval( S ) = ∞ (o valoare foarte mare) Daca S este o stare din care MIN poate castiga cu o singura mutare, atunci eval( S ) = -∞ (o valoare foarte mica).
eval(S) in Tic-Tac-Toe
X
X are 6 linii castigatoare posibile
O are 5 linii castigatoare posibile
O
eval( S ) = 6 - 5 = 1
3.3 Algoritmul taierii alfa‑beta
Este posibil sa se obtină decizia corecta a algoritmului Minimax fara a mai inspecta toate nodurile din spatiului de cautare pana la un anumit nivel. Procesul de eliminare a unei ramuri din arborele de cautare se numeste taierea arborelui de cautare (pruning).
Algoritmul taierii alfa‑beta
Fie α cea mai buna valoare (cea mai mare) gasita pentru MAX si β cea mai buna valoare (cea mai mica) gasita pentru MIN. Algoritmul alfa‑beta actualizeaza α si β pe parcursul parcurgerii arborelui si elimina investigarile subarborilor pentru care α sau β sunt mai proaste. Terminarea cautarii (taierea unei ramuri) se face dupa doua reguli:
Cautarea se opreste sub orice nod MIN cu o valoare β mai mica sau egala cu valoarea α a oricaruia dintre nodurile MAX predecesoare nodului MIN in cauza. Cautarea se opreste sub orice nod MAX cu o valoare α mai mare sau egala cu valoarea β a oricaruia dintre nodurile MIN predecesoare nodului MAX in cauza.
Tăierea alfa-beta a spaţiului de căutare
MAX
A/3
MIN
MAX
C/≤2
B/3
E/3
F / 12
G/8
H/2
I/4
D/2
J/6
K / 14
L/5
M/2
Algoritm: Alfa-beta MAX(S, α, β) { intoarce valoarea maxima a unei stari. } 0. daca S este nod final atunci intoarce scor( S ) 1. daca nivel( S ) = n atunci intoarce eval( S ) 2. altfel 2.1 pentru fiecare succesor Sj al lui S executa 2.1.1 α ← max(α, MIN(Sj, α, β)) 2.1.2 daca α ≥ β atunci intoarce β 2.2 intoarce α sfarsit MIN(S, α, β) { intoarce valoarea minima a unei stari. } 0. daca S este nod final atunci intoarce scor( S ) 1. daca nivel( S ) = n atunci intoarce eval( S ) 2. altfel 2.1 pentru fiecare succesor Sj al lui S executa 2.1.1 β ← min(β, MAX(Sj, α, β)) 2.1.2 daca β ≤ α atunci intoarce α 2.2 intoarce β sfarsit
3.4 Jocuri cu elemente de sansa
Jucatorul nu cunoaste miscarile legale ale oponentului 3 tipuri de noduri: MAX MIN Sansa (chance nodes)
• 36 rez pt 2 zaruri • 21 noduri distincte • Zaruri egale - > 1/36 • Zaruri diferite -> 1/18
Valoarea estimata pt noduri sansa • SumaSj suc S[ P(Sj)*Minimax(Sj)] •
• Functia de evaluare
Noduri de decizie
MAX Zar MIN
1/36
1/18
Noduri sansa
Zar MAX
1/36
1/18
43
