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

c

+ Font mai mare | - Font mai mic





DOCUMENTE SIMILARE

Trimite pe Messenger
Generarea de numere aleatoare
Implementarea grafurilor cu ajutorul matricei de adiacenta
Variabile locale
Conversii de format in memorie
Clase virtuale
Programarea calculatorului
PROGRAMAREA STRUCTURILOR DE DATE IN C
Variabile registru
Pointerii nu sint de tip int
Stergerea unui fisier

TERMENI importanti pentru acest document

Metoda backtracking

Prezentarea metodei




Metoda backtracking (in traducere “cautare cu revenire”) se aplica problemelor in care solutia se poate reprezenta sub forma unui vector s = (s1, , sn), s I S, S = S1 x x Sn. Multimea Sk are nk elemente, k = 1, , n. O solutie s I S se numeste solutie posibila si S se numeste spatiul solutiilor posibile. In orice problema concreta sunt date anumite relatii intre componentele s1, , sn, ale vectorului s, numite restrictii interne. Solutiile posibile care satisfac restrictiile interne se numesc solutii admisibile. In probleme se cere determinarea tuturor solutiile admisibile sau numai a uneia dintre ele, numita solutie optima, care optimizeaza o functie obiectiv data.

Observatii

Nu in toate problemele care pot fi rezolvate cu metoda backtracking se cunoaste de la inceput numarul n al multimilor S1, , Sn.

Componentele s1,,sn ale vectorului solutie s pot fi la randul lor vectori.

In unele probleme, multimile S1, , Sn coincid.

O metoda simpla de determinare a solutiilor admisibile consta in a genera, intr-un mod oarecare, toate solutiile posibile si de a le selecta doar pe cele care verifica restrictiile interne. Dezavantajul acestei metode este timpul necesar de investigare exhaustiva care este foarte mare. Astfel, chiar pentru nk = 2, k = 1, , n, timpul necesar este θ(2n), deci exponential.

Metode backtracking evita generarea tuturor solutiilor posibile. Aceasta metoda construieste o solutie admisibila, pas cu pas, prin adaugarea unei componente sk I Sk la o solutie partiala (s1, , sk-1) numita solutie acceptabila. Daca solutia partiala (s1, , sk-1, sk) verifica anumite conditii, numite conditii de continuare, atunci aceasta solutie partiala devine noua solutie acceptabila.

Ideea generala a metodei backtracking consta in urmatoarele:

(s1) este solutie acceptabila;

k:=2;

cat timp mai sunt elemente netestate in S1

daca mai exista element netestat sk din Sk atunci

daca (s1, , sk) indeplineste conditiile de continuare atunci

daca (s1, , sk) este solutie admisibila atunci

tipareste (s1,,sk)

altfel (s1,,sk) este solutie acceptabila si se alege un element     netestat din Sk+1

altfel (s1, , sk-1) este solutie accetabila si se alege un element netestat din Sk

altfel (s1, , sk-2) este solutie accetabila si se alege un element netestat din Sk-1;

Conditiile de continuare sunt in stransa legatura cu restrictiile interne si le formalizam prin functiile:

ck : S1 x x Sk → , k = 1, …, n

Metoda backtracking este prezentata in procedura BACKTRACK, care apeleaza procedura CONDCONT ce testeaza conditiile de continuare.

PROCEDURA CONDCONT(n, s, k, v);

BEGIN

ARRAY s(n);

IF ck( s1, , sk) = 1

THEN v := 1

ELSE v := 0;

ENDIF;

END

PROCEDURA BACKTRACK(n, s);

BEGIN

ARRAY s(n);

k := 1;

WHILE k > 0 DO

WHILE exista element netestat ei din Sk DO

sK := ei;

CONDCONT(n, s, k, v);

IF v = 1 THEN

IF k = n

THEN WRITE( s )

ELSE k := k + 1;

ENDIF;

ENDIF;

ENDWHILE

k := k – 1;

ENDWHILE;

END;

Observatii

Daca inlocuim predicatul ck cu 1 pentru orice k = 1, , n, atunci vor fi listate toate solutiile posibile ale problemei.

Metoda backtracking poate fi reprezentata pe un arbore radacina construit in modul urmator:

nivelul 0 contine nodul radacina r;

fiecare nod x de pe nivelul k - 1 are nk succesori y1, , , k = 1, , n si arcul (x, yi) este etichetat cu elementul ei din Sk, i = 1, , nk;

