QReferate - referate pentru educatia ta.
Referatele noastre - sursa ta de inspiratie! Referate oferite gratuit, lucrari si proiecte cu imagini si grafice. Fiecare referat, proiect sau comentariu il poti downloada rapid si il poti folosi pentru temele tale de acasa.



AdministratieAlimentatieArta culturaAsistenta socialaAstronomie
BiologieChimieComunicareConstructiiCosmetica
DesenDiverseDreptEconomieEngleza
FilozofieFizicaFrancezaGeografieGermana
InformaticaIstorieLatinaManagementMarketing
MatematicaMecanicaMedicinaPedagogiePsihologie
RomanaStiinte politiceTransporturiTurism
Esti aici: Qreferat » Referate informatica

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[1] 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:

7 2 5
4 0 0
1 6 3

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[2].

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

m

[1]

x

:=

1;

m

[1]

y

:=

2;

m

[2]

x

:=

-1;

m

[2]

y

:=

2;

m

[3]

x

:=

1;

m

[3]

y

:=

-2;

m

[4]

x

:=

-1;

m

[4]

y

:=

-2;

m

[5]

x

:=

2;

m

[5]

y

:=

1;

m

[6]

x

:=

2;

m

[6]

y

:=

-1;

m

[7]

x

:=

-2;

m

[7]

y

:=

1;

m

[8]

x

:=

-2;

m

[8]

y

:=

-1;

end;



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


= 1 to n do
(a [i][j]:3);



for j :

write
writeln
end;
writeln
end;


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


if level = n * n + 1 then

prelucreaza_solutie
else
begin


a [icurent] [jcurent] := level;
for i
:= 1 to 8 do

if este_in_tabla (icurent, jcurent, i, inou, jnou) then
if este_liber (inou, jnou, level) then
btr (inou, jnou, level
+ 1);

a [icurent] [jcurent]
:= 0
end
end;

procedure inita;

var i, j: integer;
begin

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

end;

begin
n
:= 8;
initmiscari;
inita;

circuitelor hamiltoniene ale calului pe

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

btr (1, 1, 1)
end.

2.3. Programul in limbajul C

include <stdio.h>

define TRUE 1

define FALSE 0

// 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[3]?

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[4] multimile Mi sunt identice, iar cardinalul este[5] 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[6] 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 [1..100, 1..100] of integer;
var x0, y0, xf, yf: integer;

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

m

[1]

x

= 1;

m

[1]

y

= 0;

m

[2]

x

= -1;

m

[2]

y

= 0;

m

[3]

x

= 0;

m

[3]

y

= -1;

m

[4]

x

= 0;

m

[4]

y

= 1;

end;



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 := 1 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 := 1 to 4 do

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

a [inou] [jnou] := -level -1;
prelucreaza_solutie;
a [inou] [jnou]
:= 0
end

else if este_liber (inou, jnou, level) then
btr (inou, jnou, level
+ 1);

a [icurent] [jcurent]
:= 0

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])
end;
write ('x0=');
read (x0);
write ('y0=');
read (y0);
write ('xf=');
read (xf);
write ('yf=');
read (yf);
a [x0] [y0]
:= 0;
a [xf] [yf] := 0;
end;

begin

initmiscari;
inita;

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




btr (1, x0, y0)
end.

3.3. Programul in limbajul C

include <stdio.h>

define TRUE 1

define FALSE 0

// 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] = 0 then

write (' ')
else if a [i][j] = 1 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 [1..100, 1..100] of integer;
var x0, y0: integer;

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

m

[1]

x

:=

1;

m

[1]

y

:=

0;

m

[2]

x

:=

1;

m

[2]

y

:=

1;

m

[3]

x

:=

0;

m

[3]

y

:=

1;

m

[4]

x

:=

-1;

m

[4]

y

:=

1;

m

[5]

x

:=

-1;

m



[5]

y

:=

0;

m

[6]

x

:=

-1;

m

[6]

y

:=

-1;

m

[7]

x

:=

0;

m

[7]

y

:=

-1;

m

[8]

x

:=

1;

m

[8]

y

:=

-1;

end;



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] = 0) and (a [i] [j] < h)
end;

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

este_gata := ((i = 1) or (j = 1) 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 := 1 to 8 do

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

b [inou] [jnou] := level + 1;
prelucreaza_solutie;
b [inou] [jnou]
:= 0
end

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

b [icurent] [jcurent]
:= 0
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]
:= 0;
end;
write ('x0=');
read (x0);
write ('y0=');
read (y0);
b [x0] [y0]
:= 1;
end;

begin

initmiscari;
inita;

writeln ('Coborarea pe o harta ', n1 , ' x ', n2);
btr (x0, y0,
1)
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 = 1; 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 = 1; 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'[7].



[1]  hamiltonian, adica fiecare patratel sa fie vizitat exact o singura data

[2]   de exemplu, din pozitia (1, 1) nu se va putea sari cu deplasamentele (-1, -2) pentru ca s-ar ajunge la (0, -1) care nu
exista (in afara tablei).

[3]  Adica lant inchis

[4]  Adica toate cele n*n multimi

[5]  Adica numarul de mutari posibile

[6] mai exact valoarea LEVEL

[7] de exemplu a[x0][y0] + 1




{ Politica de confidentialitate } Nu se poate descarca referatul
Acest referat nu se poate descarca

E posibil sa te intereseze alte referate despre:


Copyright © 2019 - Toate drepturile rezervate QReferat.ro Folositi referatele, proiectele sau lucrarile afisate ca sursa de inspiratie. Va recomandam sa nu copiati textul, ci sa compuneti propriul referat pe baza referatelor de pe site.
{ Home } { Contact } { Termeni si conditii }

Referate similare:







Cauta referat