Metoda backtracking - varianta nerecursiva

METODA BACKTRACKING

Varianta nerecursiva

PREZENTARE GENERALA

În anumite aplicatii apar probleme în care se cere gasirea unor solutii de forma X=x₁x₂x_3. … x_n, unde x_i A_i,i = 1…n, în care x₁…x_n trebuie sa îndeplineasca conditii specifice.

O solutie este generarea tuturor combinatiilor posibile de valori si apoi sa le alegem doar pe cele convenabile. Considerând multimile A_i=, aceste combinatii s-ar putea construi astfel: pentru fiecare valoare posibila fixata pentru componenta x_i , vom alege toata valorile posibile pentru componenta x_i+1 si pentru fiecare astfel de valoare fixata pentru x_i+1 vom alege toate valorile posibile pentru componenta x_i+2 etc.

Rezolvând problema în acest mod, deci generând toate elementele produsului cartezian A₁xA₂x…A_n si verificând abia apoi daca fiecare combinatie este o solutie, eficienta este scazuta.

Astfel, daca de exemplu ne propunem sa generam toate cuvintele formate din literele a, b, c, asa încât fiecare litera sa apara o singura data , combinatiile posibile sunt în numar de 27, dintre care convin doar 6.

Tehnica Backtraking propune generarea solutiei prin completarea vectorului x în ordinea x₁, x₂, x₃…x_n si are la baza un principiu „de bun simt” : daca se constata ca având o combinatie partiala de forma v₁, v₂, …, v_k-1(unde v₁, …, v_k-1 sunt valori deja fixate ), daca alegem pentru x_k o valoare v_k si combinatia rezultata nu ne permite sa ajungem la o solutie, se renunta la aceasta valoare si se încearca o alta (din cele ne testate în aceasta etapa). Într-adevar, oricum am alege celelalte valori , daca una nu corespunde nu putem avea o solutie.

Pentru exemplul ales anterior se observa ca daca notam cuvântul cu x₁x₂x₃ combinatia aax₃ nu ne poate conduce la o solutie (literele trebuie sa fie distincte) si deci nu are sens sa mai încercam sa stabilim valori pentru x₃.

ALGORITMUL GENERAL AL METODEI BACKTRACKING

Pentru evitarea generarii combinatiilor neconvenabile se procedeaza astfel:

Presupunem ca s-au gasit valorile v₁v₂…v_k-1 pentru componentele x₁x₂…x_k-1 (au ramas de determinat valorile pentru x_k…x_n) . Ne ocupam în continuare de componenta x_k. Pasii urmati sunt:

1.Pentru început, pentru x_k nu s-a testat înca nici o valoare.

2.Se verifica daca exista valori ne testate pentru x_k.

a) În caz afirmativ, se trece la pasul 3

b) Altfel, se revine la componenta anterioara, x_k-1; se reia pasul 2 pentru k=k-1.

3. Se alege prima valoare v din cele netestate înca pentru x_k.

4. Se verifica daca aceasta combinatie partiala v₁v₂…v_k-1v ne poate conduce la un rezultat (daca sunt îndeplinite anumite conditii de continuare).

a) Daca valoarea aleasa este buna se trece la pasul 5.

b) Altfel, se ramâne pe aceeasi pozitie k si se reia pasul 2.

5. Se verifica daca s-a obtinut o solutie.

a) În caz afirmativ, se tipareste aceasta solutie si se ramâne la aceeasi componenta x_k, reluându-se pasul 2.

b) Altfel se reia algoritmul pentru urmatoarea componenta (se trece la pasul 1 pentru k=k+1

Algoritmul începe prin stabilirea unei valori pentru componenta x₁(k=1) si se încheie când pentru aceasta am testat toate valorile posibile si conform pasului 2b) ar trebui sa revenim la componenta anterioara, care în acest caz nu exista.

Pentru cuvintele formate din trei litere distincte din exemplul anterior, generarea solutiilor se face conform schemei alaturate.

Rezumând, metoda Backtracking se foloseste în rezolvarea problemelor care îndeplinesc conditiile:

solutia poate fi pusa sub forma unui vector S=x₁x₂…x_n, unde x_i A_i, unde i = 1, … , n;

multimile A_i sunt finite si ordonate (pentru a putea lua în considerare toate valorile posibile).

