Backtracking cu solutii de lungime variabila

Backtracking cu solutii de lungime variabila

1. Enuntul problemei si modificari in algoritm

1.1. Prezentare

Sunt cazuri in care solutia cautata nu poate fi exprimata in termeni absoluti cu ajutorul a n elemente
componente ale vectorului X. De multe ori, solutia poate sa fie variabila, adica in loc sa avem :

x e Mi x M₂ x x M_n

avem:

x e u Mi x M₂ x x M_k.
1<=k<=n

O solutie ar fi apelarea succesiva a algoritmului Backtracking intr-o bucla pentru construirea
solutiei cu lungime de 1, 2, samd:

Subprogram Btr (n, p, x)
Pentru k = 1, n Executa
Apel bt/btr (k, p, x)
Sfarsit Pentru

O astfel de solutie nu satisface intru totul cerintele, pentru ca este susceptibila de a mari enorm
timpii de calcul, mai ales ca unele subsecvente se proceseaza mult mai des decat e necesar . Prin
urmare, se impune o modificare a algoritmului initial.

Deoarece aritatea functiei obiectiv depinde de dimensiunea vectorului solutie , vom identifica
functia obiectiv astfel ^_n(x₁, x₂, , x_n) pentru a o diferentia de functia de continuare 9_n(x₁, x₂, ,
x_n) si se impun conditiile:

Daca 9_n(x₁, x₂, , x_n) = 'adevarat', atunci ^_n(x₁, x₂, , x_n) = 'adevarat'.

Daca 9k(x₁, x₂, , x_k) = 'fals', atunci oricare l>=k si oricare x_k+₁, x_k+₂, , x_l ^_l(x₁, x₂, , x_l) =
'adevarat'.

1.2. Modificarea algoritmului iterativ

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

Cat Timp k > 0 Executa
Repeta

incrementeaza (x [k])
ok1 := ffi (k, x)
ok2 := fi (k, x)

ok := ok1 sau ok2 sau (x [k] > p [k])
Pana Cand ok

Daca x [k] <= p [k] Atunci
Daca ok1 Atunci

Apel prelucreaza_solutie (k, x)
Altfel

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

decrementeaza (k)
Sfarsit Daca

Sfarsit Cat Timp

Sfarsit Subprogram

Modificarea algoritmului recursiv

Subprgram btvr (level, np, p, x)

Daca level <= np Atunci

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

Apel prelucreaza_solutie (level, x)
Altfel

Daca fi (level, x) Atunci

Apel btvr (level + 1, np, p, x)

Sfarsit Daca
Sfarsit Daca
Sfarsit Pentru

Sfarsit Subprogram

Exercitii si probleme

Ce se intmapla daca K = NP si esueaza FFI, in schimb nu esueaza FI in algoritmul nerecursiv?

Corectati algoritmul pentru bug-ul de la problema anterioara.

Rezolvarea exercitiilor si problemelor

Se ajunge la o fortare a conditiilor impuse functiilor FFI si FI, respectiv algoritmul depaseste
intervalul alocat vectorilor.

Modificarea este:

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

Cat Timp k > 0 Executa
Repeta

incrementeaza (x [k])
ok1 := ffi (k, x)
ok2 := fi (k, x)

ok := ok1 sau ok2 sau (x [k] > p [k])
Pana Cand ok

Daca x [k] <= p [k] Atunci
Daca ok1 Atunci

Apel prelucreaza_solutie (k, x)
Altfel

Daca k = np Atunci
Decrementeaza (k)
Altfel

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

decrementeaza (k)
Sfarsit Daca
Sfarsit Cat Timp
Sfarsit Subprogram

2. Model de program in Pascal⁶³

program algoritmul_backtracking_cu_solutii_de_lungime_variabila;

const maxsir = 100;

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;

function ffi (k: indicesir; x: sir): boolean;
var s: integer;
var i: indicesir;
begin
s := 0;

for i := 1 to k do

inc (s, x [i]);
ffi := (s = 3)
end;

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

for i to n do

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

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

if (level > maxsir) or (level < 1) then
exit;

if (np > maxsir) or (np < 1) then
exit;

if level <= np then

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

x [level] := i;

if ffi (level, x) then

prelucreaza_solutie (level, x)
else if fi (level, x) then

btvr (level np, p, x)
end

end;

procedure btv (np: indicesir; p, x: sir);
var k: integer;
var ok, ok1, ok2: boolean;
begin
k := 1;
x [k] while k > 0 do
begin
repeat

inc (x [k]);

ok1 ffi (k, x);

ok2 fi (k, x);

ok ok1 or ok2 or (x [k] > p [k])
until ok;

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

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

end

else

dec (k)
end
end;

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

var x: sir;
begin

case tip of

recursiv: btvr np, p, x);
iterativ: btv (np, p, x)
end
end;

np := 3;

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

Modele de program in C⁶⁴

include <stdio.h>

define MAXSIR

define RECURSIV

define ITERATIV

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

define TRUE 1

define FALSE 0

// functia de continuare

int fi (int k, int x[])

// functia obiectivint ffi (int k, int x[])

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

// backtracking implementarea recursiva

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

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

if (x [k] <= p [k])
if (ok1)

prelucreaza_solutie (k, x);
else

else
k--;

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

void main ()

4. Generarea partitiilor unui intreg

4.1. Enuntul si consideratii

Problema: Sa se determine partitiile unui numar natural m.

Rezolvare: Notam cu x[1], x[2], , x[n] partitia lui n. In mod evident, avem ca

(1) ^ (n, x[1], x[2], , x[n]) = 'x[1] + x[2] + + x[n] = m'

Vom distinge 3 metode de abordare:

apelam intr-o secventa iterativa (FOR) determinarea partitiilor de lungime fixa egala cu
contorul;

modificam algoritmul BT sau BTR astfel incat sa se permita si valoarea 0 pentru varabilele
X[I]; in acest caz conventia este ca valoarea 0 reprezinta termen lipsa ;

construim o rezolvare bazata pe backtracking cu solutii de lungime variabila.

Pentru rezolvarea bazata pe solutii cu lungime variabila vom folosi functia obiectiv data de (1) si
functia de continuare de la paragraful precedent.

4.2. Programul in limbajul Pascal

program partitiile_unui_intreg;

const maxsir = 100;

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;
var s: integer;
var i: indicesir;
begin
s := 0;

for i := 1 to k do

inc (s, x [i]);
fi (s < np)
end;

function ffi (k: indicesir; x: sir): boolean;
var s: integer;
var i: indicesir;
begin
s := 0;

for i := 1 to k do

inc (s, x [i]);
ffi (s np)
end;

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

for i := 1 to n do

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

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

if (level > maxsir) or (level < 1) then
exit;

if (np > maxsir) or (np < 1) then
exit;

if level <= np then

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

x [level] := i;

if ffi (level, x) then

prelucreaza_solutie (level, x)
else if fi (level, x) then

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

end;

procedure btv (np: indicesir; p, x: sir);
var k: integer;
var ok, ok1, ok2: boolean;
begin
k := 1;
x [k] while k > 0 do
begin
repeat

inc (x [k]);

ok1 := ffi (k, x);

ok2 := fi (k, x);

ok ok1 or ok2 or (x [k] > p [k])
until ok;

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

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

else

dec (k)
end
end;

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

var x: sir;

begin

case tip of

recursiv: btvr (1, np, p, x);
iterativ: btv (np, p, x)
end
end;

var i: indicesir;
begin

writeln ('Generarea partitiilor unui intreg n');
write ('n=');
readln (np);
for i := 1 to np do
p [i] := np;

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

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

4. Programul in limbajul C

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[])

// functia obiectiv

int ffi (int k, int x[])

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

backtracking implementarea recursiva

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

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

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

else
k--;

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

void main ()

4.4. Exercitii si probleme

Modificati programul principal de la generarea partitiilor de lungime fixa pentru a rezolva
problema generarii partitiilor folosind metoda iterativa

Modificati algoritmul BT pentru a permite si valoarea 0 in multimile Mi.

Modificati algoritmul BTR pentru a permite si valoarea 0 in multimile M_;.

Cum se modifica functia de continuare in cazul folosirii valorii nule ca marca a termenului
lipsa?

Cum se modifica procedura de afisare in cazul folosirii valorii nule ca marca a termenului lipsa?

Demonstrati ca functia de continuare aleasa la rezolvarea problemei este cea mai buna functie
de continuare.

4.5. Rezolvarea exercitiilor si problemelor

1. Codul sursa este:

in limbajul Pascal:

var i: indicesir;
begin

writeln ('Generarea partitiilor lui n');
write ('n=');
readln (np);
for i := 1 to np do
begin

p [i] := np;

backtracking (iterativ, i, p)
end

end.

ii. in limbajul C:

void main

modificarile sunt legate de initializarile cu -1 in loc de 0 a elementelor vectorului x.

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

; prima modificare !!!
x [k] := -1

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

prelucreaza_solutie (np, x)
Altfel

incrementeaza (k)
; a doua modificare !!!
x [k] := -1

Sfarsit Daca

Altfel

decrementeaza (k)
Sfarsit Daca
Sfarsit Cat Timp
Sfarsit Subprogram

modificarea consta in marirea intervalului parcurs de i prin modificarea limitei inferioare de la
1 la 0:

subprogram btr (level, np, p, x)
daca level = np + 1 atunci

apel prelucreaza_solutie (np, x)
altfel

; aici e modificarea !!!

pentru i := 0, p [level] executa

x [level] := i;

daca fi (level, x) then

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

sfarsit daca

sfarsit pentru

sfarsit daca

sfarsit subprogram

Functia de continuare va fi:

k(x[1], x[2], ,x[k]) = Zk(x[1], x[2], ,x[k]) a 'x[1] + x[2] + + x[k] <= m' pentru k<n
k(x[1], x[2], ,x[k]) = Zk(x[1], x[2], ,x[k]) a 'x[1] + x[2] + + x[k] = m' pentru k=n,

unde Z_k este conditia ca elementele nule sa fie toate grupate la inceput:

Zk(x[1], x[2], ,x[k]) = 'x[k]<>0 OR (x[k]=0 AND x[k-1]=0)', pentru k>1
Zk(x[1], x[2], ,x[k]) = 'adevarat', pentru k=1.

Codul sursa este:

i. in limbajul Pascal:

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i, k: indicesir;
begin
k := 1;

while x [k] = 0 do
k := k + 1;
write (p [1], ' = ', x [k]);
for i := k + 1 to n do
write (' + ',x [i]);
writeln
end;

ii. in limbajul C:

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

6. Deoarece x[1] + x[2] + + x[k] < n, rezulta ca exista cel putin un termen astfel incat sa
obtinem o solutie partiala.