Backtracking cu miscari

Backtracking cu miscari

Principii de modificare a algoritmului

Problemele cu miscari sunt de genul celor in care se cere sa se gaseasca unul sau mai multe trasee
intre doua pozitii. In cazul acestor probleme se specifica regulile de miscare. Uzual, acestea sunt
sus, jos, stanga, dreapta sau nord, nordest, est, sudest, sud, sudvest, vest, nordvest in cazul
caroiajelor rectangulare. De remarcat ca fiecare miscare trebuie sa aiba atasata si o miscare 'inapoi'
pentru a putea implementa backtracking-ul. Prin urmare, solutia se va retine ca un sir de miscari si
nu ca un sir de pozitii. De asemenea, este necesar de a retine la fiecare miscare pozitia curenta, iar la
miscarile 'inapoi' sa se refaca contextul dinainte.

Problema circuitului hamiltonian a calului pe tabla de sah

Enuntul si consideratii

Problema: Sa se determine toate circuitele hamiltoniene ale unui cal pe o tabla de sah de
dimensiuni n x n.

Rezolvare: Miscarile calului sub forma de deplasamente relative sunt:

M =

Vom retine pe o matrice a[n, n], initial nula, numarul pasului curent facut de cal. De exemplu, la un
moment dat, matricea ar putea fi ceva de genul:

Pentru ca circuitul calului sa fie unul hamiltonian, vom pune ca si conditie de validare a unei mutari

70

ca pozitia destinatie sa nu fie deja ocupata . Evident, se va tine cont si de faptul ca o mutare este
valida prin testarea integritatii indicilor de matrice .

Programul in limbajul Pascal

program circuitul_hamiltonian_al_calului;

var n: byte;

var a: array [1..100, 1..100] of integer;

var m: array [1..8] of record x, y: integer end;
procedure initmiscari;
begin

function este_in_tabla (xinitial, yinitial, miscare: integer;
var xfinal, yfinal: integer): boolean;
begin

if (miscare < 1) or (miscare > 8) then

este_in_tabla := false
else
begin

xfinal := xinitial + m [miscare]. x;
yfinal := yinitial + m [miscare]. y;
este_in_tabla := (xfinal >= 1) and (xfinal <= n)

and (yfinal >= 1) and (yfinal <= n)
end
end;

function este_liber (i, j, level: integer): boolean;
begin

if level = n * n then

este_liber := a[i][j] = 1

else

este_liber := a[i][j] = 0
end;

procedure prelucreaza_solutie;
var i, j: integer;
begin

for i := 1 to n do
begin

for j

write
writeln
end;
writeln
end;

procedure btr (icurent, jcurent, level: integer);
var inou, jnou, i: integer;
begin

if level n n then

prelucreaza_solutie
else
begin

a [icurent] [jcurent] level;
for i to do

