Documente online.
Username / Parola inexistente
  Zona de administrare documente. Fisierele tale  
Am uitat parola x Creaza cont nou
  Home Exploreaza
Upload




























Algoritmi backtracking (II) - Operatii asociate alegerii unui candidat

Informatica




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










Document Info


Accesari: 3311
Apreciat:

Comenteaza documentul:

Nu esti inregistrat
Trebuie sa fii utilizator inregistrat pentru a putea comenta


Creaza cont nou

A fost util?

Daca documentul a fost util si crezi ca merita
sa adaugi un link catre el la tine in site

Copiaza codul
in pagina web a site-ului tau.




eCoduri.com - coduri postale, contabile, CAEN sau bancare

Politica de confidentialitate




Copyright © Contact (SCRIGROUP Int. 2021 )