OBSERVATII :

În unele probleme n variaza de la o solutie la alta ;

Multimile A_i pot coincide

Metoda Backtracking ofera toate solutiile.

Înainte de a scrie programul care va obtine solutiile, trebuie sa stabilim unele detalii cu privire la:

Vectorul solutie : câte componente are, ce mentine fiecare componenta.

Multimea de valori posibile pentru fiecare componenta (sunt foarte importante limitele acestei multimi).

Conditii de continuare (conditiile ca o valoare x[k] sa fie acceptata).

Conditia ca ansamblul de valori generat sa fie solutie.

Pe baza acestor date vom scrie apoi functiile pe care le vom apela în algoritmul general al metodei, dat mai jos, care se poate aplica tuturor problemelor ce respecta conditiile mentionate anterior. Aceste proceduri si functii au o semnificatie comuna, prezentând însa particularitati în functie de fiecare problema in parte.

Astfel, se va nota cu x vectorul care va contine solutia x[k]=v va avea ca semnificatie faptul ca elementul al V-lea din multimea de valori posibile Ak a fost selectat pentru componenta xK.. Daca multimea Ak are m elemente, a1a2…am,pentru usurinta, ne vom referi la ele prin indicii lor 1, 2, …, m. Deci valorile posibile pentru o componenta vor fi 1, 2 , …, m, în aceasta ordine.

Initial când pentru o componenta nu am testat înca nimic, aceasta va avea valoarea 0 (un indice care nu exista). Aceasta operatie se va realiza în functia INIT care va avea ca parametru indicele k.

OBSERVATIE

De obicei, valorile posibile sunt chiar succesive si în acest caz se poate considera ca x[k]=v are semnificatia ca pentru componenta xk s-a ales chiar valoarea V. În acest caz initializarea trebuie facuta cu o valoare aflata imediat înaintea primei valori posibile. De exemplu daca valorile posibile ar fi 5, 6, 7. . . atunci initializarea se va face cu valoarea x[k]=4.

Functia EXISTA(k) verifica daca ultima valoare aleasa pentru componenta xk nu a atins limita maxima admisa(indicele de valoare maxima). Întrucât elementele sunt testate in ordine, acest lucru este echivalent cu a verifica daca mai avem valori netestate înca pentru aceasta componenta.

Functia CONT(k) verifica daca valoarea aleasa pentru x[k] îndeplineste conditiile de continuare, deci daca aceasta combinatie partiala v1v2…vk poate sa conduca la o solutie.

OBSERVATIE

La implementarea acestei functii, de obicei se porneste de la premisa ca se poate obtine o solutie si se identifica acele cazuri în care acest lucru nu este posibil.

Functia SOLUTIE(k) verifica daca s-a ajuns la o solutie finala.

Functia TIPAR(k) tipareste o solutie.

Algoritmul propus este :

OBSERVATIE

În situatiile în care operatiile realizate în procedurile enuntate sunt simple, se poate renunta la implementarea lor în aceasta forma, iar algoritmul general v a contine direct aceste operatii.

De asemenea, trebuie sa avem în vedere ca algoritmul general se poate modifica si adapta în functie de problema rezolvata.

Pentru o mai buna întelegere a metodei vom studia problema generarii permutarilor care se enunta astfel:

Sa se genereze toate permutarile multimii .

Explicarea metodei de rezolvare:

Problema ne cere sa gasim toate combinatiile posibile formate cu cele n elemente, astfel încât oricare doua astfel de grupe sa difere prin ordinea de asezare a elementelor.

De exemplu, pentru multimea se obtin permutarile (1, 2, 3) , (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). Algoritmul utilizat pentru generarea acestor combinatii are în vedere faptul ca orice permutare este alcatuita din toate elementele multimii , care sunt distincte.

Pentru a scrie programul , stabilim urmatoarele repere:

Vectorul solutie are n componente x[k]=v are semnificatia ca valoarea v este asezata pe pozitia k în combinatie.

Pentru orice k din multimea valorilor posibile pentru x[k] este A_k = ; initializarea se va face cu x[k] = 0.

Conditia de continuare: pentru ca o valoare x[k] sa fie acceptata trebuie ca pentru orice i, x[k]x[i] (elementele multimii nu trebuie sa se repete).

