 |  |
|
Algoritmii de tip backtracking se
aplica la problemele unde spatiul solutiilor S este de forma
unui produs cartezian S = S0 × S1 × × Sn-1.
Orice element x din spatiul solutiilor
Nu toate elementele xIS sunt solutii valide ale problemei. Doar acele elemente x care satisfac anumite conditii impuse de problema vor fi solutii valide. Definim conditiile care trebuie satisfacute sub forma unei functii booleene Solutie(x0,x1,,xn-1). Un element x=(x0, x1, , xn-1) I S este solutie a problemei daca functia Solutie aplicata componentelor lui x va returna valoarea true.
Scopul este de a gasi acei vectori xIS pentru care functia Solutie returneaza true.
Modul de lucru al algoritmului
este urmatorul: se alege un element x00 din S0,
apoi un element x10 din S1, apoi un element x20
din S2, s.a.m.d, pana cand se va fi ales un element xn-10
din Sn-1. In acest moment vom avea un vector x = (x00,
x10, , xn-20, xn-10)
I
Aplicam principiul revenirii pe cale, adica ne intoarcem cu un pas in urma, inainte de alegerea elementului xn-10 ISn-1. De aici continuam alegand un alt element xn-11 ISn-1, xn-11 ≠ xn-10. Vom obtine un nou vector x' = (x00,x10,,xn-20,xn-11) IS asupra caruia aplicam din nou functia Solutie. Daca rezultatul este false, revenim din nou cu un pas in urma si continuam cu alegerea unui alt element xn-12 ISn-1, xn-12 ≠ xn-10 si xn-12 ≠ xn-11. Repetam acesti pasi pana la epuizarea tuturor elementelor din Sn-1.
Dupa ce am epuizat toate elementele multimii Sn-1, vom fi la faza in care am ales elementele x00, x10, , xn-20. Ar trebui sa alegem un element din Sn-1, dar cum toate elementele din Sn-1 au fost deja alese, revenim cu inca un pas in urma pe cale, si alegem un alt element xn-21 ISn-2. Pe urma reincepem alegerea elementelor din Sn-1 cu primul dintre ele, xn-10 ISn-1. Vom avea vectorul x = (x00, x10,, xn-30, xn-21, xn-10).
Procedand in
acest mod, vom ajunge practic sa construim toti vectorii xI
S,
adica vom explora intreg spatiul solutiilor posibile.
Exista in principiu doua categorii de probleme: unele care cer
gasirea unei singure solutii si unele care cer gasirea
tuturor solutiilor. Atunci cand se cere gasirea unei singure solutii,
putem opri cautarea dupa gasirea primului vector x pentru care
functia Solutie returneaza
valoarea true. La cealalta categorie de probleme este nevoie sa
parcurgem intreg spatiul solutiilor pentru a gasi toate
solutiile.
Parcurgerea intregului spatiu al solutiilor posibile este foarte mare consumatoare de timp. In general se poate accelera aceasta parcurgere prin urmatoarea optimizare: pornind de la functia Solutie(x0, x1, , xn-1), definim o functie Continuare(x0, x1, , xk) care sa ne spuna daca, avand alese la un moment dat elementele x0, x1, , xk exista o sansa de a se ajunge la o solutie. Aceasta optimizare este foarte utila deoarece de multe ori dupa alegerea catorva elemente x0, x1, , xk ne putem da seama ca nu vom putea gasi nici o solutie valida care contine elementele respective. In asemenea situatii nu mai are rost sa continuam alegerea de elemente pana la xn-1, ci putem direct sa revenim cu un pas in urma pe cale si sa incercam cu un alt element xk'.
Algoritmul backtracking redactat sub forma de pseudocod arata in felul urmator:
k = 0;
while (k >= 0)
while ( !Continuare(x[1], x[2], , x[k]) &&
(* mai sunt elemente de ales din multimea S[k]) )
if (Continuare(x[1], x[2], , x[k]))
else
}
else
}
Daca analizam modul de functionare al algoritmului backtracking, vom vedea ca la orice moment de timp ne este suficient un tablou de n elemente pentru a memora elementele x0, x1, , xn-1 alese. Ca urmare in implementare declaram un tablou x de dimensiune n. Tipul de date al tabloului depinde de problema, de tipul multimilor S.
Variabila k ne indica indicele multimii din care urmeaza sa alegem un element. La inceput de tot trebuie sa alegem un element din multimea S0, de aceea il initializam pe k cu valoarea 0. Pe urma k se modifica in functie de modul in care avansam sau revenim pe calea de cautare.
Pentru alegerea urmatorului xk din multimea Sk, ne bazam pe faptul ca intre elementele fiecarei multimi Sk exista o relatie de ordine. Daca inca nu s-a ales nici un element din multimea Sk atunci il alegem pe primul conform relatiei de ordine. Daca deja s-a ales cel putin un element, atunci il alegem pe urmatorul neales, conform relatiei de ordine.
Enunt Avem o tabla de sah de dimensiune 8x8. Sa se gaseasca toate modalitatile de a deplasa un cal pe aceasta tabla, astfel incat calul sa treaca prin toate casutele de pe tabla exact o data.
Rezolvare Pentru a parcurge fiecare casuta de pe tabla de sah exact o data, calul va trebui sa faca exact 8 × 8 = 64 de pasi. La fiecare pas el poate alege oricare din cele 64 de casute de pe tabla. Sa codificam casutele de pe tabla de sah in modul urmator: casuta de la linia i si coloana j o notam prin perechea (i,j). Sa notam multimea tuturor casutelor de pe tabla cu C: C = .
O solutie a problemei o putem nota printr-un vector x = (x0, x1, , x63), unde xIS = C × C × C × × C (produs cartezian in care multimea C apare de 64 de ori), iar xi IC, i I.
Cu aceste elemente putem vedea ca se poate aplica o rezolvare de tip backtracking. Functia Solutie va verifica sa nu existe doua elemente ci si cj care au aceeasi valoare, deoarece asta ar insemna ca s-a trecut de doua ori prin aceeasi casuta. In plus functia mai trebuie sa verifice faptul ca i I calul poate sari de la casuta ci la casuta ci+1. Asta inseamna ca fie ci si ci+1 se afla la doua linii distanta si la o coloana distanta, fie ele se afla la o linie distanta si la doua coloane distanta.
Functia Continuare trebuie sa faca exact aceleasi verificari ca si functia Solutie, dar nu pentru toate 64 de casute ci pentru cele k casute care au fost alese pana la un moment dat.
Cod sursa In continuare prezentam codul sursa pentru rezolvarea acestei probleme.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
/* Dimensiunea tablei de sah
definita ca si
Pentru o tabla de dimensiune 8x8 gasirea solutiilor
dureaza foarte mult, de aceea lucram pe o tabla de
5x5 unde solutiile sunt gasite mult mai repede. */
#define N 5
#define INVALID -1
int main(void)
k = 0;
while (k >= 0)
/* Daca elementul 'c[k]' nu este setat
pe invalid, inseamna ca deja am ales
o casuta din multimea 'C[k]'. Acum
alegem urmatoarea casuta de pe tabla.
Cu alte cuvinte incercam sa plasam
calul in urmatoarea casuta. Daca este
posibil incercam sa ramanem pe aceeasi
linie si sa ne deplasam cu o coloana
spre dreapta. */
else if (c[k][1] < N-1)
/* Daca cumva eram chiar la ultima casuta
din linie, atunci alegem prima casuta
din linia urmatoare. Ne asiguram ca nu
eram cumva si pe ultima linie a
tablei, caz in care am epuizat toate
casutele. */
else if (c[k][0] < N-1)
/* Daca eram pe ultima linie a tablei,
atunci am epuizat toate casutele.
Marcam acest lucru setand variabila
'pe_tabla' pe 0. */
else
/* Daca casuta 'c[k]' aleasa este valida
(se afla pe tabla de joc), atunci
trecem la calculul functiei
'Continuare'. */
if (pe_tabla)
}
}
/* Daca casuta 'c[k]' aleasa este in
afara tablei de sah, atunci functia
'Continuare' va returna automat
'false'. */
else
}
while (!continuare && pe_tabla);
/* Daca am obtinut rezultat pozitiv in urma
verificarilor de 'Continuare', atunci
consideram piesa asezata la pozitia 'c[k]'
si continuam cautarea. */
if (continuare)
/* Daca nu s-a parcurs inca toata tabla
atunci trecem cu un pas inainte pe
calea de cautare. */
else
}
/* Daca casuta aleasa nu este valida, atunci
marcam elementul 'c[k]' cu INVALID si
revenim cu un pas inapoi pe calea de
cautare. */
else
}
printf('%d solutiin', count);
return 0;
}
Optimizare Putem face o optimizare la programul prezentat, pornind de la faptul ca se cunosc regulile dupa care se poate deplasa calul pe tabla de sah. La alegerea din multimea Ck, in loc sa alegem pe rand fiecare casuta si apoi sa verificam daca s-ar putea face mutare in casuta respectiva, e mai eficient sa alegem direct dintre casutele in care se poate face mutare. Pentru a putea determina aceste casute, folosim doi vectori care definesc mutarile posibile ale calului (numarul de casute cu care se poate deplasa pe orizontala si pe verticala). Prezentam mai jos codul sursa care implementeaza aceasta optimizare. Implementarea este una recursiva, pentru a arata ca modul de lucru al algoritmului backtracking se preteaza in mod natural la implementari recursive.
#include <stdio.h>
#include <conio.h>
#define N 5
int dx[8] = ;
int dy[8] = ;
int c[N*N][2];
int count = 0;
void back(int pas)
else
if (continuare)
back(pas+1);
}
}
}
}
int main(void)
printf('%d solutiin', count);
return 0;
}
Sa se scrie un program care gaseste toate caile de iesire dintr-un labirint.
Configuratia labirintului se citeste din fisierul text "labirint.dat". Labirintul are forma unei matrici de dimensiune NxM. Un element al matricii poate fi perete sau spatiu liber. In fisierul de intrare labirintul este descris pe N linii de cate M caractere. Peretele se codifica prin litera 'P', iar spatiul liber prin caracterul .
Un exemplu de fisier de intrare care descrie un labirint este:
PPPP.PPP
P.PPP
PP..PPSP
PP.PP..P
P..PP.PP
P.PPP..P
PPP.P
PPP.PP.P
PPP.P
PPPPPPPP
In afara de caracterele 'P' si , in fisierul de intrare va mai apare si caracterul 'S', o singura data. Caracterul 'S' reprezinta un spatiu liber in labirint si marcheaza punctul de unde incepem cautarea iesirilor.
Deplasarea se poate face doar pe verticala si pe orizontala intre oricare doua celule invecinate, cu conditia ca ambele celule sa fie spatii libere. Nu este permis sa se treaca de mai multe ori prin aceeasi celula.
Pentru fiecare cale de iesire gasita, programul trebuie sa afiseze aceasta cale pe ecran, dupa care va astepta apasarea unei taste. Dupa apasarea unei taste se va trece la urmatoarea cale de iesire gasita, s.a.m.d. Pentru afisarea unei cai de iesire se va folosi aceeasi codificare ca si cea din fisierul de intrare, cu diferenta ca se va marca drumul de iesire prin caracterul 'x'.
Spre exemplu un drum de iesire posibil pentru labirintul de mai sus este:
PPPPxPPP
P.xxxPPP
PPx.PPSP
PPxPPxxP
PxxPPxPP
PxPPPxxP
PxxxPPxP
PPPxPPxP
PPPxxxxP
PPPPPPPP
Daca nu exista nici un drum de iesire din labirint, programul va afisa mesajul "Nu avem nici un drum de iesire."
Un labirint va avea maxim 24 de linii si 80 de coloane. Valorile pentru N si M nu sunt date explicit, va trebui sa le deduceti din structura fisierului de intrare. Se garanteaza ca datele de intrare sunt corecte.
Pentru problema anterioara sa se determine si sa se afiseze pe ecran doar cel mai scurt drum de iesire din labirint.
Avem o tabla de sah de dimensiune 8x8. Sa se aseze pe aceasta tabla de sah 8 regine astfel incat sa nu existe doua regine care se ataca intre ele.
Implementarea trebuie sa fie facuta folosind recursivitatea.
Acest document nu se poate descarca
| E posibil sa te intereseze alte documente despre: |
| Copyright © 2024 - Toate drepturile rezervate QReferat.com | Folositi documentele afisate ca sursa de inspiratie. Va recomandam sa nu copiati textul, ci sa compuneti propriul document pe baza informatiilor de pe site. { Home } { Contact } { Termeni si conditii } |
Documente similare:
|
Cauta document |