Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  
AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Metoda backtracking (cautare cu revenire)

c



+ Font mai mare | - Font mai mic



Metoda backtracking (cautare cu revenire)

Aceasta metoda se aplica problemelor ce pot fi reprezentate sub forma unui arbore finit iar cautarea solutiei presupune parcurgerea arborelui in adancime (DF=Depth First).



Problemele de acest tip au in general solutia de forma x=(x1, . . . ,xn) I S1x . . . xSn, fiecare Sk fiind o multime finita. Mai facem cateva precizari preliminare:

a) pentru fiecare problema sunt date anumite relatii intre componentele x1, . . . ,xn ale lui

x numite conditii interne;

b) produsul cartezian S=S1xxSn se mai numeste spatiul solutiilor posibile, iar solutiile

posibile care satisfac conditiile interne se numesc solutii rezultat;

c) in general se cer doua lucruri in astfel de probleme:

- determinarea tuturor solutiilor rezultat;

- determinarea doar a acelor solutii care optimizeaza o functie obiectiv data.

Cum rezolvam astfel de probleme? Exista doua modalitati de rezolvare:

1) tehnica directa (numita si tehnica fortei brute) prin care se genereaza toate elementele spatiului de solutii posibile si apoi se verifica fiecare daca este sau nu o solutie rezultat; aceasta tehnica necesita un timp prohibitiv (daca fiecare Si are doar 2 componente complexitatea este O(2n); totodata ar fi necesara imbricarea a n cicluri cu n aprioric necunoscut).

2) backtracking care evita generarea tuturor solutiilor posibile.

Sa dam in continuare cateva repere ale rezolvarii:

solutia este construita progresiv, componenta cu componenta;

lui xk i se atribuie o valoare (evident ca numai din Sk) daca si numai daca x1, . . . ,xk-1 au deja valori;

se verifica conditiile de continuare (strans legate de conditiile interne) daca are sens trecerea la xk+1;

daca nu are sens (adica conditiile de continuare nu sunt indeplinite atunci facem o noua alegere pentru xk sau daca am epuizat valorile din Sk atunci k:=k-1 si se face o noua alegere pentru xk-1; s.a.m.d.

2. daca are sens atunci k:=k+1 si se testeaza daca k>n:

21) daca inegalitatea este adevarata atunci se afiseaza solutia astfel determinata

si k:=k-1 continuand procesul de la punctul 1;

22) daca inegalitatea este falsa se continua procesul de la punctul 1.

Procedura rezolvarii unor astfel de probleme este:

procedure BT(n,x)

integer n;

array x(n);

k:=1;

while k>0 do

cod:=0;

while ([mai exist o valoare α din Sk netestat] and cod=0)

x(k):=α;

if Æk(x(1),,x(k)) then cod:=1;

endif;

endwhile;

if cod=0 then

k:=k-1

else

if k=n then write (x(1),,x(n))

else k:=k+1

endif

endif;

endwhile;

return;

end procedure

Vom face cateva precizari:

1o. Predicatul Æk(x1, . . . , xk) reprezinta conditiile de continuare pentru x1, . . . , xk;

2o. Cod este o valoare ce indica indeplinirea/neindeplinirea conditiilor de continuare;

3o. Daca predicatul Æk(x1, . . . , xk) este adevarat k I atunci se vor afla toti vectorii din S;

4o. Backtracking poate fi usor reprezentat pe un arbore construit astfel:

- nivelul 1 contine radacina;

- din orice nod de pe nivelul k pleaca sk muchii spre nivelul k+1, etichetate cu cele

sk elemente ale lui Sk;

- nivelul n+1 va contine s1*s2*. . .* sn noduri frunza;

- pentru fiecare nod de pe nivelul n+1 etichetele muchiilor continute in drumul ce

leaga radacina de acest nod reprezinta o solutie posibila;

Daca multimile Sk reprezinta progresii aritmetice atunci algoritmul general se modifica astfel:

procedure BTA(n,a,b,h)

integer n;

array primul(n),ultimul(n),ratia(n),x(n);

k:=1;

x(1):=primul(1)-ratia(1);

while k>0 do

cod:=0;

while ( x(k)+ratia(k) £ ultimul(k) and cod=0 )

x(k):=x(k)+ratia(k);

if Æk(x(1),,x(k)) then cod:=1 endif;

endwhile;

if cod=0 then

k:=k-1

else

if k=n then write (x(1),,x(n))

else k:=k+1

x(k):=a(k)-h(k)

endif

endif;

endwhile;

return;

end procedure

unde:

- primul(n) reprezinta vectorul primilor termeni ai progresiilor aritmetice;

- ultimul(n) reprezinta vectorul ultimilor termeni ai progresiilor aritmetice;