Am gasit o solutie finala daca am completat toate componentele vectorului (deci k =n).

Pentru exemplul considerat, initial k=1, x[k]=0; (se începe cu prima componenta si nu s-a testat înca nici o valoare).Vectorul solutie se va completa astfel:

Programul C++ corespunzator este

#include<iostream.h>

#include<conio.h>

const nmax=25

int x[100],n ;

void CITIRE()

void INIT(int k)

int EXISTA (int k)

int CONT(int k)

int SOLUTIE(int k)

void TIPAR(int k)

void BKT

else

k--;

void main()

APLICATII ALE METODEI BACKTRACKING ÎN COMBINATORICA

GENERALIZARE

Algoritmul de generare a permutarilor poate fi folosit pentru a aranja oricare n elemente distincte în toate modurile posibile.

Exemple:

1. Se da o multime alcatuita din n litere distincte. Se cer toate cuvintele care se pot forma cu ele, astfel încât fiecare cuvânt sa contina n litere distincte. De exemplu, daca multimea , vom avea cuvintele: abc, acb, bac, bca, cab si cba.
2. Se dau numele a n persoane. Se cere sa se afiseze toate modurile posibile în care acestea se pot aseza pe o banca. De exemplu, daca n=3, iar persoanele sunt Ioana, Costel si Mihaela, atunci solutiile sunt:

Ioana Costel Mihaela

Ioana Mihaela Costel

Costel Ioana Mihaela

…

În astfel de cazuri, cele n elemente distincte se memoreaza într-un vector v, asa cum se observa mai jos:

Atunci când s-a generat o permutare, de exemplu 213, se va afisa v[1]v[2]v[3], adica bac, în primul caz sau Costel Ioana Mihaela, în al doilea caz.

Procedeul de mai sus poate fi folosit pentru oricare alta aplicatie din combinatorica, în probleme cum ar fi: generarea tuturor submultimilor unei multimi, generarea aranjamentelor, generarea combinarilor sau a tuturor partitiilor unei multimi.

#include<iostream.h>

int x[100],n;

void init(int K)

int exista(int k)

int cont(int k)

int solutie(int k)

void tipar(int k)

void bkt()

} else

k--;}

void main()

GENERAREA ARANJAMENTELOR

Se dau doua multimi A = si B = . Se cer toate functiile injective definite pe A cu valori în B. O astfel de problema este una de generare a aranjamentelor de n elemente luate câte p ().

Exemplu: p=2, n=3. Avem: 12, 21, 13, 31, 23, 32. De exemplu, 21 este functia f : A B data astfel: f(1) = 2, f(2)=1. Avem relatiile:

Enunt: Se citesc n si p.Sa se genereze toate aranjamentele de n luate câte p.

Sa observam ca daca se cunoaste fiecare submultime de p elemente a multimii de n elemente, atunci aranjamentele se pot obtine permutând în toate modurile posibile elementele unei astfel de multimi. Pornind de la aceasta observatie, suntem tentati sa generam toate submultimile cu p elemente ale multimii cu n elemente si, din fiecare astfel de submultime, sa obtinem permutarile ei.

Pe de alta parte, se poate lucra mult mai eficient.O solutie este de forma: X1X2Xp unde X1,X2,,Xp trebuie sa fie distincte. Spre deosebire de algoritmul de generare a combinarilor, aici ne intereseaza toate permutarile unei solutii (acestea sunt,la rândul lor,alte solutii) . Aceasta înseamna ca nu mai putem pune în solutie elementele în ordine crescatoare. Sa recapitulam:

-o solutie are p numere din B

-numerele trebuie sa fie distincte.

Rezulta de aici ca algoritmul este acelasi de la pemutari, diferenta fiind data de faptul ca solutia are p numere, nu ca în cazul pemutarilor.

#include<iostream.h>

int x[100],n,p;

void init(int K)

int exista(int k)

int cont(int k)

int solutie(int k)

void tipar(int k)

void bkt()

} else

k--;}

void main()

GENERAREA COMBINARILOR

Fiind data multimea A=, se cer toate submultimile ei cu p elemente. Problema este cunoscuta sub numele de „generarea combinarilor de n, luate câte p” . Se stie ca numarul solutiilor acestei probleme este:

