Algoritmica - Curs 13 1

Curs 13:

Tehnica cutrii cu revenire(Backtracking)

Algoritmica - Curs 13 2

Structura

Ce este tehnica cutrii cu revenire ?

Structura general a algoritmilor proiectai folosind aceasttehnic

Aplicaii: Generarea permutrilor Problema plasrii reginelor pe tabla de ah Colorarea hrilor Gsirea traseelor care unesc dou locaii Problema labirintului

Algoritmica - Curs 13 3

Ce este tehnica cutrii cu revenire?

Este o strategie de cutare sistematic n spaiul soluiilor uneiprobleme

Se utilizeaz n special pentru rezolvarea problemelor a crorcerin este de a determina configuraii care satisfac anumiterestricii (probleme de satisfacere a restriciilor). Majoritateaproblemelor ce pot fi rezolvate folosind tehnica cutrii cu revenirese ncadreaz n urmtorul ablon:

S se gseasc o submulime S a produsului cartezian A1 x A2 x x An (Ak mulimi finite) avnd proprietatea c fiecare element s=(s1,s2,,sn) satisface anumite restrictii

Exemplu: generarea tuturor permutrilor mulimii {1,2,,n}Ak = {1,2,,n} pentru fiecare k=1..nsi sj pentru orice ij (restricia: componente distincte)

Algoritmica - Curs 13 4

Ce este tehnica cutrii cu revenire?Ideea de baza: Soluiile sunt construite n manier incremental prin gsirea

succesiv a valorilor potrivite pentru componente (la fiecare etapse completeaz o component obinndu-se o soluie parial)

Fiecare soluie parial este evaluat cu scopul de a stabili daceste valid (promitoare). O soluie parial valid poate conduce la o soluie final pe cnd una invalid ncalc restriciile pariale, nsemnnd c nu va conduce niciodat la o soluie care ssatisfac toate restriciile problemei

Dac nici una dintre valorile corespunztoare unei componente nu conduce la o soluie parial valid atunci se revine la componentaanterioar i se ncearc alt valoare pentru aceasta.

Algoritmica - Curs 13 5

Ce este tehnica cutrii cu revenire?Ideea de baz:

Principiul tehnicii poate fi vizualizat folosind un arbore de cutarecare ilustreaz parcurgerea spaiului soluiilor:

Rdcina arborelui corespunde strii iniiale (nainte de a ncepecompletarea componentelor)

Un nod intern corespunde unei soluii pariale valide

Un nod extern (frunz) corespunde fie unei soluii pariale invalide fie unei soluii finale

Algoritmica - Curs 13 6

Ce este tehnica cutrii cu revenire?Exemplu: arborele de parcurgere a spaiului soluiilor n cazul

problemei de generare a permutrilor (n=3)

(*,*,*)

(1,*,*) (2,*,*) (3,*,*)

(1,1,*) (1,2,*) (1,3,*)

(1,2,3) (1,3,2)

(2,1,*) (2,2,*) (2,3,*) (3,1,*) (3,2,*) (3,3,*)

(2,1,3) (2,3,1) (3,1,2) (3,2,1)

Algoritmica - Curs 13 7

Structura general a algoritmului

Etape n proiectarea algoritmului:

1. Se alege modul de reprezentare a soluiilor

2. Se identific spaiul de cutare i se stabilesc mulimile A1,,Ani ordinea n care acestea sunt parcurse

3. Din restriciile problemei se deduc condiiile pe care trebuie sle satisfac soluiile pariale pentru a fi valide. Aceste condiii sunt denumite condiii de continuare.

4. Se stabilete criteriul n baza cruia se decide dac o soluieparial este soluie final

Algoritmica - Curs 13 8

Structura general a algoritmului

Exemplu: generarea permutrilor

1. Reprezentarea soluiei: fiecare permutare este un vector s=(s1,s2,sn) care satisface sisj pentru orice ij

2. Mulimile A1,,An : {1,2,,n}. Fiecare mulime este parcursn ordinea natural a elementelor (de la 1 la n)

3. Condiii de continuare: o soluie parial (s1,s2,,sk) trebuie ssatisfac sksi pentru orice i

Algoritmica - Curs 13 9

Structura general a algoritmului

Notaii:

(s1,s2,,sk) soluie parial

k indice n s

Ak = {ak1,,akmk}

mk=card{Ak}

ik - indice in Ak

10

Structura general a algoritmului

Backtracking(A1, A2, , An)k 1; ik 0WHILE k>0 DOik ik+1 v FalseWHILE v=False AND ik

Algoritmica - Curs 13 11

