Algoritmi backtracking (II)
Operatii asociate alegerii unui candidat
Acceptarea unei valori candidat pentru o componentă x[k] a solutiei poate implica anumite operatii legate de această alegere, operatii specifice problemei rezolvate. De exemplu, în problema restului, alegerea unei monede este însotită de diminuarea sumei rămase de acoperit cu valoarea monedelor alese. Vom reuni aceste operatii asociate alegerii unei valori pentru x[k] într-o functie "include(k)& 20220e424u quot; apelată în "cautSol".
Metoda backtracking poate reveni asupra valorii alese pentru x[k] si oricum mai încearcă si alte valori pentru x[k], deci toate operatiile efectuate la alegerea unei valori pentru x[k] trebuie anulate odată cu renuntarea la o valoare aleasă anterior. Vom reuni aceste operatii asociate anulării unei valori pentru x[k] într-o functie "exclude(k)", cu efect de refacere a stării dinaintea executării procedurii "include".
O altă exprimare folosită este aceea că procedura "include" modifică contextul aplicării metodei backtracking, iar procedura "exclude" reface contextul modificat de "include".
Noua formă a functiei "cautSol", completată cu operatii de includere si excludere:
void cautSol ( int k)
}
Uneori functiile "include" si "exclude" contin o singură instructiune si acestea pot fi inserate direct în procedura "cautSol", fără a mai defini subprograme separate .
In mai multe probleme functia "posibil" trebuie să verifice că valoarea propusă pentru x[k] este diferită de valorile x[1],..x[k-1]. In aceste cazuri functia "include" va adăuga la multime valoarea lui x[k], iar functia "exclude" va elimina din multime valoarea lui x[k] :
// adauga x[k] la multimea v
void include (int k)
// elimina pe x[k] din multimea v
void exclude (int k)
Algoritm backtracking pentru problema restului
Problema restului se poate enunta astfel: Fiind date o sumă de plată "rest" si n tipuri de monede cu valori a[1], a[2],...,a[n], să se determine:
a) toate modalitatile de achitare a sumei "rest" folosind monedele disponibile;
b) numărul minim de monede si valorile lor (tipurile de monede) pentru achitarea sumei "rest'"
Vectorul x contine numărul de monede din fiecare tip, deci x[i] este numărul monedelor de valoare a[i]. De remarcat că este posibil ca mai multe componente x[i] să aibă valoarea zero, dacă monedele respective nu sunt folosite. Deci, ciclul 'for' din functia "cautSol" porneste cu valoarea 0 si nu cu valoarea 1.
Conditia de acceptare a unei valori x[k] este :
a[k]+x[k] <= rest pentru k < n si
a[k]*x[k] = rest pentru k=n.
Functia "scrieSol" retine numărul minim de monede folosite si valorile acestor monede.
Problema nu are solutie dacă suma "rest" nu poate fi acoperită exact cu monedele disponibile (când nu există monedă cu valoarea 1). Urmează un program complet pentru varianta (b):
// exprimare rest de plata cu numar minim de monede
#define M 20 // nr. maxim de monede diferite
int a[M], x[M], xopt[M];
int n,m,rest,i,min;
// diminuare rest cu x[k] monede de valoare a[k]
void include (int k)
// refacere rest dupa eliminare x[k] monede
void exclude (int k)
// daca se pot folosi x[k] monede de val. a[k]
int posibil (int k)
// retine numar minim de monede folosite
void prelSol (int k)
}
// determina nr de monede de valoare a[k]
void cautSol ( int k)
}
void main ()
Programul principal contine o mică simplificare, în sensul că numărul maxim de monede de aceeasi valoare 'm' ar trebui calculat ca maxim între valorile (rest div a[i]), dar am presupus că există o monedă de valoare 1 si deci acest număr este (rest div 1).
Problema restului poate fi considerată ca o problemă cu solutie de lungime fixă (egală cu numărul de monede diferite) sau ca problemă cu solutie de lungime variabilă, ignorând valorile x[k]=0 de la sfârsitul vectorului x.
Probleme cu solutii de lungimi diferite
Functia "cautSol" consideră că s-a obtinut o solutie atunci când k = n, deci când s-au determinat toate cele n componente ale solutiei.
Intr-o serie de probleme solutiile au lungime variabilă, iar conditia de obtinere a unei solutii este specifică problemei rezolvate. De exemplu, la determinarea tuturor drumurilor dintre două noduri dintr-un graf sau a determinării drumului minim dintre două noduri, solutia este formată din numerele nodurilor de pe drumul găsit, iar lista acestor numere poate avea orice lungime.
Pentru a lua în considerare si aceste probleme cu solutii de lungimi diferite vom modifica functia "cautSol" înlocuind conditia k==n sau k > n cu o functie "solutie(k)", care are rezultat 1 dacă s-a obtinut solutie în pasul 'k' si rezultat 0 dacă nu s-a obtinut o solutie.
Functia "solutie" are nevoie de parametrul k pentru că ea verifică dacă primele k componente ale vectorului 'x' pot constitui o solutie.
De observat că în acest caz si functia "prelSol" are nevoie de parametrul k, care reprezintă lungimea solutiei ce trebuie afisată sau comparată.
Functia 'cautSol' va avea una dintre formele următoare:
// cauta solutie de lungime variabia
void cautSol ( int k)
// cautare solutie de lungime variabila
void cautSol ( int k)
In prima variantă subprogramele "solutie" si "prelSol" primesc parametrul 'k-1' si nu 'k' deoarece verifică existenta solutiei în pasul k-1, căci valoarea x[k] nu a fost încă determinată de "cautSol".
Pentru problema permutărilor functia "solutie" va fi :
// daca solutie de lungime n
int solutie (int k)
Problema drumului dintre două noduri dintr-un graf
Intr-un graf dat se specifică două noduri si se cere să se spună dacă există sau nu (cel putin) un drum între aceste noduri.
Solutia backtracking înaintează în graf pornind din nodul sursă, pe toate arcele posibile, până ajunge la nodul destinatie sau până când epuizează toate posibilitătile de înaintare în graf.
Dacă există un drum, atunci vectorul solutie contine numerele nodurilor de pe drumul găsit de la sursă la destinatie. Lungimea vectorului solutie poate varia între 2 (drumul este arcul direct de la sursă la destinatie) sau n (numărul de noduri în graf), dacă drumul căutat trece prin toate nodurile. Problema are si o solutie mai eficientă, prin explorare în adâncime din nodul sursă si verificarea atingerii nodului destinatie.
Conditia de acceptare a unei valori pentru x[k] este ca nodul x[k] să nu fi fost deja vizitat si ca să existe arc de la nodul x[k-1] la nodul x[k]. De fapt, este suficient să se verifice existenta arcului (x[k-1],x[k]), deoarece nu există arce de forma (v,v) si fiecare x[i] este diferit de x[i-1].
De observat că, în programul principal, se initializează x[1] cu numărul nodului sursă 'v' si se apelează procedura "cautSol" cu parametul 2, pentru că x[1] este fixat si se caută valori numai
pentru componentele x[2],x[3],.. din vectorul solutie.
Functia "solutie(k)" verifică dacă în pasul k s-a ajuns la nodul destinatie 'w'. Functia "prelSol" din programul următor nu afisează nimic, ci doar numără într-o variabilă "nd" solutiile găsite.
Functia arc(v,w) verifică dacă există arc de la nodul 'v' la nodul 'w'.
// numara drumuri posibile dintre doua noduri
#define M 20 // nr. max de noduri
int n ; // n=nr de noduri
int a [M][M] ; // matr. de adiacente graf
int x [M] ; // vector solutie
int nd=0 ; // numar de drumuri intre 2 noduri
int v,w; // noduri sursa si destinatie
// test daca arc intre x[k-1] si x[k]
int posibil (int k)
// test daca solutie completa
int solutie (int k)
// actiuni la obtinerea unei solutii
void prelSol(int k)
void cautSol ( int k)
}
void main ()
Acest program se poate modifica usor pentru a rezolva si alte probleme cu grafuri.
Pentru a stabili dacă un graf este sau nu puternic conectat (tare conex) vom repeta în programul principal căutarea drumului între toate perechile de noduri din graf. De fapt, programul se termină când găseste prima pereche de noduri între care nu există drum :
// verifica daca un graf dat este tare conex
void main ()
}
printf( "graf tare conex");
Pentru a stabili dacă un graf este sau nu aciclic este suficient să facem nodul destinatie egal cu nodul sursă si să repetăm apelul functiei "cautSol" pentru fiecare nod din graf. Dacă există un drum care pleacă si se întoarce în acelasi nod, atunci graful nu este aciclic.
void main ()
}
printf (" graf aciclic \n");
Pentru acest program mai este necesară o mică modificare în functia "cautSol", care să permită vectori de lungime n+1, pentru detectarea si afisarea unui ciclu hamiltonian într-un graf. De exemplu, într-un graf cu 3 noduri ciclurile au forma 1,2,3,1 sau 1,3,2,1.
Metoda backtracking pentru probleme de optimizare
Problemele abordate până acum au fost probleme de decizie si probleme de enumerare (de
determinare si afisare a tuturor solutiilor posibile).
Intr-o problemă de optimizare trebuie determinată solutia optimă dintre toate solutiile posibile. Functia "cautSol" nu se modifică, datorită rolului pe care îl are de a genera toate solutiile posibile si de a le transmite functiei "scrieSol". Modificările apar în functia "scrieSol" si în programul principal, după cum sunt necesare si câteva noi variabile.
Functia "prelSol" nu afisează solutia descoperită ci o compară cu o solutie optimă partială si eventual modifică solutia optimă partială. După compararea tuturor vectorilor solutie generati de "cautSol", optimul retinut de "prelSol" este chiar solutia optimă căutată si poate fi afisată de programul principal, unde se revine din "cautSol" după generarea tuturor solutiilor.
Criteriul de optim este de obicei o singură mărime numerică, cum ar fi o sumă calculată pe baza vectorului solutie. De exemplu, în problema determinării drumului de cost minim dintre două noduri date dintr-un graf cu costuri, criteriul de optim este costul total al drumului găsit, deci suma costurilor arcelor de pe acest drum.
Pentru a retine solutia optimă mai este necesar un vector 'xopt', eventual si lungimea sa, dacă nu este mereu aceeasi; copierea din vectorul 'x' în 'xopt' se face atunci când se găseste un drum de cost mai mic decât cele găsite anterior, în functia 'prelSol'.
Valoarea minimă (sau maximă) este initializată în programul principal, înainte de primul apel al functiei "cautSol". Valorile dintre care se determină minimul (sau maximul) sunt generate prin procesul declansat de apelul functiei recursive "cautSol".
Programul următor determină drumul de cost minim dintre două noduri date ale unui graf .
// drum minim in graf prin backtracking
#define M 20 // nr. max de noduri
int n, nopt ; // n=nr de noduri
int c [M][M] ; // matr. de costuri graf
int x [M], xopt[M] ; // vector solutie
int cmin ; // cost drum minim intre 2 noduri
int v,w; // noduri sursa si destinatie
// test daca arc intre x[k-1] si x[k]
int posibil (int k)
// test daca s-a ajuns in nodul w
int solutie (int k)
// determina drumul minim si costul sau
void prelSol(int k)
// cauta solutie de lungime variabila
void cautSol ( int k)
//
void main ()
|