nivelul n contine n = n1 n2 nn noduri si pentru fiecare nod terminal, drumul D = (s1, , sn), sk I Sk, k = 1, , n reprezinta o solutie posibila;

determinarea solutiilor admisibile cu metoda backtracking corespunde parcurgerii DF (mai intai in adancime) a arborelui radacina

Teorema 4.2

Metoda backtracking are complexitatea exponentiala.

Demonstratie

Evident

Probleme rezolvate

Problema B1

Colorarea hartilor

Fiind data o harta cu n tari, se cere sa se genereze toate solutiile de colorare a hartii cu m culori astfel incat pentru fiecare tara sa se foloseasca o singura culoare si doua tari vecine (cu frontiera comuna) sa fie colorate diferit.

Observatie

Este demonstrat faptul ca sunt suficiente 4 culori pentru colorarea tarilor conform enuntului problemei.

Rezolvarea problemei cu metoda backtracking

Configuratia hartii este furnizata cu ajutorul unei matrice H = (hij)nxn,

daca tara i este vecina cu tara j,

in caz contrar.

Fie C = = multimea celor m culori si T = multimea celor n tari. Elementele problemei sunt urmatoarele:

Sk = C, k = 1, , n

o solutie posibila este de forma s = (s1, , sn), sk I C, k = 1,,n;

restrictiile interne sunt: si sj daca hij = 1, i = 1,,n, j = 1,,n;

conditiile de continuare sunt: si sk pentru orice tara i din T, vecina cu tara k.

Algoritmul de colorare este prezentat in procedura COLOR care apeleaza procedura CONDCONT ce testeaza conditiile de continuare.

PROCEDURA COLOR(n, s, m, H);

BEGIN

ARRAY s(n); H(n,n);

k := 1; s1 = 0;

WHILE k > 0 DO

WHILE sk < n DO

sk := sk + 1;

CONDCONT(n, s, k, v, H);

IF v = 1 THEN

IF k = n THEN

WRITE( s )

ELSE

BEGIN

k := k + 1; sk := 0;

END;

ENDIF

ENDIF;

ENDWHILE;

k := k - 1;

endWHILE;

END;

PROCEDURA CONDCONT(n, s, k, v, H);

BEGIN

ARRAY s(n); H(n,n);

v := 1;

FOR i := 1 TO k - 1 DO

IF hik = 1 and si = sk THEN

v:=0; EXIT;

ENDIF;

ENDFOR;

END;

Fie harta cu multimea tarilor T si multimea culorilor C prezentate in figura 4.2. Arborele radacina asociat metodei backtracking pentru rezolvarea problemei colorarii acestei harti este prezentat in figura 4.3.

T = S1 = S2 = S3 = C =

Figura 4.2



Figura 4.3

Solutiile admisibile obtinute cu procedura COLOR (parcurgerea DF a arborelui radacina) sunt urmatoarele:

s = (1, 2, 1); s = (1, 2, 3); s = (1, 2, 4); s = (1, 3, 1); s = (1, 3, 2);

s = (1, 3, 4); s = (1, 4, 1); s = (1, 4, 2); s = (1, 4, 3); s = (2, 1, 2);

s = (2, 1, 3); s = (2, 1, 4); s = (2, 3, 1); s = (2, 3, 2); s = (2, 3, 4);

s = (2, 4, 1); s = (2, 4, 2); s = (2, 4, 3); s = (3, 1, 2); s = (3, 1, 3);

s = (3, 1, 4); s = (3, 2, 1); s = (3, 2, 3); s = (3, 2, 4); s = (3, 4, 1);

s = (3, 4, 2); s = (3, 4, 3); s = (4, 1, 2); s = (4, 1, 3); s = (4, 1, 4);

s = (4, 2, 1); s = (4, 2, 3); s = (4, 2, 4); s = (4, 3, 1); s = (4, 3, 2);

s = (4, 3, 4);

Textul sursa al programului care implementeaza algoritmul prezentat mai sus este:

#include<stdio.h>

void afisare(int s[20], int n)

int cont(int s[20], int k, int h[20][20])

void back(int n, int m, int h[20][20])

k--;

}

void main()

back(n,m,h);

Problema B2

Problema permutarilor

Sa se afiseze toate permutarile de cate n elemente. De exemplu, pt n=3 acestea sunt 1, 2, 3 – 1, 3, 2 – 2, 1, 3 – 2, 3, 1 – 3, 1, 2 – 3, 2, 1.

Rezolvarea problemei cu metoda backtracking

