0metoda reluarii
-
Upload
balan-veronica -
Category
Education
-
view
321 -
download
0
Transcript of 0metoda reluarii
1
Metoda reluăriiAutor: Vovcioc RaisaProfesor: Josu Larisa
2
Ne amintim mai întîi tehnica Greedy
Datele iniţiale:
},,,{ 21 naaaA Soluţia problemei:
AxxxxX k ),,,,( 21 Ideia tehnicii Greedy:
alegem cîte un element din mulţimea A şi îl includem în vectorul X
mulţimea
vectorul
3
Schema generală a algoritmului Greedy
while ExistaElemente do begin AlegeUnElement(x); IncludeElementul(x); end
4
Datele iniţiale în metoda reluării
Mulţimile:
};,,{11,12111 maaaA
};,,{22,22212 maaaA
...
}.,,{ ,21 nnmnnn aaaA
5
Soluţia în metoda reluării
Spaţiul soluţiilor:
nAAAS 21
Soluţia: ),,,,( 21 nxxxX
unde ;11 Ax ;22 Ax ..., .nn Ax
6
Ideia metodei reluării
1. Presupunem că la pasul k am calculat deja valorile:
),,,( 21 kxxx
2. Selectăm din mulţimea Ak+1 valoarea xk+1:
),,,,( 121 kk xxxx
3. Dacă ),,,,( 121 kk xxxx satisface condiţiile
problemei, trecem la pasul k+2.
În caz contrar revenim la pasul k şi alegem alt xk.
7
Căutarea soluţiei prin metoda reluării
01
1
10
k := 1
k k:= + 1
a 1 ,1
a 2 ,1
a 1 2,
a 2 ,2
a 3 ,1a 3 ,2 a 3 ,30
k k:= + 1 k k-:= 1k k:= + 1
1
A 1
A 2
A 3
0 0
8
Schema generală a algoritmului recursiv bazat pe metoda reluării
procedure Reluare(k:integer);begin if k<=n then begin X[k]:=PrimulElement(k); if Continuare(k) then Reluare(k+1); while ExistaSuccesor(k) do begin X[k]:=Succesor(k); if Continuare(k) then Reluare(k+1) end; { while } end { then } else PrelucrareaSolutiei;end; {Reluare}
9
Clasificarea problemelor
1. Mulţimile A1, A2, ..., An sînt cunoscute.
3. Elementele din care sînt formate mulţimile A1, A2, ..., An şi numărul n sînt necunoscute.
2. Sînt cunoscute elementele din care sînt formate mulţimile A1, A2, ..., An, numărul n fiind necunoscut.
10
Exemplu
Se consideră mulţimile A1, A2, ..., An, fiecare mulţime fiind formată din mk numere naturale. Selectaţi din fiecare mulţime cîte un număr în aşa mod încît suma lor să fie egală cu q.
11
Reprezentarea datelor
const mmax=50; { numărul maximal de mulţimi } nmax=50; { numărul maximal de elemente }
type Natural = 0..MaxInt; Multime = array[1..nmax] of Natural;
var A : array[1..nmax] of Multime; n : 1..nmax; { numărul de mulţimi } M : array[1..nmax] of 1..mmax; { cardinalul mulţimii S[k] } X : array[1..nmax] of 1..mmax; { indicii elementelor selectate } q : Natural; k, j : integer; Indicator : boolean;
12
Function PrimulElement
function PrimulElement(k : integer) : Natural;begin PrimulElement:=1;end; {PrimulElement }
13
function Continuare(k : integer) : boolean;var j : integer; suma : Natural;begin suma:=0; for j:=1 to k do suma:=suma+A[j, X[j]]; if ((k<n) and (suma<q)) or ((k=n) and (suma=q)) then Continuare:=true else Continuare:=false;end; { Continuare }
Function Continuare
14
function ExistaSuccesor(k : integer) : boolean;begin ExistaSuccesor:=(X[k]<M[k]);end; { ExistaSuccesor }
Function ExistaSuccesor
15
procedure Reluare(k : integer); { Metoda reluarii - varianta recursiva }begin if k<=n then begin X[k]:=PrimulElement(k); if Continuare(k) then Reluare(k+1); while ExistaSuccesor(k) do begin X[k]:=Succesor(k); if Continuare(k) then Reluare(k+1); end { while } end { then } else PrelucrareaSolutiei;end; { Reluare }
Procedure Reluare
16
123
j
iC
12
......
3B
n
1 2 31 2 ... m...
Exemplul 2. Labirintul
17
Labirintul. Formularea matematică
Mulţimile:},,,{1 StîngaJosDreaptaSusA },,,{2 StîngaJosDreaptaSusA
...Soluţia:
},,,,,
,,,,,{
JosJosJosJosDreaptaDreapta
DreaptaJosDreaptaDreaptaDreaptaX
},,,{3 StîngaJosDreaptaSusA
18
Exemplul 3. Domino
Piesele iniţiale “Tren” format din 3 piese
)}6,6(),0,3(),5,3(),6,3{(1 A
19
Calculul mulţimilor A1, A2, ..., An
)}6,6(),0,3(),5,3{(2 A
Includem (3, 6) în tren.
Includem (6, 6) în tren.
)}0,3(),5,3{(3 A
20
Calculul mulţimilor A1, A2, ..., An
A1 – peştera INTRARE:
A1 = {STALACTITE, STALAGMITE}
A3 – peştera IZVOARE:
A2 = {STALACTITE, IESIRE, LILIECI}
A2 – peştera STALACTITE:
A2 = {INTRARE, IZVOARE}