if este_in_tabla (icurent, jcurent, i, inou, jnou) then
if este_liber (inou, jnou, level) then
btr (inou, jnou, level
a [icurent] [jcurent] end
end;

procedure inita;

var i, j: integer;
begin

for i := 1 to n do
for j := 1 to n do
a [i] [j]

end;

begin
n initmiscari;
inita;

writeln ('Determinarea
tabla de ', n x n)

btr end.

2.3. Programul in limbajul C

include <stdio.h>

define TRUE

define FALSE

// dimensiunea tablei

int n, x[100], a[100][100];
// miscari

int mx [] = ;
int my [] = ;

// verifica daca o miscare este sau nu in afara tablei
int este_in_tabla (int xinitial, int yinitial, int miscare,
int *xfinal, int *yfinal)

// verifica daca un patrat este liber pentru nivelul level

int este_liber (int i, int j, int level)

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie ()

backtracking implementarea recursiva
void btr (int icurent, int jcurent, int level)

// s-au completat cele n * n patrate

void main ()

2. Exercitii si probleme

Exista solutii pentru N = 8?

Cum verificam faptul ca avem un cicuit ?

Unde este sirul P?

Unde este implementata functia FI?

Unde se afla vectorul X?

2.5. Rezolvarea exercitiilor si problemelor

Ruland programul, rezulta ca da.

In primul rand prin impunerea lui a [1][1] = 1 (pentru a nu numara de doua ori un circuit, in
functie de punctul de pornire) si in al doilea rand prin verificarea inchiderii drumului (in functia
ESTE_LIBER).

Deoarece toate multimile M_i sunt identice, iar cardinalul este 8, peste tot in surse s-a
modificat cu 8 referirea la oricare element al sirului P.

Functia FI este ascunsa in spatele a doua functii: ESTE_IN_TABLA si ESTE_LIBER. Practic,
FI = ESTE_IN_TABLA AND ESTE_LIBER, cu mentiunea ca ESTE_LIBER implementeaza si
testul final de circuit.

5. Valorile vectorului X sunt memorate implicit pe stiva de executie ca variabila I din bucla FOR.
S-a renuntat la folosirea explicita a lui X pentru ca nicaieri in codul programului nu era nevoie
de aceasta valoare, chiar si evaluarile FI fiind facute pe matricea A.

3. Problema labirintului

Enuntul si consideratii

Problema: Se considera un labirint. Se cere sa se determine toate drumurile care duc de la o pozitie
initiala (intrarea in labirint) la o pozitie finala (iesirea din labirint). Labirintul se da sub forma unei
matrici binare in care 0 reprezinta cale de acces, iar 1 reprezinta zid. Miscarile pot fi de tipul sus,
jos, stanga, dreapta.

Rezolvare: Miscarile in cadrul matricei sub forma de deplasamente relative sunt:

M =

In matricea initiala vom marca cu valori negative pasii pe care ii face algoritmul in gasirea solutiei
cu mentiunea ca se va pastra principiul de restaurare a contextului.

Programul in limbajul Pascal

program labirint_matricial;

var n1, n2: byte;

var a: array of integer;
var x0, y0, xf, yf: integer;

var m: array [1..4] of record x, y: integer end;
procedure initmiscari;
begin

function este_in_tabla (xinitial, yinitial, miscare: integer;
var xfinal, yfinal: integer): boolean;
begin

if (miscare < 1) or (miscare > 4) then

este_in_tabla := false
else
begin

xfinal := xinitial + m [miscare]. x;
yfinal := yinitial + m [miscare]. y;
este_in_tabla := (xfinal >= 1) and (xfinal <= n1)

and (yfinal >= 1) and (yfinal <= n2)
end
end;

function este_liber (i, j, level: integer): boolean;
begin

este_liber := (a[i][j] = 0)
end;

function este_gata (i, j, level: integer): boolean;
begin

este_gata := ((i = xf) and (j = yf))
end;

procedure prelucreaza_solutie;
var i, j: integer;
begin

for i := 1 to n1 do
begin

for j to n2 do

write (a [i][j]:3);
writeln
end;
writeln
end;

procedure btr (icurent, jcurent, level: integer);
var inou, jnou, i: integer;
begin

a [icurent] [jcurent] -level;
for i to do

if este_in_tabla (icurent, jcurent, i, inou, jnou) then
if este_gata (inou, jnou, level) then
begin

a [inou] [jnou] -level prelucreaza_solutie;
a [inou] [jnou] end

else if este_liber (inou, jnou, level) then
btr (inou, jnou, level
a [icurent] [jcurent]

end;

procedure inita;

var i, j: integer;
begin

write ('n1=');
read (n1);
write ('n2=');
read (n2);
for i to n1 do
for j to n2 do
begin

write ('a[', i, j,

read (a [i] [j])
end;
write ('x0=');
read (x0);
write ('y0=');
read (y0);
write ('xf=');
read (xf);
write ('yf=');
read (yf);
a [x0] [y0] a [xf] [yf] end;

begin

initmiscari;
inita;

writeln ('Determinarea iesirilor dintr-un labirint ', n1 x
n2);

btr x0, y0)
end.

3.3. Programul in limbajul C

include <stdio.h>

define TRUE

define FALSE

// dimensiunea matricei

int n1, n2, x0, y0, xf, yf, a[100][100];
miscari

int mx int my

// verifica daca o miscare este sau nu in afara tablei
int este_in_tabla (int xinitial, int yinitial, int miscare,
int *xfinal, int *yfinal)

if ((miscare < l) jj (miscare > 4))

return FALSE;
else
i

*xfinal xinitial mx [miscare];
*yfinal yinitial my [miscare];
return (*xfinal >= l) SS (*xfinal <= nl)
SS (*yfinal >= l) SS (*yfinal <= n2);

j

j

verifica daca un patrat este liber pentru nivelul level
int este_liber (int i, int j, int level)
i

return (a[i][j] O);
j

verifica daca am ajuns la capat
int este_gata (int i, int j, int level)
i

return ((i xf) SS (j yf));

j

// prelucrarea unei solutii x de dimensiune n
void prelucreaza_solutie ()
i

for (int i = l; i <= nl; i++)
i

for (int j = l; j <= n2; j++)
printf ('%Sd a[i][j]);

printf ('n');
j

printf ('n');
j

backtracking implementarea recursiva
void btr (int icurent, int jcurent, int level)
i

int inou, jnou;

marchez mutarea la nivelul curent
a [icurent] [jcurent] = -level;
for (int i = l; i <= 4; i++)

if (este_in_tabla (icurent, jcurent, i, Sinou, Sjnou))
if (este_gata (inou, jnou, level))

i

a [inou] [jnou] = -level -l;
prelucreaza_solutie ();

a [inou] [jnou] = O;
j

else if (este_liber (inou, jnou, level))
btr (inou, jnou, level + l);
// refac contextul

a [icurent] [jcurent] = 0;
}

void main ()

printf ('x0=');
scanf ('%d', &x0);
printf ('y0=');
scanf ('%d', &y0);
printf ('xf=');
scanf ('%d', &xf);
printf ('yf=');
scanf ('%d', &yf);

btr (1, x0, y0);

3. Exercitii si probleme

De ce se face atribuirea

a [icurent] [jcurent] = -level;

Identificati functia FI si FFI, vectorii P si X din algoritmul backtracking cu solutii variabile.

Modificati functia de afisare, astfel incat unde este zid sa se afiseze 'X', unde este drum sa se
afiseze '.', pozitia initiala sa se marcheze cu 'I', cea finala cu 'F', iar unde este drum nefolosit sa
se puna ' '

3.5. Rezolvarea exercitiilor si problemelor

Este marca prin care se pastreaza urma in cadrul matricii. S-au ales valori negative pentru a nu
interfera cu valorile 0 si 1 din matricea initiala.

Avem:

FI = ESTE_IN_TABELA AND ESTE_LIBER
FFI = ESTE_IN_TABELA AND ESTE_GATA
P = 4

X = variabila I

in limbajul Pascal:

procedure prelucreaza_solutie;
var i, j: integer;
begin

for i := 1 to n1 do
begin

for j := 1 to n2 do

if (i = x0) and (j = y0) then

write ('I')
if (i = xf) and (j = yf) then

write ('F')
else if a [i][j] then

write else if a [i][j] then

write ('X')
else

write writeln
end;
writeln
end;

in limbajul C:

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie

printf ('n');

Probleme de coborare

1. Enuntul si consideratii

Problema: Fie o matrice in care valorile elementelor reprezinta cotele medii din relief de pe o harta
caroiata. Se lanseaza o bila de pe pozitia (i, j). Care sunt traseele posibile ale bilei, stiind ca ea se

poate deplasa in oricare din cele 8 pozitii invecinate cu conditia ca respectiva pozitie sa aiba cota
mai strict mai mica.

Rezolvare: Miscarile in cadrul matricei sub forma de deplasamente relative sunt:

M =
Intr-o matrice B vom pastra traseul bilei, iar matricea initiala A va ramane nemodificata.

2. Programul in limbajul Pascal

program coborare;

var n1, n2: byte;

var a, b: array of integer;
var x0, y0: integer;

var m: array [1..8] of record x, y: integer end;
procedure initmiscari;
begin

function este_in_tabla (xinitial, yinitial, miscare: integer;
var xfinal, yfinal: integer): boolean;
begin

if (miscare < 1) or (miscare > 8) then

este_in_tabla := false
else
begin

xfinal := xinitial + m [miscare]. x;
yfinal := yinitial + m [miscare]. y;
este_in_tabla := (xfinal >= 1) and (xfinal <= n1)

and (yfinal >= 1) and (yfinal <= n2)
end

end;

function este_liber (i, j, h: integer): boolean;
begin

este_liber (b [i] [j] and (a [i] [j] < h)
end;

function este_gata (i, j, level: integer): boolean;
begin

este_gata ((i or (j or (i n1) or (j n2))
end;

procedure prelucreaza_solutie;
var i, j: integer;
begin

for i := 1 to n1 do
begin

for j := 1 to n2 do

write (a [i][j]:3);
for j := 1 to n2 do

write (b [i][j]:3);
writeln
end;
writeln
end;

procedure btr (icurent, jcurent, level: integer);
var inou, jnou, i: integer;
begin

b [icurent] [jcurent] level;
for i to do

if este_in_tabla (icurent, jcurent, i, inou, jnou) then
if este_gata (inou, jnou, level) then
begin

b [inou] [jnou] level prelucreaza_solutie;
b [inou] [jnou] end

else if este_liber (inou, jnou, a [icurent][jcurent]) then
btr (inou, jnou, level
b [icurent] [jcurent] end;

procedure inita;

var i, j: integer;
begin

write ('n1=');

read (n1);
write ('n2=');
read (n2);
for i := 1 to n1 do
for j := 1 to n2 do
begin

write ('a[', i, j,

read (a [i] [j]);
b [i] [j] end;
write ('x0=');
read (x0);
write ('y0=');
read (y0);
b [x0] [y0] end;

begin

initmiscari;
inita;

writeln ('Coborarea pe o harta n1 x n2);
btr (x0, y0, end.

3. Programul in limbajul C

include <stdio.h>

define TRUE 1

define FALSE 0

// dimensiunea matricei

int n1, n2, x0, y0, b[100][100], a[100][100];
// miscari

int mx [] = ;
int my [] = ;

// verifica daca o miscare este sau nu in afara tablei
int este_in_tabla (int xinitial, int yinitial, int miscare,
int *xfinal, int *yfinal)

II verifica daca un patrat este liber pentru nivelul level
int este_liber (int i, int j, int h)
i

return ((b [i] [j] == 0) && (a [i] [j] < h));
j

Il verifica daca am ajuns la capat
int este_gata (int i, int j, int level)
i

return ((i == 1) jj (j == 1) jj (i == n1) jj (j == n2));
j

II prelucrarea unei solutii x de dimensiune n
void prelucreaza_solutie ()
i

for (int i i <= n1; i++)
i

for (int j = 1; j <= n2; j++)

printf ('%3d ', a[i][j]);
for (j = 1; j <= n2; j++)
printf ('%3d ', b[i][j]);

printf ('n');
j

printf ('n');
j

II backtracking implementarea recursiva
void btr (int icurent, int jcurent, int level)
i

int inou, jnou;

Il marchez mutarea la nivelul curent
b [icurent] [jcurent] = level;
for (int i i <= B; i++)

if (este_in_tabla (icurent, jcurent, i, &inou, &jnou))
if (este_gata (inou, jnou, level))

i

b [inou] [jnou] = level + 1;
prelucreaza_solutie ();

b [inou] [jnou] = 0;
j

else if (este_liber (inou, jnou, a [icurent][jcurent
btr (inou, jnou, level + 1);
II refac contextul

b [icurent] [jcurent] = 0;
j

void main i

printf ('Coborarea pe o harta %d x %dn', n1, n2);
printf ('n1=');
scanf ('%d', &n1);
printf ('n2=');

scanf ('%d', &n2);

for (int i = 1; i <= n1; i++)

for (int j = 1; j <= n2; j++)

printf ('x0=');
scanf ('%d', &x0);
printf ('y0=');
scanf ('%d', &y0);

btr (x0, y0, 1);

Exercitii si probleme

1. Imaginati-va o rezolvare care implica eliminarea folosirii testului ESTE_IN_TABLA.

5. Rezolvarea exercitiilor si problemelor

1. Solutia ar fi bordarea matricii cu doua linii suplimentare (o prima si ultima linie), precum si
bordarea cu doua coloane suplimentare (o prima si ultima coloana). Toate valorile acestor elemente
partial introduse trebuie sa fie suficient de 'mari' .