Metoda reluării

Efectuat de: Bejan Mihai

Datele iniţiale în metoda reluării

Mulţimile:

};,,{11,12111 maaaA

};,,{22,22212 maaaA

...

}.,,{ ,21 nnmnnn aaaA

Soluţia în metoda reluării

Spaţiul soluţiilor:

nAAAS 21

Soluţia: ),,,,( 21 nxxxX

unde ;11 Ax ;22 Ax ..., .nn Ax

Ideea 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.

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

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}

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.

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.

Exemplul 1. 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;

Function PrimulElement

function PrimulElement(k : integer) : Natural;begin PrimulElement:=1;end; {PrimulElement }

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

function ExistaSuccesor(k : integer) : boolean;begin ExistaSuccesor:=(X[k]<M[k]);end; { ExistaSuccesor }

Function ExistaSuccesor

Anatol Gremalschi, 2004

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

Anatol Gremalschi, 2004 14

Vă mulţumesc pentru atenţie !