Fie C = = multimea celor n obiecte. Elementele problemei sunt urmatoarele:

Sk = C, k = 1, , n

o solutie posibila este de forma s = (s1, , sn), sk I C, k = 1,,n;

conditiile interne sunt: si sj, i = 1,,n, j = 1,,n;

conditiile de continuare sunt: si sk pentru orice obiect i din .

Algoritmul de generarea a permutarilor este prezentat in procedura PERM care apeleaza procedura CONDCONT ce testeaza conditiile de continuare.

PROCEDURA PERM(n, s);

BEGIN

ARRAY s(n);

k := 1; s1 = 0;

WHILE k > 0 DO

WHILE sk < n DO

sk := sk + 1;

CONDCONT(n, s, v);

IF v = 1 THEN

IF k = n THEN

WRITE( s )

ELSE

BEGIN

k := k + 1; sk := 0;

END

ENDIF;

ENDIF;

ENDWHILE;

k := k - 1;

endWHILE;

END;

PROCEDURA CONDCONT(n, s, k, v);

BEGIN

ARRAY s(n);

v := 1;

FOR i := 1 TO k - 1 DO

IF si = sk THEN

v:=0; EXIT;

ENDIF;

ENDFOR;

END;

Codul sursa al programului este:

#include<stdio.h>

void afisare(int s[20], int n)

int cont(int s[20], int k)

void back(int n)

k--;

}

void main()

Problema B3

Problema discreta a rucsacului.

Un hot sparge un magazin in care se gasesc n obiecte pe care si le-ar dori. Din pacate, greutatea lor totala depaseste capacitatea sacului pe care il are la dispozitie. Prin urmare, el este nevoit sa aleaga doar cateva din cele n obiecte. Hotul alege obiectele in functie de greutatea si valoarea lor, in asa fel incat valoarea finala a furtului sa fie maxima. Datele de intrare sunt: capacitatea rucsacului, numarul n de obiecte si pentru fiecare obiect in parte greutatea si utilitatea lui. Sa se afiseze obiectele furate de hot.

Rezolvarea problemei cu metoda backtracking

Fie C = = multimea celor n obiecte identificate prin valorile V = , si greutatile G = lor; capacitatea sacului este Capac;

Elementele problemei sunt urmatoarele.

Sk = C, k = 1, , n

o solutie posibila este de forma s = (s1, , sn), si I , i = 1,,n cu proprietatea ca ; daca si = 0 inseamna ca obiectul i nu este pus in sac, iar daca si = 1 inseamna ca obiectul i este pus in sac;

conditiile interne sunt: si sj, i = 1,,n, j = 1,,n;

conditiile de continuare sunt: si sk pentru orice obiect i din .

Algoritmul de determinare a multimii obiectelor furate este prezentat in procedura SAC care apeleaza procedura CONDCONT ce testeaza conditiile de continuare.

PROCEDURA SAC(n, s);

BEGIN

ARRAY s(n);

k := 1; s1 := -1; C1 := 0; V1 := 0; Vmax := 0;

WHILE k > 0 DO

(6) WHILE sk < 1 DO

(7) sk := sk + 1;

IF sk = 1 THEN

BEGIN

C1:= C1 + g[k];

V1:= V1 + v[k];

END;

IF CONDCONT(s, k, C1) THEN

IF k = n THEN

IF C1 ≤ C and V1 > Vmax THEN

Vmax := V1;

retine(S, Smax);

ENDIF;

ELSE

BEGIN

k := k + 1; sk := -1;

END;

ENDIF;

ENDIF;

ENDWHILE;

IF sk = 1 THEN

BEGIN

C1:= C1 - g[k];

V1 := V1 - v[k];

END;

k := k - 1;

endWHILE;

END;

PROCEDURA CONDCONT(s, k, C1)

(2) BEGIN

IF sk = 1 AND C1 > C THEN

return False

ELSE

return True

ENDIF;

(8) END;

Codul sursa al programului este:

#include<stdio.h>

typedef struct

obiect;

void afisare(int s[20], int n, obiect o[20])

int cont(int s[20], int k, double c, double c1)

void retine(int s[20], int smax[20], int n)

void back(int n, double c, obiect o[20])

if(cont(s,k,c,c1))

if(k==n)

}

else

s[++k]=-1;

}

if(s[k]==1)

k--;

}

afisare(smax, n, o);

void main()

back(n,c,o);






Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 767
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 2021 . All rights reserved

Distribuie URL

Adauga cod HTML in site