Backtracking
Backtracking sau "algoritmul cu revenire" este un algoritm exponential, ce ajuta la rezolvarea unor probleme cu aproape o infinitate de solutii (de unde si clasificarea de algoritm exponential).
Problema cea mai simpla pentru prezentarea algoritmului backtracking este aceea a ge 222t1917c nerarii permutarilor multimii numerelor de la 1 la n, cu n numar natural pozitiv introdus de la tastatura. Pentru acesta se genereaza toate combinatiile de numere distincte de la 1 la n.
Exemplu: Pentru n=3 se genereaza solutiile 123, 132, 213, 231, 312, 321.
Mai jos sunt prezentate programele de rezolvare a problemei in limbajele Turbo Pascal si C++.
Programul in limbajul Turbo Pascal
program permutari;
var
st: array[1..10] of integer;
i,j,n: integer;
c: longint;
procedure initializare;
begin
for i:=1 to n do
st[i]:=0;
end;
function valid (var p: integer): boolean;
var
sol: boolean;
begin
sol:=true;
for i:=1 to p do
for j:=i+1 to p do
if st[i]=st[j] then
sol:=false;
valid:=sol;
end;
procedure tipar;
begin
c:=c+1;
write(c:10,' ');
for i:=1 to n do
write(st[i]);
writeln;
end;
procedure bckt(p: integer);
var
val: integer;
begin
for val:=1 to n do
begin
st[p] := val;
if ( valid(p) ) then
if (p=n) then
tipar
else
bckt(p+1);
end;
end;
begin
write('Introduceti un numar: ');
readln(n);
initializare;
c:=0;
bckt(1);
writeln('Exista ',c,' solutii!');
readln;
end.
Programul in limbajul C++
#include "iostream.h"
#include "conio.h"
int n, st[10];
void initializare() // initializeaza stiva si citeste n
void tipar(int p) // tipareste o solutie memorata in vectorul st
int valid (int p)
// testeaza daca valoarea pusa pe nivelul p genereaza o solutie valida,
// returnind 1 sau 0
void bktr (int p) // algoritmul backtracking
void main()
Saritura calului pe tabla de sah
O alta problema clasica este aceea a sariturii calului pe o tabla de sah: Se cere sa se gaseasca un traseu complet care acopera tabla de sah, generat adoptind saritura calului fara a trece de doua ori prin aceeasi pozitie. Iata programul in limbajul C++.
#include "iostream.h"
#include "conio.h"
int n, st[9][9], solutie, tip;
void initializare() // initializeaza matricea
void tipar() //
}
else
if (solutie%50==0)
cout << "-";
int valid ()
// testeaza daca valoarea pusa pe nivelul p genereaza o solutie valida,
// returnind 1 sau 0
posibil=1;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
if (st[i][j]==0)
posibil=0;
return (posibil);
void sterge(int val)
void bktr (int a, int b, int val) //
}
else
}
}
void main()
}
if (solutie==0)
cout << "Nu exista solutii!";
else
cout << "Exista " << solutie << " solutii!";
getch();
|