Structura general a algoritmului

Varianta recursiv:

Presupunem ca A1,,An is sunt variabile globale

Fie k componenta care urmeaz a fi completat

Algoritmul se apeleaz prinBT_rec(1)

BT_rec(k)IF (s1,,sk-1) este soluie

THEN se prelucreaz soluiaELSE FOR j 1,mk DO

sk akjIF (s1,sk) este validTHEN BT_rec(k+1) ENDIF

ENDFOR ENDIF

Se ncearc fiecare valoareposibil

Se completeaz urmtoareacomponent

Algoritmica - Curs 13 12

Aplicaie 1: generarea permutrilorBacktracking(A1, A2, , An)

k 1; ik 0WHILE k>0 DOik ik+1 v FalseWHILE v=False AND ik0 DOs[k] s[k]+1v FalseWHILE v=False AND s[k]

Algoritmica - Curs 13 13

Aplicaie 1: generarea permutrilor

Funcie care verific dac o soluie parial este valid

valid(s[1..k])FOR i 1,k-1 DO

IF s[k]=s[i] THEN RETURN FALSE

ENDIFENDFORRETURN TRUE

Varianta recursiva:

perm_rec(k)IF k=n+1 THEN WRITE s[1..n]ELSE

FOR i 1,n DOs[k] iIF valid(s[1..k])=True

THEN perm_rec(k+1)ENDIF

ENDFORENDIF

Algoritmica - Curs 13 14

Aplicaie 2: problema reginelorS se determine toate posibilitile de a plasa n regine pe o tabl de

ah de dimensiune nxn astfel nct acestea s nu se atacereciproc:

- fiecare linie conine exact o regin- fiecare coloan conine exact o regin- fiecare diagonal conine cel mult o regina

Obs. Este o problem clasic propus de ctre Max Bezzel (1850) i studiat de ctre mai muli matematicieni ai vremii (Gauss, Cantor)

Exemplu: dac n

Algoritmica - Curs 13 15

Aplicaie 2: problema reginelor

1. Reprezentarea soluiei: vom considera c regina k estentotdeauna plasat pe linia k. Astfel pentru fiecare regineste suficient s se identifice coloana pe care va fi plasat. Soluia va fi astfel reprezentat printr-un tablou (s1,,sn) undesk = indicele coloanei pe care se plaseaz regina k

2. Mulimile A1,,An : {1,2,,n}. Fiecare mulime va fiprelucrat n ordinea natural a elementelor (de la 1 la n)

3. Condiii de continuare: o soluie parial (s1,s2,,sk) trebuies satisfac restriciile problemei (nu mai mult de o regin pefiecare linie, coloan sau diagonal)

4. Criteriu pentru a decide dac o soluie parial este final:k = n (toate reginele au fost plasate)

Algoritmica - Curs 13 16

Aplicaie 2: problema reginelorCondiii de continuare: Fie (s1,s2,,sk) o soluie parial. Aceasta este

valid dac satisface:

Reginele se afl pe linii diferite condiia este implicit satisfacutdatorit modului de reprezentare utilizat (regina i este ntotdeaunaplasat pe linia i)

Reginele se afla pe coloane diferite:

sisj pentru orice ij

