met backtracking bun

Upload: imovinabil

Post on 10-Apr-2018

265 views

Category:

Documents


0 download

TRANSCRIPT

  • 8/8/2019 Met Backtracking Bun

    1/28

    UNIVERSITATEA DIN CRAIOVAFACULTATEA DE INFORMATIC MATEMATIC

    METODA BACKTRACKING

    PROFESOR: Student :

    Bzvan Petre tefan Cristian

    2009

  • 8/8/2019 Met Backtracking Bun

    2/28

    TEMA LUCRRII:

    COLORAREA HRILOR FOLOSIND METODA BACKTRACKING

    Motivul alegerii acestei teme este:

    Studierea si aprofundarea rezolvarii problemelor prinmetoda backtracking.

  • 8/8/2019 Met Backtracking Bun

    3/28

    CUPRINS:

    1. METODA BACKTRACKING 3

    2. APLICAII REZOLVATE 5

  • 8/8/2019 Met Backtracking Bun

    4/28

    METODA BACKTRACKINGNOIUNI GENERALE

    La dispoziia celor care rezolv probleme cu ajutorul calculatorului

    exist mai multe metode . Dintre acestea cel mai des utilizate sunt:

    - metoda Greedy;

    - metodaDivide et impera;

    - metodaBranch and Bound;

    - metodaBacktracking;

    Metoda Backtracking se aplic problemelor n care soluia poate fi

    reprezentat sub forma unui vector x = (x1, x2, x3, xk, xn) S, unde S

    este mulimea soluiilor problemei i S = S1 x S2 x x Sn, i Si sunt mulimi

    finite avnd s elemente si xi si , ()i = 1..n.Pentru fiecare problem se dau relaii ntre componentele vectorului x,

    care sunt numite condiii interne; soluiile posibile care satisfac condiiile

    interne se numesc soluii rezultat. Metoda de generare a tuturor soluiilor

    posibile si apoi de determinare a soluiilor rezultat prin verificarea ndeplinirii

    condiiilor interne necesit foarte mult timp.

    Metoda backtracking evit aceast generare i este mai eficient.

    Elementele vectorului x, primesc pe rnd valori n ordinea cresctoare a

    indicilor, x[k] va primi o valoare numai daca au fost atribuite valori

    elementelor x1.. x[k-1]. La atribuirea valorii lui x[k] se verifica ndeplinirea

    unor condiii de continuare referitoare la x1x[k-1]. Daca aceste condiii nu

    sunt ndeplinite, la pasul k, acest lucru nseamn ca orice valori i-am atribui

    lui x[k+1], x[k+1], .. x[n] nu se va ajunge la o soluie rezultat.

  • 8/8/2019 Met Backtracking Bun

    5/28

    Metoda backtracking construiete un vector soluie n mod progresiv

    ncepnd cu prima component a vectorului i mergnd spre ultima cu

    eventuale reveniri asupra atribuirilor anterioare.

    Metoda se aplica astfel :

    1) se alege prima valoare sin S1 si I se atribuie lui x1 ;2) se presupun generate elementele x1x[k-1], cu valori din S1..S[k-1];

    pentru generarea lui x[k] se alege primul element din S[k] disponibil si

    pentru valoarea aleasa se testeaz ndeplinirea condiiilor de continuare.

    Pot aprea urmtoarele situaii :

    a) x[k] ndeplinete condiiile de continuare. Daca s-a ajuns la

    soluia final (k = n) atunci se afieaz soluia obinut. Daca nus-a ajuns la soluia final se trece la generarea elementului

    urmtor x [k-1];

    b) x[k] nu ndeplinete condiiile de continuare. Se ncearc

    urmtoarea valoare disponibila din S[k]. Daca nu se gsete nici

    o valoare n S[k] care s ndeplineasc condiiile de continuare,

    se revine la elementul x[k-1] i se reia algoritmul pentru o nou

    valoare a acestuia. Algoritmul se ncheie cnd au fost luate in

    considerare toate elementele lui S1.

    Problemele rezolvate prin aceast metod necesit timp mare de

    execuie, de aceea este indicat sa se foloseasc metoda numai daca nu avem

    alt algoritm de rezolvare.

    Dac mulimile S1,S2,Sn au acelai numr k de elemente, timpul

    necesar de execuie al algoritmului este k la n. Dac mulimile S1, S2.. Sn nuau acelai numr de elemente, atunci se noteaz cu m minimul cardinalelor

    mulimilor S1Sn si cu M, maximul. Timpul de execuie este situat n

    intervalul [m la n .. M la n]. Metoda backtracking are complexitatea

    exponenial, in cele mai multe cazuri fiind ineficient. Ea insa nu poate fi

    nlocuit cu alte variante de rezolvare mai rapide n situaia n care se cere

    determinarea tuturor soluiilor unei probleme.

  • 8/8/2019 Met Backtracking Bun

    6/28

    APLICAII REZOLVATE

    Exemple:

    Generarea permutrilor. Se citete un numr natural n. S se

    genereze toate permutrile mulimii {1, 2, 3, ,n}.

    Generarea permutrilor se va face innd cont c orice permutare va fi

    alctuit din elemente distincte ale mulimii A. Din acest motiv, la generarea

    unei permutri, vom urmri ca numerele s fie distincte.

    Prezentm algoritmul corespunztor cazului n=3:

    1 2 31 2 2 2 2

    1 1 1 1 1 1

    1 2 33 3 3 3 11 1 1 1 2 2

    1 2 3 11 1 1 2 3 32 2 2 2 2 2

    se ncarc n stiv pe nivelul 1 valoarea 1;

    ncrcarea valorii 1 pe nivelul al 2-lea nu este posibil, ntruct

    aceast valoare se gsete i pe nivelul 1 al stivei;

    ncrcarea valorii 2 pe nivelul al 2-lea este posibil, deoarece aceastvaloare nu mai este ntlnit;

    valoarea 1 din nivelul al 3-lea se regsete pe nivelul 1;

    valoarea 2 din nivelul al 3-lea se regsete pe nivelul al 2-lea;

    valoarea 3 pe nivelul al 3-lea nu e ntlnit pe nivelurile anterioare;

    ntruct nivelul 3 este completat corect. Tiprim: 1 2 3

  • 8/8/2019 Met Backtracking Bun

    7/28

    Algoritmul continu pn cnd stiva devine vid.

    Problema celor n dame. Fiind dat o tabl de ah n n se cer toate

    soluiile de aranjare a n dame, astfel nct s nu se afle dou dame pe aceeai

    linie, coloan sau diagonal (damele s nu se atace reciproc).

    Exemplu: Presupunnd c dispunem de o tabl de dimensiune 4 4, o

    soluie ar fi urmtoarea:

    D

    D

    D

    D

    Cum procedm? Observm c o dam trebuie s fie plasat singur pe

    linie. Plasm prima dam pe linia 1 coloana 1.

    D

    A doua dam nu poate fi aezat dect pe coloana a 3-a.

    D

    D

    Observm c a treia dam nu poate fi plasat n linia a 3-a. ncercm

    atunci plasarea celei de-a doua dame n coloana a 4-a.

    D

    D

  • 8/8/2019 Met Backtracking Bun

    8/28

    A treia dam nu poate fi plasat dect pe coloana a 2-a.

    D

    D

    D

    n aceast situaie dama a patra nu mai poate fi aezat. ncercnd s

    avansm cu dama a treia, observm c nu este posibil s o plasm nici n

    coloana a treia, nici n coloana a patra, deci o vom scoate de pe tabl. Dama adoua nu mai poate avansa, deci i ea este scoas de pe tabl. Avansm cu

    prima dam n coloana a doua.

    D

    A doua dam nu poate fi aezat dect n coloana a patra.

    D

    D

    Dama a treia se aeaz n prima coloan.

    D

    D

    D

  • 8/8/2019 Met Backtracking Bun

    9/28

    Acum este posibil s plasm a patra dam n coloana a treia i astfel am

    obinut o soluie a problemei.

    D

    D

    D

    D

    Algoritmul continu n acest mod pn cnd trebuie scoas de pe tabl

    prima dam.

    Pentru prezentarea unei soluii putem folosi un vector cu n componente

    (avnd n vedere c pe fiecare linie se gsete o singur dam). Exemplu:

    pentru soluia gsit avem vectorul st ce poate fi asimilat unei stive.

    Dou dame se gsesc pe aceeai diagonal dac i numai dac este

    ndeplinit condiia. |st (i) st (j)| = |i-j| : (diferena, n modul, ntre linii i

    coloane este aceeai).

    3 ST (4)

    1 ST (3) n general ST(i) = k semnificfaptul c pe linia i dama ocup

    poziia k.4 ST (2)

    2 ST (1)

    Exemplu: n tabla 4 4 avem situaia:

    DSt (1) = 1 i = 1;St (3) = 1 j = 3;| St (1) st (3) | = |1 3| = 2|i j| = |1 3| = 2

    D

    Sau situaia:

  • 8/8/2019 Met Backtracking Bun

    10/28

    DSt (1) = 3 i = 1;St (3) = 1 j = 3;| St (i) st (j) | = |3 1| = 2|i j| = |3 1| = 2

    D

    ntruct dou dame nu se pot gsi pe aceeai coloan, rezult c o

    soluie este sub form de permutare. O prim idee ne conduce la generarea

    tuturor permutrilor i la extragerea soluiilor pentru problem (ca dou dame

    s nu fie plasate n aceeai diagonal). A proceda astfel, nseamn s lucr

    conform strategiei backtracking. Aceasta presupune ca imediat ce am gsit

    dou dame care se atac, s relum cutarea. Fa de programul de generare a

    tuturor soluiilor problemei celor n dame, are o singur condiie suplimentar,

    n procedura valid.

    Produsul cartezian a n mulimi. Se dau mulimile de mai jos i se cere

    produsul cartezian al lor.

    A1 = {1, 2, 3, , k1}

    A2 = {1, 2, 3, , k2}

    An = {1, 2, 3, , kn}

    Exemplu: A1 = {1, 2}

    A2 = {1, 2, 3}

    A3 = {1, 2, 3}

    A1 A2 A3 = {(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 1), (1, 2, 2), (1, 2, 3),(1, 3, 1), (1, 3, 2), (1, 3, 3), (2, 1, 1), (2, 1, 2), (2, 1, 3), (2, 2, 1), (2, 2, 2), (2, 2,

    3), (2, 3, 1), (2, 3, 2), (2, 3, 3)}.

    Pentru rezolvare, se folosesc stiva ST i un vector A ce reine numerele

    k1, k2, kn. Utilizm metoda backtracking, uor modificat din urmtoarele

    motive:

  • 8/8/2019 Met Backtracking Bun

    11/28

    a) Orice element aflat la nivelul k al stivei este valid, motiv pentru care

    procedura valid nu face altceva dect s atribuie variabilei ev

    valoarea TRUE.

    b) Limita superioar pe nivelul k al stivei este dat de A(k).

    Modul de concepere a algoritmului rezult din cele ce urmeaz:

    1 2 3 1

    1 1 1 2 2

    1 1 1 1 1 1

    2 3 1 2 3

    2 2 3 3 3 3

    1 1 1 1 1 1

    Observaii:

    Algoritmul prezentat aici este de tip backtracking? ntrebarea are

    sens pentru c este absent mecanismul de ntoarcere. Vom admite c

    i aceasta este backtracking, dar degenerat.

    Generarea aranjamentelor. Se citesc n i p. S se genereze toate

    aranjamentele de n luate cte p.

    Din analiza problemei rezult urmtoarele:

    stiva are nlimea p;

    fiecare nivel ia valori ntre 1 i n;

    elementele plasate pe diverse niveluri trebuie s fie distincte.

    Algoritmul este asemntor cu cel de la permutri, cu deosebirea c aici

    stipa are nlimea p.

  • 8/8/2019 Met Backtracking Bun

    12/28

    Generarea combinrilor. Se citesc n i p numere naturale, np. Se

    cere s se genereze toate submulimile cu p elemente ale mulimii {1, 2, 3, ,

    n}.

    Pentru rezolvarea problemei trebuie inut cont de urmtoarele:

    stiva are nlimea p;elementele aflate pe niveluri diferite ale stivei trebuie s fie distincte;

    pentru a evita repetiia elementele se aeaz n ordine cresctoare: pe

    nivelul k se va afla o valoare mai mare dect pe nivelul k-1 i mai mic sau

    egal cu n-p+k.

    Problema comis-voiajorului. Un comis voiajor trebuie s viziteze un

    numr n de orae. Iniial, el se afl ntr-unul dintre ele, notat 1. Comis voiajorul dorete s nu treac de dou ori prin acelai ora, iar la ntoarcere s

    revin n oraul 1. Cunoscnd legturile existente ntre orae, se cere s se

    tipreasc toate drumurile posibile pe care le poate efectua comis voiajorul.

    Exemplu: n figura alturat sunt simbolizate cele 6 orae, precum i

    drumurile existente ntre ele.

    2 3

    1 4

    6 5

    Comis voiajorul are urmtoarele posibiliti de parcurgere:

    1, 2, 3, 4, 5, 6, 1;

    1, 2, 5, 4, 3, 6, 1;

    1, 6, 3, 4, 5, 2, 1;

    1, 6, 5, 4, 3, 2, 1;

  • 8/8/2019 Met Backtracking Bun

    13/28

    Legturile existente ntre orae sunt date n matricea An,n. Elementele

    matricei A pot fi 0 sau 1 (matricea este binar).

    1, dac exist drum ntre oraele i i j;

    A(i,j) =

    0 , altfelSe observ c A(i,j) = A(j,i), oricare ar fi i,j {1, 2, 3, , n} matricea

    este simetric.

    Pentru rezolvarea problemei folosim stiva st. la baza stivei (nivelul 1)

    se ncarc numrul 1. Prezentm n continuare modul de rezolvare a

    problemei.

    2 De la oraul 1 la oraul 2 exist drum, deci se va urca n stiv;1

    2Oraul 2 se mai gsete n stiv, deci nu este acceptat;2

    1

    3De la oraul 2 la oraul 3 se gsete drum; prin oraul 3 nu s-a mai

    trecut, deci oraul 3 este acceptat.21

    Algoritmul continu n acest mod pn se ajunge din nou la nivelul 1,

    caz n care algoritmul se ncheie.

    Un succesor, ntre 2 i n, aflat pe nivelul k al stivei, este considerat

    valid dac sunt ndeplinite urmtoarele condiii:

    nu s-a mai trecut prin oraul simbolizat de succesor, deci acesta nu

    se regsete n stiv;

    exist drum ntre oraul aflat la nivelul k-1 i cel aflat la nivelul k;

    dac succesorul se gsete la nivelul n, s existe drum de la el la

    oraul 1.

  • 8/8/2019 Met Backtracking Bun

    14/28

    Observaii:

    1. Problemele rezolvate prin aceast metod necesit un timp

    ndelungat de execuie. Din acest motiv este bine s utilizmmetoda atunci numai atunci cnd nu mai avem la dispoziie un

    alt algoritm mai eficient

    2. Menionm c nu exist probleme pentru care nu se cunosc

    algoritmi eficieni de rezolvare, deci backtracking este

    indicat.

    3. Rezolvarea iterativ ncalc principiul stivei atunci cnd

    verificm condiiile de continuare, sau atunci cnd tiprim

    soluia gsit, pentru c accesm orice nivel al stivei. Consider

    c o structur trebuie folosit ca atare atunci cnd este strict

    necesar. De exemplu, chiar i segmentul de stiv al

    calculatorului poate fi accesat oriunde. Asta nu nseamn c

    acolo nu se utilizeaz din plin mecanismul stivei.

  • 8/8/2019 Met Backtracking Bun

    15/28

    PROBLEMA COLORRII HARILOR

    Enun:

    Fiind dat o hart nu n ri, se cer toate soluiile de colorare a hrii,

    utiliznd cel mult patru culori, astfel nct dou ri de frontier comun s

    fie colorate diferit. Este demonstrat faptul c sunt suficiente numai patru

    culori pentru ca orice hart s poat fi colorat.

    Rezolvare:

    Pentru exemplificare, vom considera urmtoarea hart unde rile sunt

    numerotate cu cifre cuprinse ntre 1 i 5:

    O soluie a acestei probleme este urmtoarea:

    ara 1 culoarea 1

    ara 2 culoarea 2

    ara 3 culoarea 1;

    ara 4 culoarea 3;

    ara 5 culoarea 4;

    Harta este furnizat programului cu ajutorul unei matrice An,n

    1, dac ara i se nvecineaz cu ara j;

    A(i,j) =

    0 , altfel

    1

    2 3

    4

    5

  • 8/8/2019 Met Backtracking Bun

    16/28

  • 8/8/2019 Met Backtracking Bun

    17/28

    ev:false

    end;

    function solutie(k:integer):integer;

    begin

    solutie:=(k=n);

    end;

    procedure tipar;var

    i:integer;

    beginfor i:= 1 to n do

    writeln(Tara =, i,; culoarea=,st[i]);

    writeln(===================);

    end;

    begin

    write(Numarul de tari = );

    readln(n);for i:= 1 to n do

    for j:=1 to i-1 do

    beginwrite(a[,i,,,j,]=);

    readln(a[i,j])

    end;k:=1;

    init(k,st);

    while k>0 dobegin

    repeatsuccesor(as,st,k);

    if as

    then

    valid(ev,st,k);until (not as) or (as and ev);

    if asthen

    if solutie (k)

    thentipar

    else

    begink:=k+1;

  • 8/8/2019 Met Backtracking Bun

    18/28

    init(k,st)

    end

    elsek:=k-1

    end

    end.

    ConcepiaistrategiametodeiBACKTRACKING

    Metodaafostconceputpentruaevitagenerareatuturorsoluiilorposibile.

    nacestsens,metodafoloseteunarborevirtualconstruitastfel: nivelul0coninerdcinavirtualr; nivelul1coninecanoduri,elementelemulimiiS1,ncarecomponenta

    x1 ia valori,legturilemulimiietichetatecu1,2,, s1; nivelulk 2,coninecanodurielementelemulimiiSk,astfelcadinorice

    noddepenivelulk-1pleacexactsk muchii;nivelulconines1,sk noduri; nivelulnconines1 ... sn noduriterminale.

  • 8/8/2019 Met Backtracking Bun

    19/28

    r

    1 2.. s1

    x1 s1 noduri

    1 2s2 1 2 . . s2 1 2...s2 s1s2x2 noduri

    . . .

    . . .

    . . .

    xn

    s1sn

    1 2..sn 12. .sn 1 2sn noduri

    Arboreleataatspaiuluisoluiilorposibile.

    Metoda Backtracking utilizeaz arborele ataat soluiilor posibilepentrua

    generasoluiilerezultat,evitndgenerarea tuturorsoluiilorposibileprinverificarea condiiilordecontinuitate k(x1,,xk)

    Exemplu: Arborele ataat spaiului soluiilor posibile pentruproblema generriipermutrilormulimii{1,2,,n}:

    r

    1 2.. n

    x1 n noduri

    1 2.n 1 2 .. n 1 2...n n2

    x2 noduri

    . . .

    . . .

    . . .

    1 2..n 12. .n 1 2n nn

    xn noduri

    S1={1,2,n}; S2={1,2,n};Sn={1,2,n};|Sn|=n; Sn={1,2,,n}.

  • 8/8/2019 Met Backtracking Bun

    20/28

    k k

    Observaie: Generarea elementelorprodusului cartezian {1,,n}x x {1,,n}presupunegenerareantreguluispaiualsoluiilorposibile.

    Observaie:Osoluierezultatesteundrumdelardcinlaunnodterminal.

    Metoda va genera drumuri de la stnga la dreapta conformparcurgerii DF(depth, first) a arborilor (n adncime) i anume va generavectorul (x1,x2,,xn) astfel:

    componentelex1,x2,,xn primescpe rnd valori, adic mai ntix1, apoix2,

    , deci xk vorprimi valoare numai dac au fost deja stabilite valoripentrux1,x2,,xk-1;

    dac xk aprimit valoare, nu se trece la nivelul urmator ca s i seatribuie

    valoriluixk+1,frssetestezecondiiiledecontinuare k(x1,,xk);

    dac k(x1,,xk)=true,atuncisencearcssedeavaloripentruxk+1. dac k(x1,,xk)=false,atunci:

    a) vatrebuioaltalegerepentruxk,dacSk nus-aepuizatsau b) dacSk s-aepuizat,serevine lanivelul inferior(k-1)ixkprimeteo

    nou alegere, abandonndu-se un ntreg arbore (de aicidenumireametodei).

    x1

    x2 Observaie: n(x1,,xn)

    x3

    xk-1

    xk1 2 sk 1 2 sk 1 2 sk

    Proceduranerecursiv

    Implementareametodei

    INPUT :

    S = { 1, 2

    ,..., sk},k= 1,n,s = sk k k k k k

  • 8/8/2019 Met Backtracking Bun

    21/28

    k kvalorile

    0S

    cu proprietatea ca

    succ( 0)=

    k(x1,,xk)condiii decontinuare

    OUTPUT: (x1,,xn) soluii

    rezultat. ProcedureBACK;

    k1 {reprezintnivelulnarbore}xk k

    0 {valoaredestart}

    whilek>0do {segenereazdrumuri}ifk=k+1then {s-agsitosoluie}

    kk-1writex1,x2,,xn

    else{altsoluie}skifxk

  • 8/8/2019 Met Backtracking Bun

    22/28

    Utilizare:BACK(1);

    Exemplul1:Generareapermutrilormulimii{1,2,.n}

    programpermutari;var

    x:array[1..200]ofinteger;nr,i,n,k:integer;functioncol(k:integer):boolean;begin

    col:=true;fori:=1tok-1do

    ifx[i]=x[k]thenbegin

    col:=false;exit;

    end;

  • 8/8/2019 Met Backtracking Bun

    23/28

    begin

    write('n=');readln(n);

    nr:=0;

    k:=1;fori:=1tondox[i]:=0;

    whilek>0doifk=n+1then

    begink:=k-1;nr:=nr+1;writeln('solutianr',nr);fori:=1tondo

    write(x[i]:2);readln;

    endelse

    ifx[k]

  • 8/8/2019 Met Backtracking Bun

    24/28

    Observaii:pt.n=3seobin6soluii:123; 132; 213; 231; 312; 321.

    Exemplul 2: Problema celor n dame (regine). S se aeze cele 8 damepe otabl de ahptrat cu 8 linii i 8 coloane, astfel ca s nu se atace reciproc,adic s nu existe dou damepe aceeai linie, coloan sau diagonal. OricesoluierezultatX=(x1,,xn), xi=coloanapecareseafldamadepeliniai.

    Condiiiinterne:Fieiijdoudame:a) damelesnuseaflepeaceeaicoloanxi xj;i jb) snuseaflepediagonalaxi , xj

    (i,xi) (i,xi)

    (j,xj) (j,xj)

    j-i xj xi i-j xi -xj

    |i-j| |xi-xj|

  • 8/8/2019 Met Backtracking Bun

    25/28

    Programcele_8_regine;var

    x:array[1..200]ofinteger;nr,i,n,k:integer;

    functioncol(k:integer):boolean;begin

    col:=true;fori:=1tok-1do

    if(x[i]=x[k])or(abs(i-k)=abs(x[i]-x[k]))thenbegin

    col:=false;exit;

    end;

    begin

    end;

    write('n=');readln(n);nr:=0;k:=1;fori:=1tondo

    x[i]:=0;whilek>0do

    ifk=n+1thenbegin

    k:=k-1;nr:=nr+1;writeln('solutianr',nr);fori:=1tondo

    write(x[i]:2);readln;

    end

    elseifx[k]

  • 8/8/2019 Met Backtracking Bun

    26/28

    Exemplul3:Colorareagrafurilorhrilor:Fiecreihriisepoateataaungrafplanar.

    G=(Vi,E), Vi=mulimeanodurilor; E=mulimeamuchiilor;n=nr.deri; n=|V|nr.denoduri;c=nr.deculori;Sk={1,2,,c}; k=1,,n;Soluie:(x1,,xn),xi{1,,c}; xi=culoareaataatnoduluii.Gpoatefireprezentatprin:

    1aij0

    daca

    exista

    altfel

    muchie

    matriceadeadiacenA=||aij|| i=1,,n;j=1,,n;

    matriceamuchiilorxi xj,i j

    (x1,...,x

    k

    true

    )=

    false

    daca

    i,j{1,...,k},

    ij,

    altfel

    xi xj

    tari

    vecine

    Intrri: n=nr.denodurim=nr.demuchii

    (i,j)=muchiilec=nr.de

    culoriIeiri:(x1,x2,,xn),xi{1,,c},i=1,,n

    Programcolorare_harti;var

    a:array[1..30,1..30]of0..1;x:array[1..30]ofinteger;nr,i,j,n,m,k,c:integer;

    functioncont(k:integer):boolean;begin

    cont:=true;

  • 8/8/2019 Met Backtracking Bun

    27/28

    fori:=1tok-1doforj:=i+1tokdo

    if(a[i,j]=1)and(x[i]=x[j])thenbegin

    cont:=false;

    end;end;

    exit;

    begin

    write('nrdenoduri(tari):n=');readln(n);write('nr.demuchii(vecini):m=');readln(m);nr:=0;k:=1;fori:=1tondo

    forj:=1tondoa[i,j]:=0;

    writeln('introducetimuchiile(ij):');fori:=1tomdo

    begin

    end;

    readln(k,c);a[k,c]:=1;a[c,k]:=1;

    write('nr.deculoric=');readln(c);k:=1;fori:=1tondo

    x[i]:=0;whilek>0do

    ifk=n+1

    thenbegin

    k:=k-1;nr:=nr+1;writeln('solutianr',nr);fori:=1tondo

    write(x[i]:2);readln;

    endelse

    ifx[k]

  • 8/8/2019 Met Backtracking Bun

    28/28

    Bibliografie

    Cerchez, Emanuela, Programareain limbajul C++ pentru liceu. Volumul al II-lea: Metode si

    tehnici de programare, Editura POLIROM, Bucuresti, 2005

    Socaciu, Tiberiu ; Backtracking. Teorie si exemple, Vol. 1 C, Editura InfoData, Bucuresti, 2005