- ratia(n) reprezinta vectorul ratiilor progresiilor aritmetice;

De retinut cele doua avantaje ale acestui procedeu:

evitarea imbricarii unui numar oarecare de cicluri aprioric variabil (in algoritmul propus se imbrica doar doua cicluri pretestate while);

evitarea construirii spatiului tuturor solutiilor posibile S1xS2x . . . xSn.

Problema rezolvata

In cate moduri se pot aranja 8 dame pe tabla de sah astfel incat sa nu se 'bata' reciproc. Sa se foloseasca al doilea algoritm dintre cei mentionati anterior.



Prima varianta

Acest program respecta algoritmul anterior cu unele mici modificari. Facem precizarea ca vectorul x contine in componenta x[i] numarul coloanei de pe tabla de sah pe care se va afla dama de pe linia i. Tiparirea va reprezenta o permutare (din cele 8! solutii posibile). Se vor afla 92 de solutii. Lasam pe seama cititorului sa deduca analogiile si diferentele intre algoritm si program.

#include <stdio.h>

#include <math.h>

void main (void)

// sfarsit while

} // sfarsit if

// sfarsit while

if (cod= =0) k‑‑;

else }

else x[++k]=0;

}

A doua varianta:

#include <stdio.h>

#include <math.h>

#define n 100

int x[100],cod,k,nc,nsol;

int Verifica(void)

return cod1;

void ScrieSolutie(void)

void CitesteDate(void)

void main (void)

if (cod= =0) k‑‑;

else

A doua varianta este modulara, mai usor de inteles si generalizeaza problema damelor pana la tabla de sah de 100x100. Lasam pe seama cititorului modificarea functiei ScrieSolutie pentru a afisa in mod grafic tabla de sah.

Daca in functia Verifica se sterge instructiunea notata cu (*) atunci se obtin toate permutarile de n obiecte.

Probleme propuse

Sa se rezolve problema turelor de sah dupa al doilea algoritm. In cate moduri se pot aranja n turnuri pe tabla de sah astfel incat sa nu se 'bata' reciproc.

Sa se afiseze pozitiile succesive ale unui cal pe tabla de sah, pornind dintr-o pozitie data, astfel incat sa fie atinse toate casutele tablei de sah.

Avand un fisier cu o multime de cuvinte din limba romana de aceeasi lungime k sa se scrie un program C care afiseaza toate careurile rebusiste fara puncte negre. ( Problema e fascinanta implicand si cunostinte gramaticale dar si cunoscand faptul ca nu s-au construit careuri de 10x10 fara puncte negre manual si nici cu ajutorul calculatorului; se poate incerca apoi si cu k:=11,12, . . .).

Un intreprinzator dispune de un capital C si are n variante de investitii. Pentru fiecare investitie i cunoaste fondurile de investitie fi precum si beneficiile bi. Se cere un program care sa deduca toate variantele posibile de investitii al intreprinzatorului. Se mai dau si conditiile C³ci iI

Avand un graf neorientat caracterizat prin matricea costurilor sa se determine prin bactraking circuitul de cost minim pornind dintr-un varf dat.

Avand un graf neorientat caracterizat prin matricea de incidenta a varfurilor sa se determine prin bactraking multimile interior stabile maximale.

Sa se determine toate cuvintele binare de lungime 10 care contin exact 5 cifre de 1.

Sa se determine toate cuvintele binare de lungime 10 care contin cel mult 5 cifre de 1.

Sa se determine toate cuvintele din * (multimea tuturor cuvintelor peste alfabetul Σ se noteaza cu Σ* ) de lungime 10 care contin exact 2 simboluri 'a'; 3 simboluri 'b' si 5 simboluri 'c'.

Sa se determine toate cuvintele din * de lungime n care contin exact na simboluri 'a'; nb simboluri 'b' si nc simboluri 'c' (cu conditia n=na+nb+nc).

Sa se determine toate tripletele (x1,x2,x3) de numere astfel ca:

x1+x2+x3£suma

x1*x2*x3£produs

cu valorile suma si produs date iar x1IS1, x2IS2 si x3IS3 ; S1, S2 si S3 fiind trei progresii aritmetice date deasemenea.

Sa se determine toate variantele de pronosport cu 13 rezultate din care contin exact n1 simboluri '1'; nx simboluri 'x' si n2 simboluri '2' (cu conditia n1+nx+n2=13).

Sa se determine toate variantele de pronosport cu 13 rezultate din care contin cel mult n1 simboluri '1'; cel mult nx simboluri 'x' si simboluri '2' in rest (cu conditia n1+nx£





Politica de confidentialitate | Termeni si conditii de utilizare



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1121
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved