Metoda backtracking

Metoda backtracking
1.1. Ideile de baza

Enuntul problemei

Fie n multimi Mi, M₂, ..M_n cu cate pi, p₂, ..p_n elemente.
IMil = pi.

Fara a particulariza, consideram ca

Mi = .
Fie M produsul cartezian al celor n multimi
M = M₁ x M₂ x x M_n.

Se pune problema determinarii tuturor tuplurilor
x e M

care verifica o anumita conditie unde

M .

Prin urmare, ne punem problema determinarii multimii solutiilor

S = .

Parcurgerea intregii multimi M pentru gasirea solutiilor poate fi descurajanta, de aceea se impun
mecanisme de parsare sistematica a multimii M.

Functia de continuare

Ideea de baza a algoritmului backtracking este de a gasi solutia problemei prin construirea partiala
a solutiei. Astfel, este important de gasit solutii partiale pentru prolema noastra. O solutie partiala
este un vector (x₁, x₂, , x_k) pentru care exista posibilitatea completarii pana la un vector solutie
(x₁, x₂, , x_n). Mai precis, putem afirma cu siguranta ca (x₁, x₂, , x_k) nu este solutie partiala, daca
oricum am completa acest vector pana la indicele n, (x x ., xn) nu este vector solutie. Prin
urmare putem defini in mod natural functia de continuare, acea functie logica

k: Mi x M x x Mn
care verifica simultan urmatoarele proprietati:

n =

daca k(xi, X , xk)='fals' ^ Vxk₊i e Mk+i, k+i(xi, X xk+i)='fals'
Acum putem da definitia unei solutii partiale:

Definitie: Spunem ca (x_i? x₂, , x_k) este o solutie partiala daca si numai daca _k(x_i? x₂, ,
x_k)='adevarat'.

De remarcat semantica functiei de continuare, pe care se bazeaza intreg algoritmul Backtracking:
daca evaluarea functiei de continuare imi da 'adevarat', atunci 'are sens' sa continuam cu cautarea
solutiilor partiale prin marirea numarului de elemente din tuplu (faza de 'inainte'). Algoritmul
trebuie sa aiba si puncte in care se revine (de 'inapoi'), de aceea algoritmul se mai numeste si
'avansare cu revenire'. Practic daca (x_i? x₂, , x_k) este o solutie partiala, inseamna ca are sens sa
cautam candidati pentru x_k+_i din multimea M_k+_i prin parcurgerea treptata a multimii. In cazul in
care gasim o valoare astfel incat (x_i, x₂, , x_k+_i) sa fie solutie partiala, vom continua algoritmul cu
aceasta valoare. Dupa epuizarea acestei 'filiere' de obtinere a solutiilor si solutiilor partiale, vom
reveni la urmatoarea valoare din M_k+_i, pana la epuizarea multimii. Dupa epuizarea multimii ne
intoarcem la solutia partiala (x_i, x₂, , x_k-i), apoi continuam cu urmatoarea valoare x_ke M_k.

1.1.3. Exercitii si probleme

Demonstrati ca pentru identic adevarata se genereaza produsul cartezian

M = M_i x M₂ x x M_n.

Demonstrati ca pentru identic adevarata, 9_k este de asemenea identic adevarata.

Demonstrati ca IMI = p_i.p₂.p_n.

Ce este o solutie partiala de dimensiune n?

Demonstrati ca daca

k(xi, x , xk)='fals',
atunci nu exista nici o solutie (x_i, x₂, , x_n).
1.1.4. Rezolvarea exercitiilor si problemelor

Evident pe baza definitiei.

Prin inductie descrescatoare dupa k:
pentru k = n este chiar (i);

presupunem ca k+i este identic adevarat, vrem sa demonstram ca si k este identic adevarat.
Presupunem prin absurd ca 9_k nu e identic adevarat, adica exista (x_i, x₂, , x_k) pentru care _k(x_i,
x₂, , x_k)='fals'. Aplicand (2) avem ca Vx_k+i e M_k+i, k+i(xi, x₂, , x_k+i)='fals', adica 9_k+i nu e
identic adevarat; contradictie.

Demonstratia este imediata prin inductie dupa n.

O solutie a problemei.

Aplicand de n-k ori relatia (2) obtinem enuntul.
1.2. Algoritmul in varianta iterativa

Algoritmul

Subprogramul pentru algoritmul Backtracking este:

Subprogram bt (np, p, x)
k := 1
x [k] := 0

Cat Timp k > 0 Executa
Repeta

incrementeaza (x [k])
Pana Cand fi (k, x) or (x [k] > p [k])
Daca x [k] <= p [k] Atunci
Daca k = np Atunci

Apel prelucreaza_solutie (np, x)
Altfel

incrementeaza (k)
x [k] := 0
Sfarsit Daca
Altfel

decrementeaza (k)
Sfarsit Daca
Sfarsit Cat Timp
Sfarsit Subprogram

Apelul subprogramului se face prin:

apel bt (np, p, x)

Exercitii si probleme

Ce reprezinta variabila K?

Presupunand ca parametri se transmit prin referinta, subprogramul de mai sus este funtional in
continuare?

Care este rolul testului K = NP?

Presupunand ca NP, P si X sunt variabile globale, puteti modifica subprogramul BT astfel incat
sa isi pastreze functionalitatea?

Cu modificarile de la problema anterioara, puteti rula programul intr-un mediu concurent? Dar
paralel?

Pastrand variabilele definite global, putem rescrie algoritmul intr-o versiune concurenta? Dar
paralela?

De ce dupa incrementarea lui K se initializeaza cu 0 elementul X [K]?

Ce se intampla dupa gasirea unei solutii?

De ce se decrementeaza variabila K?

Demonstrati total corectitudinea algoritmului BT.

Evaluati complexitatea algoritmului BT.

1.2.3. Rezolvarea exercitiilor si problemelor

Numarul de componente din solutia partiala construita.

Da, pentru ca in afara de x, nici o variabila nu se mai modifica, iar in cazul lui x, valorile se
modifica in ritmul constuirii de solutii partiale.

Verificarea faptului ca solutia partiala este de fapt o solutie.

Subprogramul modificat este:

Global np, p, x
Subprogram bt
k := 1
x [k] := 0

Cat Timp k > 0 Executa
Repeta

incrementeaza (x [k])
Pana Cand fi (k, x) or (x [k] > p [k])
Daca x [k] <= p [k] Atunci
Daca k = np Atunci

Apel prelucreaza_solutie (np, x)
Altfel

incrementeaza (k)
x [k] := 0
Sfarsit Daca
Altfel

decrementeaza (k)
Sfarsit Daca
Sfarsit Cat Timp
Sfarsit Subprogram

Da, dar nu se vor folosi nici una din facilitatile concurentei sau paralelismului in mod explicit

Nu. Dupa incrementarea lui K si initializarea lui X[K] este punctul in care se poate creea un
proces rulat paralel sau concurent. De mentionat ca fiecare proces trebuie sa aiba copia lui a
vectorului X.

Pentru ca se intra din nou in iteratia dupa K, care continua cu gasirea unui candidat pentru X[K],
unde prima operatie este incrementarea lui X[K].

La gasirea unei solutii se apeleaza PRELUCREAZA_SOLUTIE, apoi se intra din nou in iteratia
dupa K, astfel incat se modifica X[NP] pentru cautarea unei noi solutii.

Deoarece pentru X[K] s-au verificat si procesat toti candidatii pentru solutia partiala, se va trece
la urmatoarea solutie partiala folosind primele K-i elemente din solutia partiala curenta.

Vom demonstra mai intai ca orice rezultat scos de BT este corect, adica 9 este adevarat. De
remarcat ca unicul loc in care are loc o iesire a datelor este apelul PRELUCREAZA_SOLUTIE;
dar acest lucru nu poate sa se intample decat daca K = NP, adica avem deja completate NP
valori din vectorul cu solutii partiale X, valori care au trecut toate de testul de acceptanta prin
apelul functiei de continuare FI, adica datele scoase reprezinta solutii.

Vom demonstra acum ca nu exista solutii pe care BT sa nu le gaseasca. Presupunem prin absurd
ca vectorul Y[i], Y[2], , Y[NP] reprezinta o solutie negasita de BT. Fie K maximul
numarului de elemente consecutive incepand cu prima pozitie identice din vectorul Y si vectorul
solutiilor partiale X de-a lungul perioadei de viata. Evident, FI (K, Y[i], Y[2], , Y[K]) este
adevarat, deci dupa incrementarea lui K se intra din nou in cautarea unui nou candidat, in urma
incrementarilor succesive ale lui X[K] se va ajunge la un moment dat la solutia partiala pe K+i
elemente pentru care X[K+i] = Y[K+i], solutie ce verifica evident si FI (K+i, Y[i], Y[2], ,
Y[K+i]), adica avem K+i valori identice, adica K ales nu e maxim cu proprietatea ceruta;
contradictie.

8 9

Am demonstrat ca algoritmul este partial corect , urmeaza sa demonstram ca e finit : Fie PMAX
maximul elementelor vectorului P. Definim functia

W: x M ^ N,

unde W(K, X) este numarul de NP cifre in baza PMAX, cu primele K cifre din vectorul X, iar
ultimele NP-K cifre 0 pentru o solutie partiala la care nu se revine prin decrementare. Respectiv
W(K,X) este definit ca mai sus adaugandu-se 0,5 * PMAX^AK. In mod evident W este o functie
limitata superior de PMAXA(NP+i)

Ramane de aratat ca functia W este o functie monoton crescatoare. Acest lucru, insa, este
imediat pe observatia ca in cadrul lui BT, la fiecare iteratie are loc o crestere a lui X[K], implicit
si a valorii lui W sau o crestere a valorii W cu 0,5 * PMAXAK daca are loc decrementarea lui K.

Prin urmare, am demonstrat ca algoritmul este total corect .
ii. Presupunand ca 9 este identic adevarat si ca p_i=2, atunci multimea solutiilor are 2ⁿ elemente,
care sunt toate generate. Deci O(BT)=2ⁿ, adica avem o complexitate exponentiala.

1.3. Algoritmul in varianta recursiva

Algoritmul

Subprogramul pentru algoritmul Backtracking este:

Subprogram btr (level, np, p, x)

Daca level = np + 1 Atunci

Apel prelucreaza_solutie (np, x)

Altfel

Pentru i := 1, p [level] Executa
x [level] := i;
Daca fi (level, x) Atunci

Apel btr (level + 1, np, p, x)
Sfarsit Daca
Sfarsit Pentru

Sfarsit Daca

Sfarsit Subprogram

Apelul subprogramului se face prin:

apel btr (1, np, p, x)

Exercitii si probleme

Ce reprezinta parametrul LEVEL?

Presupunand ca parametri se transmit prin referinta, subprogramul de mai sus este funtional in
continuare?

Presupunem ca in stiva de executie avem K instante a subprogramului BTR, iar prima instanta a
fost apelata corect, care este valoarea parametrului LEVEL in cea mai tanara instanta? Dar in
cea mai batrana instanta?

Care este rolul testului LEVEL = NP + 1?

Presupunand ca np, p si x sunt variabile globale, puteti modifica subprogramul BTR astfel incat
sa isi pastreze functionalitatea?

Cu modificarile de la problema anterioara, puteti rula programul intr-un mediu concurent? Dar
paralel?

Pastrand variabilele definite global, putem rescrie algoritmul intr-o versiune concurenta? Dar
paralela?

Demonstrati total corectitudinea algoritmului BTR.

Determinati complexitatea algoritmului BTR.

Demonstrati ca BT si BTR sunt algoritmi echivalenti .

1.3.3. Rezolvarea exercitiilor si problemelor

LEVEL reprezinta indicele in vectorul x ce urmeaza a fi completat cu diverse valori candidat

Da, pentru ca in afara de X, nici o variabila nu se mai modifica, iar in cazul lui X, dupa apelul
recurent nu se modifica nici o valoare cu indicele mai mic decat LEVEL

K, respectiv 1

Verificarea faptului ca am identificat toti cei NP valori din vectorul X astfel incat sa avem in X
o solutie valida

Subprogramul nou este:

Global np, p, x

Subprogram btr (level)

Daca level = np + 1 Atunci

Apel prelucreaza_solutie (np, x)

Altfel

Pentru i := 1, p [level] Executa
x [level] := i
Daca fi (level, x) Atunci

Apel btr (level + 1)
Sfarsit Daca
Sfarsit Pentru

Sfarsit Daca

Sfarsit Subprogram

Da, dar nu se vor folosi nici una din facilitatile concurentei sau paralelismului in mod explicit

Nu. Apelul recursiv BTR poate fi lansat simultan pe maxim P[LEVEL] procesoare, respectiv
se pot porni maxim P[LEVEL] procese fiu . De mentionat ca fiecare proces trebuie sa aiba
copia lui a vectorului X.

Vom demonstra mai intai ca orice rezultat scos de BTR este corect, adica 9 este adevarat. De
remarcat ca unicul loc in care are loc o iesire a datelor este apelul PRELUCREAZA_SOLUTIE;
dar acest lucru nu poate sa se intample decat daca LEVEL = NP + 1, adica suntem in a (NP +
1)-a instanta a lui BTR, adica avem deja completate NP valori din vectorul X, valori care au

- io -

trecut toate de testul de acceptanta prin apelul functiei de continuare FI, adica datele scoase
reprezinta solutii.

Vom demonstra acum ca nu exista solutii pe care BTR sa nu le gaseasca. Presupunem prin
absurd ca vectorul Y[i], Y[2], , Y[NP] reprezinta o solutie negasita de BTR. Fie K maximul
numarului de elemente consecutive incepand cu prima pozitie identice din vectorul Y si vectorul
solutiilor partiale X de-a lungul perioadei de viata. Evident, FI(K+i, Y[i], Y[2], , Y[K],
Y[K+i]) este adevarat, deci dupa atribuirea X[K+i] := Y[K+i], in urma apelului de evaluare a
lui FI se va face apelul recursiv intrandu-se intr-o noua instanta a lui BTR; adica avem K+i
valori identice, adica K ales nu e maxim cu proprietatea ceruta; contradictie.

Am demonstrat ca algoritmul este partial corect , urmeaza sa demonstram ca e finit : Fie
PMAX maximul elementelor vectorului P. Definim functia

W: x M ^ N,

unde W(LEVEL,X) este numarul de NP cifre in baza PMAX, cu primele LEVEL cifre din
vectorul X, iar ultimele NP-LEVEL cifre 0. Respectiv

W(NP+i, X) = PMAX ^A (NP+i).

In mod evident W este o functie limitata superior de PMAXA(NP+1) , valoare ce se atinge
pentru LEVEL = NP+1.

Ramane de aratat ca functia W este o functie monoton crescatoare. Acest lucru, insa, este
imediat pe observatia ca in cadrul lui BTR, inainte de apelul recursiv are loc o crestere a lui
X[LEVEL], implicit si a valorii lui W, respectiv la apelul recursiv are loc o crestere a lui
LEVEL, deci implicit mai multe cifre in W.

Prin urmare, am demomstrat ca algoritmul este total corect .

Presupunand ca 9 este identic adevarat si ca

pi = 2,

atunci multimea solutiilor are 2ⁿ elemente, care sunt toate generate. Deci
O (BTR) = 2ⁿ.

Deoarece BT si BTR sunt total corecte rezolvand ambele aceeasi problema si deoarece BT si
BTR au aceeasi complexitate, rezulta ca cei doi algoritmi sunt echivalenti.

Model de program in Pascal

1.4.1. Modelul de program

program algoritmul_backtracking;

const maxsir

type indicesir 1..maxsir;

type sir array [indicesir] of integer;
type tipbacktracking = (recursiv, iterativ);

var p: sir;

var np: indicesir;

function fi (k: indicesir; x: sir): boolean;
begin
fi := true
end;

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i: indicesir;
begin

for i := 1 to n do

write (x [i], ' ');
writeln
end;

procedure btr (level, np: indicesir; p, x: sir);
var i: indicesir;
begin

if level > maxsir then
exit;

if level = np + 1 then

prelucreaza_solutie (np, x)
else

for i := 1 to p [level] do
begin

x [level] := i;

if fi (level, x) then

btr (level + 1, np, p, x)
end

end;

procedure bt (np: indicesir; p, x: sir);
var k: integer;
var ok: boolean;

begin
k := 1;
x [k] := 0;

while k > 0 do
begin
repeat

inc (x [k]);

ok := fi (k, x) or (x [k] > p [k])
until ok;

if x [k] <= p [k] then
if k = np then

prelucreaza_solutie (np, x)
else
begin
inc (k);
x [k] := 0;
end

else

dec (k)
end
end;

procedure backtracking (tip: tipbacktracking; np: indicesir; p:
sir);

var x: sir;
begin

case tip of

recursiv: btr np, p, x);
iterativ: bt (np, p, x)
end
end;

begin

p p p np := 3;

writeln ('exemplificare
backtracking (recursiv,
writeln ('exemplificare
backtracking (iterativ,
end.

backtracking recursiv');
np, p);

backtracking iterativ');

np, p)

1.4.2. Exercitii si probleme

Demonstrati ca programul genereaza produsul cartezian ca la orincipiul contorului.

Care este rolul parametrului TIP in procedura BACKTRACKING?

Care este numarul maxim de multimi M_i?

Care este numarul de multimi Mi?

Unde se memoreaza IM_iI?

Modificati procedura PRELUCREAZA_SOLUTIE astfel incat solutia sa fie afisata sub forma
unui tuplu cu elementele separate prin virgula.

Modificati programul astfel incat sa se termine la gasirea primei solutii (in caz ca ea exista)

Modificati programul astfel incat sa se afiseze in procedura PRELUCREAZA_SOLUTIE si
numarul curent al solutiei.

Modificati programul principal astfel incat sa se citeasca de la tastatura numarul de multimi Mi
si dimensiunile lor.

Aceeasi problema, cu mentiunea ca elementele P[I] sunt identice.

Modificati procedura BTR in spiritul programarii defensive .

Modificati procedura BT in spiritul programarii defensive.

1.4.3. Rezolvarea exercitiilor si problemelor

Deoarece functia de continuare este identic adevarata, rezulta ca si este identic adevarata,
adica se va genera produsul cartezian.

Rolul este de selector a implementarii (recursiv sau iterativ)

MAXSIR

NP

In elementul p[i]

Vom afisa separat paranteza de deschidere si primul element, respectiv ultimul element, lasand
in bucla iterativa afisarea virgulei curente si a elementului curent:

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i: indicesir;
begin

write( '(', x [1]);
for i := 2 to n do

write (', ', x [i]);
writeln (')')
end;

vom folosi procedura halt:

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i: indicesir;
begin

for i := 1 to n do

write (x [i], ' ');
writeln;

halt
end;

adaugam variabila globala NUMARSOLUTII initializata cu zero la compilare; la fiecare apel al
procedurii PRELUCREAZA_SOLUTII incrementam aceasta variabila cu o unitate:

const numarsolutii: word

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i: indicesir;
begin

inc (numarsolutii);

writeln ('Solutia nr. ', numarsolutii);
for i := 1 to n do

write (x [i], ' ');
writeln
end;

avem nevoie de o variabila I cu ajutorul careia vom itera la citirea dimensiunilor:

var i: indicesir;
begin

write ('n=', np);
readln (np);
for i := 1 to np do
begin

write ('p[', i, ']=');

readln (p [i])
end;

writeln ('exemplificare backtracking recursiv');
backtracking (recursiv, np, p);

writeln ('exemplificare backtracking iterativ');
backtracking (iterativ, np, p)
end.

Este suficient sa citim doar primul element , restul fiind initializati intr-o bucla FOR:

var i: indicesir;
begin

write ('n=', np);
readln (np);
write ('p [1]=');
readln (p [1])

for i to np do
p [i] p writeln ('exemplificare
backtracking (recursiv,
writeln ('exemplificare
backtracking (iterativ,
end.

backtracking recursiv');
np, p);

backtracking iterativ');

np, p)

11. Adaugam conditiile suplimentare LEVEL > 0, NP > 0, NP <= MAXSIR

procedure btr (level, np: indicesir; p, x: sir);
var i: indicesir;
begin

if (level > maxsir) or (level <= 0) or (np <= 0) or (np >
maxsir) then
exit;

if level np then

prelucreaza_solutie (np, x)
else

for i := 1 to p [level] do
begin

x [level] := i;

if fi (level, x) then

btr (level + 1, np, p, x)
end

end;

12. Adaugam conditiile suplimentare NP > 0, NP <= MAXSIR

procedure bt (np: indicesir; p, x: sir);
var k: integer;
var ok: boolean;
begin

if (np <= 0) or (np > maxsir) then

exit;
k := 1;
x [k] while k > 0 do
begin
repeat

inc (x [k]);

ok fi (k, x) or (x [k] > p [k])
until ok;

if x [k] <= p [k] then
if k = np then

prelucreaza_solutie (np, x)
else
begin
inc (k);
x [k] end

else

dec (k)
end
end;

Model de program in C

1.5.1. Modelul de program

include <stdio.h>

define MAXSIR 100

define RECURSIV 1

define ITERATIV 2

// dimensiunile multimilor Mi
int p [MAXSIR];
int np;

define TRUE 1

define FALSE 0

// functia de continuare

int fi (int k, int x[])

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

backtracking implementarea recursiva

void btr (int level, int np, int p[], int x[])

void bt (int np, int p[], int x[])

if (x [k] <= p [k])
if (k np)
prelucreaza_solutie (np, x);
else

else

k-- ;

void backtracking (int tip, int np, int p[])

void main ()

Exercitii si probleme

Demonstrati ca programul genereaza produsul cartezian ca la orincipiul contorului.

Care este rolul parametrului TIP in functia BACKTRACKING?

Care este numarul maxim de multimi Mi?

Care este numarul de multimi Mi?

Unde se memoreaza IM_il?

Modificati functia PRELUCREAZA_SOLUTIE astfel incat solutia sa fie afisata sub forma unui
tuplu cu elementele separate prin virgula.

Modificati programul astfel incat sa se termine la gasirea primei solutii (in caz ca ea exista)

Modificati programul astfel incat sa se afiseze in functia PRELUCREAZA_SOLUTIE si
numarul curent al solutiei.

Modificati programul principal astfel incat sa se citeasca de la tastatura numarul de multimi M_i
si dimensiunile lor.

Aceeasi problema, cu mentiunea ca elementele p[i] sunt identice.

Modificati functia BTR in spiritul programarii defensive .

Modificati functia BT in spiritul programarii defensive.

Rezolvarea exercitiilor si problemelor

Deoarece functia de continuare este identic adevarata, rezulta ca si 9 este identic adevarata,
adica se va genera produsul cartezian.

Rolul este de selector a implementarii (recursiv sau iterativ)

MAXSIR-1

NP

In elementul p[i]

Vom afisa separat paranteza de deschidere si primul element, respectiv ultimul element, lasand
in bucla iterativa afisarea virgulei curente si a elementului curent:

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

vom folosi functia exit:

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

adaugam variabila globala NUMARSOLUTII initializata cu zero la compilare; la fiecare apel al
procedurii PRELUCREAZA_SOLUTII incrementam aceasta variabila cu o unitate:

unsigned int numarsolutii = 0;

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

avem nevoie de o variabila I cu ajutorul careia vom itera la citirea dimensiunilor:

void main

printf ('exemplificare backtracking recursivn');
backtracking (RECURSIV, np, p);

printf ('exemplificare backtracking iterativn');

backtracking (ITERATIV, np, p);
}
Este suficient sa citim doar primul element^[23], restul fiind initializati intr-o bucla FOR:

void main

Adaugam conditiile suplimentare LEVEL > 0, NP > 0, NP <= MAXSIR

backtracking implementarea recursiva

void btr (int level, int np, int p[], int x[])

Adaugam conditiile suplimentare NP > 0, NP <= MAXSIR

void bt (int np, int p[], int x[])

if (x [k] <= p [k])
if (k == np)
prelucreaza_solutie (np, x);
else

else

k-- ;

1.6. Serializarea ca metoda de obtinere a functiei de continuare

Prezentarea metodei

Vom prezenta in cele ce urmeaza o metoda simpla de obtinere a funtiei de continuare din Presupunem ca poate fi scrisa sub forma de conjunctii dupa cum urmeaza:

(xi, x , xn) = Wl(xi) A (xi, x A . A Onfrl, x . , xn)
in acest caz, o buna functie de continuare ar putea fi:

k(xi, x , x_k) = Wl(xi) A ©z(xi, x A ... A ffl^xi, x . , x_k)
pentru ca sunt respectate conditiile pentru funtia de continuare.

Se observa cu usurinta ca:

k(xi, x , xk) = k-l(xi, x , xk-l) A Wk(xi, x , xk)

astfel ca in implementarea functiei de continuare putem evalua doar rezultatul expresiei ro_k(x_l, x₂,
, x_k), deoarece membrul stang al conjunctiei a fost evaluat anterior si rezultatul este 'adevarat'.

Exemplu

Vom prezenta in continuare metoda serializarii pentru problema determinarii permutarilor pentru
multimea , unde vectorul x va codifica valoarea functiei-permutare pentru indicele

29

dat . Se cunoaste urmatoarea lema a bijectiei pe multimi finite:

Lema: Fie A o multime finita, f:A^A. Urmatoarele afirmatii sunt echivalente

i.     f este functie bijectiva

ii.       f este functie injectiva

iii.     f este functie surjectiva

Pe baza lemei, este suficient sa testam injectivitatea, adica faptul ca vectorul x are valori distincte.
Deci este:

(Xi, X ..Xn) = A (Xi <>Xj)

1 <= i < j <= n

Identificand functiile omega prin serializare obtinem:

©k(Xl, X , Xk) = A (Xi <>Xk)

1 <= i < k

Adica este suficient ca la adaugarea unui element X_k in tuplu sa testam daca el este diferit de
elementele deja introduse in tuplu.

Alte tipuri de serializari

Presupunem ca functia este de forma:

(Xi, X Xn) = 'X[1] + x[2] + + X[n] <= K',
atunci vom cauta sa implementam o conditie de continuare bazata pe ideea de suma:

k (Xi, X Xk) = 'X[1] + x[2] + . + X[k] <= K',
Presupunem ca functia este de forma:

(Xi, X , Xn) = ' U C K',

1<=i<=n

atunci vom cauta sa implementam o conditie de continuare bazata pe ideea de suma:

k (Xi, X , Xk) = ' u c K',
1<=i<=k

Prin urmare, ideea de baza a serializarii este de a 'rupe' o parte din functia pe baza asociativitatii
unor operatori binari, astfel incat parti din conditie sa se poata verifica pe parcurs folosind o solutie
partiala pentru evaluare.

Exercitii si probleme

Demonstrati afirmatia (3).

Demonstrati ca functia definita la (2) este o buna functie de continuare.

Demonstrati afirmatia referitoare la implementarea functiei de continuare.

Demonstrati lema bijectiei pe multimi finite.

Implementati functia FI pentru problema generarii permutarilor.
6. Construiti prin serializare functia de continuare pentru problema colorarii graiurilor si
implementati functia FI.

1.6.4. Rezolvarea exercitiilor si problemelor

In definitia (1) substituim k cu k-1 si obtinem apoi imediat formula (3) prin rescrierea definitiei
(1)

Se observa ca

(X X , Xn) = n(X X . , Xn),

ambii termeni ai egalitatii fiind la randul lor egali cu

(X A (X X A A ©k(X X , Xk)
(conform (1) si (2)). Conform (3) avem prin substitutia lui k cu k+1 ca

k+1(X X , Xk+1) = k(X X , Xk) A ©k+1(X X , Xk+1)

prin urmare, daca _k(X₁, x₂, , X_k) este 'fals', rezulta ca si _k(X₁, x₂, , X_k) a ro_k+₁(X₁, x₂, , X_k+₁)
este 'fals', adica si ^_k+₁(x₁, x₂, , x_k+₁) este 'fals'.

Deoarece apelul functiei FI pentru un K si un X dat succede apelului functiei FI pentru o valoare
a lui K mai mica cu o unitate, respectiv cu aceleasi prime K-1 elemente din vectorul X.

Vom demonstra pe rand urmatoarele afirmatii:

i.     bijectiv ^ injectiv

evident pe baza definitiei bijectivitatii unei functii

ii.       injectiv ^ surjectiv

presupunem prin absurd ca f nu e surjectie, adica exista un ye A care nu are contraimagine; conform
principiului includerii si al excluderii avem ca exista distincte a, b e A pentru care f(a) = f(b),
adica f nu e injectiva; contradictie.

iii.     surjectiv ^ bijectiv

e suficient sa demonstram doar surjectiv ^ injectiv: presupunem prin absurd ca f nu e injectiva,
deci exista distincte a, b e A pentru care f(a) = f(b), adica numarul imaginilor functiei f este mai
mic decat numarul de elemente a multimii A , adica eXista elemente din A care nu sunt imagini ale
lui f , deci f nu e surjectiva; contradictie.

Implementarea functiei FI:

i.     limbajul Pascal

function fi (k: indicesir; x: sir): boolean;
var i: indicesir;

begin

fi := true;

for i := 1 to k - 1 do

if x [i] = x [k] then
fi := false

end;

ii.       limbajul C

// functia de continuare

int fi (int k, int x[])

Presupunem ca avem un graf G = (V, U), unde V = este multimea celor n varfuri,
iar U e V x V este multimea muchiilor data prin matricea de adiacenta . Fie X vectorul
culorilor atasate. Spunem ca X este o colorare buna daca nu avem doi vecini colorati cu
aceeasi culoare. Prin urmare, 9 este:

9 (Xi, X2, Xn) = A (Xi <>X_k)

1 <= i < j <= n
a [i, j] = 1

Prin serializare obtinem:

k (xi, x xk) = A (xi <>xk)
l <= i < k
a [i, j] = l

Functia FI aferenta implementata este:

i. in limbajul Pascal :

function fi (k: indicesir; x: sir): boolean;
var i: indicesir;

begin

fi := true;

for i := 1 to k - 1 do

if (a [i, j] = 1) and (x [i] = x [k]) then
fi := false

end;
ii. limbajul C

// functia de continuare

int fi (int k, int x[])

1.7. Cea mai buna functie de continuare

1.7.1. Definitie

Spunem ca 9_k este cea mai buna functie de continuare daca verifica urmatoarea proprietate:

9_k este functie de continuare

_k(X₁,X₂,.,X_k)='adevarat' ^ (X_k+₁,X_k+₂.,X_n) astfel incat 9(x₁,x₂,., X_n)='adevarat'

adica, daca (x₁,x₂,.,x_k) este o solutie partiala , atunci cu siguranta exista o solutie obtinuta prin
sufiXarea acesteea.

1.7.2. Exemplu

Fie problema generarii permutarilor pentru care am vazut ca:

(X X . , Xn) = A (Xi <>Xj)

1 <= i < j <= n
si din care am obtinut in urma serializarii:

k(X X Xk) = A (Xi <>Xj)

1 <= i < j <= k

Vom arata ca k asa cum e definit mai sus este cea mai buna functie de continuare. Presupunem ca
_k(x_l, x₂, , x_k) este adevarata, deci cele k valori sunt distincte doua cate doua. Daca k=n, atunci
(x_l, x₂, x_n) este o solutie. Daca k < n, atunci multimea este nevida ,
deci multimea permutarilor acestei multimi este nevida, prin urmare putem gasi (x_k+l, x_k+₂, , x_n)
astfel incat (x_l, x₂, x_n) sa fie o permutare, adica (x_l, x₂, x_n) sa fie o solutie.

Ordonarea functiilor de continuare

Fie 9_lk si 9_2k doua functii de continuare ale aceleasi probleme. Spunem ca 9_lk este mai buna decat

43

2k si notam ik >= 2k daca :

Vxi,x ,,xk: ik(xi,x ,,xk) 2k(xi,x ,,xk)

adica 9_lk are mai putine sanse de a genera parcurgeri inutile a spatiului de potentiale solutii partiale.

Se observa ca pe multimea a tuturor solutiilor partiale relatia >= este o relatie de ordine partiala si in plus, daca notam cu 0k cea mai buna functie de continuare, avem ca

V9ke$: 90k>=9k

Exercitii si probleme

Demonstrati ca pentru orice functie se poate defini k)k=i,n astfel incat k sa fie o functie de
continuare.

Demonstrati relatia (3)

Demonstrati ca ( ,>=) este o multime partial ordonata

Definiti o relatie de 'mai putin bun' pe si aratati ca este o relatie de ordine partiala

Rezolvarea exercitiilor si a problemelor

9_k identic adevarat pentru k=l,n-l si 9_n=9.

Deoarece 0k este cea mai buna functie de continuare, adica se garanteaza constructia unei
solutii din solutia partiala rezulta ca Vx_l,x₂,.,x_k: _0k(x_l,x₂,,x_k) _k(x_l,x₂,,x_k), adica
0k>=9k.

Reflexivitatea: Vx_l,x₂,.,x_k: _k(x_l,x₂,.,x_k) _k(x_l,x₂,.,x_k), adica 9_k>=9_k.

Tranzitivitatea: ik>=92k si 2k>=93k, adica Vxi,x ,,xk: ik(xi,x ,,xk) 2k(xi,x ,,xk) si
Vxi,x ,^,xk: 2k(xi,x ,,xk) 3k(xi,x ,.,xk), adica Vxi,x ,,xk: ik(xi,x ,,xk) 3k(xi,x ,.,xk), adica ik>=93k-

Antisimetria: ik>=^2k si ^2k>=9ik, adica Vxi,x ,,xk: ik(xi,x ,,xk) 2k(xi,x ,,xk) si
Vxi,x ,.,xk: 2k(xi,x ,.,xk) ik(xi,x ,.,xk), adica Vxi,x ,,xk: ik(xi,x ,,xk) =
ik(xi,x ,.,xk), adica ik 2k-

4. 9_ik<=9_2k daca si nu mai daca 9_ik>=9_2k. Reflexivitatea, tranzitivitatea si antisimetria se bazeaza
pe proprietatile omoloage ale lui >=.