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 ()
|