(este suficient s se verifice ca sksi pentru orice 1

Algoritmica - Curs 13 17

Aplicaie 2: problema reginelorObs:

Dou regine i i j se afl peaceeai diagonal dac

i-si=j-sj i-j = si-sjsau

i+si=j+sj i-j= sj-siAceasta nseamn c

|i-j|=|si-sj|

i-j=0

i-j=-1

i-j=-(n-2)i-j=1

i-j=n-2

i+j=n+1

i+j=n

i+j=3

i+j=2n-1

i+j=n+2

Algoritmica - Curs 13 18

Aplicaie 2: problema reginelor

Validare(s[1..k])

FOR i 1,k-1 DO

IF s[k]=s[i] OR |i-k|=|s[i]-s[k]| THEN RETURN False

ENDIF

ENDFOR

RETURN True

Apel: regine(1)

Algoritm:

regine(k)

IF k=n+1 THEN WRITE s[1..n]

ELSE

FOR i 1,n DO

s[k] i

IF Validare(s[1..k])=True

THEN regine(k+1)

ENDIF

ENDFOR

ENDIF

Algoritmica - Curs 13 19

Aplicaie 3: colorarea hrilorProblema: Considerm o hart geografic care conine n ri.

Avnd la dispoziie 4

Algoritmica - Curs 13 20

Aplicaie 3: colorarea hrilorProblema: : Considerm o hart geografic care conine n ri.

Avnd la dispoziie 4

Algoritmica - Curs 13 21

Aplicaie 3: colorarea hrilor1. Reprezentarea soluiei

S=(s1,,sn) unde sk culoarea asociat rii k

2. Mulimile A1,,An : {1,2,,m}. Fiecare mulime va fiprelucrat n ordinea natural a elementelor (de la 1 la m)

3. Condiii de continuare: o soluie parial (s1,s2,,sk) trebuies satisfac sisj pentru toate perechile (i,j) pentru care N(i,j)=1

Pentru fiecare k este suficient s se verifice ca sksj pentrutoate valorile i in {1,2,,k-1} satisfacnd N(i,k)=1

4. Criteriu pentru a decide daca o solutie partiala este solutiefinala: k = n (toate rile au fost colorate)

Algoritmica - Curs 13 22

Aplicaie 3: colorarea hrilorAlgoritm recursiv

Colorare(k)IF k=n+1 THEN WRITE s[1..n]ELSE

FOR j 1,m DOs[k] jIF valid(s[1..k])=True

THEN Colorare(k+1)ENDIF

ENDFORENDIF

Algoritm de validare

valid(s[1..k])FOR i 1,k-1 DO

IF N[i,k]=1 AND s[i]=s[k]THEN RETURN FalseENDIF

ENDFORRETURN True

Apel: Colorare(1)

Algoritmica - Curs 13 23

Aplicaie 4: gsirea traseelorConsiderm un set de n orae i o reea de drumuri care le

conecteaz. S se determine toate traseele care conecteazdou orae date (un traseu nu poate trece de dou ori prinacelasi ora).

Arad

Timisoara

Satu Mare

Brasov

Iasi

Bucuresti

Constanta

Orae:

1.Arad

2.Brasov

3.Bucuresti

4.Constanta

5.Iasi

6.Satu-Mare

7.Timisoara

Trasee de la Arad la Constanta

1->7->3->4

1->2->3->4

1->6->5->3->4

1->6->5->2->3->4

Algoritmica - Curs 13 24

Aplicaie 4: gsirea traseelorFormalizarea problemei: Reeaua de osele este specificat prin

matricea C: 0 nu exist osea direct de la oraul i la oraul j

C(i,j) = 1 exist osea direct de la oraul i la oraul j

S se gseasc toate traseele S=(s1,,sm) - unde sk n {1,,n} specific oraul vizitat la etapa k - astfel nct

s1 este oraul surssm este oraul destinaiesisj pentru orice i j (un ora este vizitat o singur dat)C(sk,sk+1)=1 (exist osea direct ntre oraele vizitate la momente

consecutive de timp)

Algoritmica - Curs 13 25

Aplicaie 4: gsirea traseelor1. Reprezentarea soluiei

S=(s1,,sm) cu sk reprezentnd oraul vizitat la etapa k(m = numrul de etape; nu este cunoscut de la nceput)2. Mulimile A1,,An : {1,2,,n}. Fiecare mulime va fi

prelucrat n ordinea natural a elementelor (de la 1 la n)

3. Condiii de continuare: o soluie parial (s1,s2,,sk) trebuies satisfac:

sksj pentru orice j n {1,2,,k-1} (oraele sunt distincte)C(sk-1,sk)=1 (se poate trece direct de la sk-1la sk)

4. Criteriul pentru a decide dac o soluie parial este soluiefinal:

sk = ora destinaie

Algoritmica - Curs 13 26

Aplicaie 4: gsirea traseelorAlgoritm recursiv

trasee(k)IF s[k-1]=oras destinatie THEN

WRITE s[1..k-1]ELSE

FOR j 1,n DOs[k] jIF valid(s[1..k])=TrueTHEN trasee(k+1)ENDIF

ENDFORENDIF

Algoritm de validare

valid(s[1..k])IF C[s[k-1],s[k]]=0 THEN

RETURN FalseENDIFFOR i 1,k-1 DO

IF s[i]=s[k]THEN RETURN False

ENDIFENDFORRETURN True

Apel: s[1] ora surstrasee(2)

Algoritmica - Curs 13 27

Aplicaie 5: problema labirintuluiProblema. Se consider un labirint definit pe o gril nxn. S se

gseasc toate traseele care pornesc din (1,1) i se termin n (nxn)

Obs. Doar celulele libere pot fi vizitate. Dintr-o celul (i,j) se poate trece n una dintre celulele vecine:

(i,j)(i,j-1) (i,j+1)

(i-1,j)

(i+1,j)

Obs: celulele de pe frontier au mai puinivecini

Algoritmica - Curs 13 28

Aplicaie 5: problema labirintuluiFormalizarea problemei. Labirintul este stocat ntr-o matrice nxn

0 celul liberM(i,j) =

1 celul ocupatS se gseasc S=(s1,,sm) cu sk n {1,,n}x{1,,n} indicii

corespunztori celulei vizitate la etapa k s1 este celula de start: (1,1) sm este celula destinaie: (n,n) sksq pentru orice k q (o celul este vizitat cel mult o

dat) M(sk)=0 (doar celulele libere pot fi vizitate) sk-1 si sk sunt celule vecine

Algoritmica - Curs 13 29

Aplicaie 5: problema labirintului1. Reprezentarea soluiei

S=(s1,,sn) cu sk reprezentnd indicii celulei vizitate la etapak

2. Mulimile A1,,An sunt submulimi ale mulimii{1,2,,n}x{1,2,,n}. Pentru fiecare celul (i,j) exist un set de 4 vecini: (i,j-1), (i,j+1), (i-1,j), (i+1,j)

3. Condiii de continuare: o soluie parial (s1,s2,,sk) trebuie ssatisfac:

sksq pentru orice q in {1,2,,k-1} M(sk)=0sk-1 i sk sunt celule vecine

4. Condiia ca o soluie parial (s1,,sk) s fie soluie final:sk = (n,n)

Algoritmica - Curs 13 30

Aplicatie 5: problema labirintuluilabirint(k)

IF s[k-1].i=n and s[k-1].j=n THEN WRITE s[1..k]

ELSE // se incearc toi vecinii

s[k].i s[k-1].i-1; s[k].j s[k-1].j

IF valid(s[1..k])=True THEN labirint (k+1) ENDIF

s[k].i s[k-1].i+1; s[k].j s[k-1].j

IF valid(s[1..k])=True THEN labirint (k+1) ENDIF

s[k].i s[k-1].i; s[k].j s[k-1].j-1

IF valid(s[1..k])=True THEN labirint (k+1) ENDIF

s[k].i s[k-1].i-1; s[k].j s[k-1].j+1

IF valid(s[1..k])=True THEN labirint (k+1) ENDIF

ENDIF

Obs:

s[k].i reprezintprima component a perechii de indici

s[k].j reprezint a doua component a perechii de indici

Algoritmica - Curs 13 31

Aplicaie 5: problema labirintuluivalid(s[1..k])

IF s[k].in OR s[k].jn // n afara grilei

THEN RETURN False

ENDIF

IF M[s[k].i,s[k].j]=1 THEN RETURN False ENDIF // celul ocupat

FOR q 1,k-1 DO // celul deja vizitat

IF s[k].i=s[q].i AND s[k].j=s[q].j THEN RETURN False ENDIF

ENDFOR

RETURN TrueApel algoritm labirint:

s[1].i:=1; s[1].j:=1

labirint(2)

Algoritmica - Curs 13 32

Curs urmtor: recapitulare

Tematica examen:

Algorirmi iterativi: proiectare i analiza complexitate Algoritmi recursivi: descriere i analiza complexitate Tehnici de reducere i divizare: descriere i analiza

complexitate Algoritmi de sortare:

algoritmi elementari (inserie, selecie, interschimbare) algoritmi eficieni (sortare prin interclasare, sortare rapid)

Cutare local optimala (greedy) Programare dinamic Cutare cu revenire (backtracking)

Slide Number 1StructuraCe este tehnica cutrii cu revenire?Ce este tehnica cutrii cu revenire?Ce este tehnica cutrii cu revenire?Ce este tehnica cutrii cu revenire?Structura general a algoritmuluiStructura general a algoritmuluiStructura general a algoritmuluiStructura general a algoritmuluiStructura general a algoritmuluiAplicaie 1: generarea permutrilorAplicaie 1: generarea permutrilorAplicaie 2: problema reginelorAplicaie 2: problema reginelorAplicaie 2: problema reginelorAplicaie 2: problema reginelorAplicaie 2: problema reginelorAplicaie 3: colorarea hrilorAplicaie 3: colorarea hrilorAplicaie 3: colorarea hrilorAplicaie 3: colorarea hrilorAplicaie 4: gsirea traseelorAplicaie 4: gsirea traseelorAplicaie 4: gsirea traseelorAplicaie 4: gsirea traseelorAplicaie 5: problema labirintuluiAplicaie 5: problema labirintuluiAplicaie 5: problema labirintuluiAplicatie 5: problema labirintuluiAplicaie 5: problema labirintuluiCurs urmtor: recapitulare