De exemplu, daca n=4 si p=3, solutiile sunt urmatoarele:

, , si .

Enunt.Se citesc n si p numere naturale, n>=p. Se cere sa se genereze toate submultimile cu p elemente ale multimii A=.

Rezolvare.O solutie este de forma X1, X2, , Xp unde X1, X2, ,Xp apartin multimii A. In plus, X1, X2, ,Xp trebuie sa fie distincte. Cum la o multime ordinea elementelor nu prezinta importanta, putem genera elementele ei în ordine strict crescatoare. Aceasta observatie ne ajuta foarte mult în elaborarea algoritmului.

Pentru k>1, sol[k] > sol[k-1].

Pentru fiecare k apartine , sol[k] <= n-p+k. Sa presupunem, prin absurd, ca aceasta ultima relatie nu este respectata. Aceasta înseamna ca exista k astfel încat sol[k] > n-p+k. Deci:

Sol[k+1] > n-p+k+1,

..

Sol[p] > n-p+p=n.

Absurd.De aici rezulta ca:

1 <= sol[1] <= n-p+1,

Sol[1] < sol[2] <= n-p+2,

Sol[n-1] <s ol[n] <= n-p+p= n.

Relatiile de mai sus simplifica mult algoritmul, pentru ca tinând cont de ele,nu mai este necesar sa se testeze nici o conditie de continuare.
#include<iostream.h>

int x[100],n,p;

void init(int k)

int exista(int k)

int solutie(int k)

int cont()

void tipar(int k)

void bkt()

} else

k--;}

void main()

APLICATIE

ENUNT

La o conferinta participa n persoane. Fiecare reprezinta o firma. Se cunosc p perechi de persoane care apartin unor firme concurente. În cadrul conferintei se organizeaza:

O masa rotunda la care trebuie sa participe cele n persoane. Se cere sa se determine toate modalitatile de asezare la masa a persoanelor astfel încât sa nu stea alaturi doua persoane de la firme concurente.

Un workshop la care trebuie sa participe t persoane. Sa se determine toate modalitatile de participare la workshop astfel încât la workshop sa participe cel putin un reprezentant al unei firme.

DATE DE INTRARE

Fisierul „CONFERINTA.IN” va contine:

a.     Pe prima linie un numar natural reprezentând numarul de persoane participante la conferinta;

b.     Pe urmatoarele n linii se vor gasi câte doua siruri de caractere care reprezinta numele unei persoane si denumirea firmei la care este angajata;

c.      Pe urmatoarele p linii se vor gasi câte doua siruri de caractere care reprezinta numele a doua persoane de la firme concurente.

DATE DE IESIRE

Se vor afisa în fisierul „CONFERINTA.IN” .

REZOLVAREA PROBLEMEI

SURSA PROGRAMULUI C++

#include<fstream.h>

#include<string.h>

int x[100],n,p,k,a[100][100];

void init(int K)

int exista(int k)

int cont(int k)

else return 1; }

int solutie(int k)

void tipar(int k)

void bkt()

} else

k--;}

void main()

EXECUTIA PROGRAMULUI

TEST 1

DATE DE INTRARE:

DATE DE IESIRE:

TEST 2

DATE DE INTRARE:

DATE DE IESIRE :

BIBLIOGRAFIE

LIVIA TOCA, ANDREEA RUXANDRA DEMCO, CRISTIAN OPINCARU, ADRIAN SINDILE - INFORMATICA , MANUAL PENTRU CLASA A X-A, EDITURA NICULESCU, BUCURESTI, 2001

MIHAELA RUNCEANU, CARMEN NEGREA - CULEGERE DE PROBLEME DE INFORMATICA VARIANTELE PASCAL SI C++, EDITURA DONARIS - SIBIU, 2003

VLAD HUTANU, TUDOR SORIN - MANUAL DE INFORMATICA INTENSIV, Clasa a XI-a, EDITURA L&S Soft - BUCURESTI, 2006

CUPRINS

Prezentare generala …………………………..	2
Algoritmul general al metodei backtraking ….	3
Aplicatie ………………………………………….
Rezolvarea problemei …………………………..
Sursa programului C++ ………………………..
Executia programului …………………………..
Bibliografie ……………………………………