�ݺ�ߣ

Optimizare combinatorie
TAP
INFO II
TI II

Introducere
O problemă de optimizare (PO) este:
unde:
(funcţia obiectiv); pe B există o relaţie totală
de ordine; opt este criteriul de optimizare (max sau min);
constr este mulţimea de constrângeri.
Exemplu
echiv:
)
,
,
,
,
( constr
opt
B
A
f
B
A
f 
:
R
x
x
x
x
constr
x
x
x
x
f
R
R
f
constr
R
R
f









}
131
)
ln(
,
17
7
{
4
5
2
)
(
:
)
max,
,
,
,
(
3
10
4
7








131
)
ln(
17
7
)
4
5
2
(
max
3
10
4
7
x
x
x
x
x
x
R
x

Introducere
Soluţiile fezabile ale unei probleme de optimizare:
Soluţiile (valorile optime ale) unei probleme de optimizare:
)}
),
(
(
)
(
|
{ F
S
y
y
f
opt
x
f
A
x 


}
|
{ constr
valideaza
y
A
y
S
F 


Introducere
O problemă de optimizare combinatorie (POC) este o
problemă de optimizare unde A este produsul cartezian
al unor mulţimi (soluţia problemei se exprimă prin
combinaţii).
Obs. De obicei, A este puterea unei mulţimi.
Exemplu
N
x
x
x
x
x
x
x
x
x
x
x
constr
x
x
x
x
x
x
x
f
R
N
f
constr
R
N
f













3
2
1
3
1
2
1
3
3
2
1
3
2
2
1
3
2
1
3
3
,
,
}
28
5
2
4
,
17
{
4
5
2
)
,
,
(
:
)
max,
,
,
,
(

Introducere
Soluţiile fezabile ale unei POC:
Soluţiile (valorile optime ale) unei POC:
Soluţiile parţiale ale unei POC:
Obs. 1.
Obs. 2. Unii algoritmi generează spaţii mai largi de soluţii, pe
care apoi le triază (slides 16 şi 19).
P
F S
S 
)}
),
(
(
)
(
|
)
,
,
(
{ 2
1 F
n S
y
y
f
opt
x
f
A
x
x
x
x 


 
}
|
)
,
,
,
(
{ 2
1 constr
valideaza
y
A
y
y
y
y
S n
F 

 
}
1
|
)
,
,
,
(
{ 2
1 n
k
y
y
y
y
S k
P 


 

Probleme de optimizare
combinatorie
Problemele de optimizare combinatorie sunt prezente în
viaţa de zi cu zi şi sunt studiate intens de cercetători.
Domenii de interes: Matematică, Cercetare operaţională,
Algoritmică, Inteligenţa Artificială, Complexitatea
calculului.
Exemple de POC
• Probleme de alocare (Problema alocării liniare, Problema
alocării pătratice);
• Probleme de fluxuri în grafuri (Problema arborelui minim
de acoperire, Problema fluxului maxim);
• Probleme de transport (Problema comis-voiajorului,
Problema rutării vehiculelor).

combinatorie
Caracteristicile POC:
• uşor de formalizat
• spaţiu uriaş de căutare
• dificile (cu câteva excepţii - cele mai cunoscute excepţii:
Problema arborelui minim de acoperire; Problema
alocării liniare).

combinatorie
• Formalizare simplă
Problema alocării liniare:
Dată o matrice C(nxn) de valori pozitive,
să se aleagă n valori aflate pe linii şi
coloane diferite şi care au suma minimă.
Problema comis-voiajorului:
Dat un graf cu ponderi pozitive G(V,E,d),
să se găsească un circuit hamiltonian
de cost minim.
n
j
i
x
n
j
x
n
i
x
x
c
ij
n
i
ij
n
j
ij
n
i
n
j
ij
ij














 


 
,
1
}
1
,
0
{
1
1
1
1
min
1
1
1 1
V
j
i
x
V
S
x
V
j
x
V
i
x
x
d
ij
S
i S
V
j
ij
E
ij
ij
E
ij
ij
E
ij
ij
ij












 



 



,
}
1
,
0
{
1
1
1
min

)
(
)
(
)
(

combinatorie
• Spaţiu uriaş de căutare
Dacă n = 100, atunci spaţiul de soluţii
fezabile pentru Problema alocării liniare
are __________ elemente.
n
j
i
x
n
j
x
n
i
x
x
c
ij
n
i
ij
n
j
ij
n
i
n
j
ij
ij














 


 
,
1
}
1
,
0
{
1
1
1
1
min
1
1
1 1

combinatorie
• Spaţiu uriaş de căutare
Dacă n = 100, atunci spaţiul de soluţii
fezabile pentru Problema alocării liniare
are 100! (aprox. 9x10167) elemente.
Atomii din Univers: 1080
n
j
i
x
n
j
x
n
i
x
x
c
ij
n
i
ij
n
j
ij
n
i
n
j
ij
ij














 


 
,
1
}
1
,
0
{
1
1
1
1
min
1
1
1 1

combinatorie
• Dificile (cu câteva excepţii)
Nu s-au găsit algoritmi de complexitate polinomială care să
le rezolve.
Clasa problemelor pentru care există algoritmi polinomiali de
rezolvare se numeşte P (Probleme Polinomiale).
Hungarian Method este un algoritm polinomial pentru
Problema alocării liniare; deci Problema alocării liniare este
în P .
Există algoritmi care nu au complexitate polinomială:
forţa brută pentru Problema alocării liniare este O(n!).
Aceşti algoritmi se numesc exponenţiali.





 k
n n
n
k
!
lim
1

combinatorie
• Dificile (cu câteva excepţii)(cont.)
Toţi algoritmii cunoscuţi pentru Problema comis-voiajorului
sunt exponenţiali.
Dar nu s-a demonstrat că nu există algoritmi polinomiali
care s-o rezolve.
Problema comis-voiajorului este în clasa NP (probleme
Nedeterminist – Polinomiale).

Metode de rezolvare
pentru POC
1. Forţa brută (metodă exactă):
Inspectarea tuturor soluţilor fezabile (din );
2. Metode “prin eliminare” (cutting) (metode exacte):
Se elimină din zonele pentru care se demonstrează că nu
conţin soluţii;
3. Metode aproximative:
Se găseşte o soluţie fezabilă pentru care se demonstrează că
funcţia obiectiv este apropiată de valoarea optimă
(calitatea soluţiei este garantată);
4. Metode euristice:
Se caută o soluţie fezabilă obţinută rapid (nici găsirea soluţiei
şi nici calitatea sa nu sunt garantate).
5. Calcul concurent (creşterea vitezei de calcul).
F
S
F
S

1. Forţa brută
(Căutare exhaustivă)
Este recomandată dacă nu este foarte mare.
Exemplu
Se dă un graf planar complet cu n noduri (puncte de interes +
distanţe între ele).
Să se determine distanţa maximă parcursă de un turist care
are 3 bilete de transport (între orice 2 puncte se
validează un bilet).
F
S

2. Metode “prin eliminare”
(Cutting methods)
Se construieşte un arbore. Nodurile corespund unor
submulţimi ale lui . Rădăcina corespunde lui . Fiii
fiecărui nod se obţin printr-o metodă de partiţionare
(branch) a mulţimii corespunzătoare nodului respectiv.
Când submulţimea corespunzătoare devine vidă,
ramura se închide.
Exemple: Backtracking; Branch and bound.
F
S F
S

Problema alocării liniare
9 2 7
C = 6 4 3
5 8 1
S conţine toate combinaţiile posibile;
Back la slide 5
3
}
3
,
2
,
1
{
)}
333
(
),
332
(
),
331
(
),
113
(
),
112
(
),
111
{( 
 
S
16
8
6
2
))
212
(( 



f

2.1. Backtracking
Parcurgere în adâncime. Pentru nivelul 1 se partiţionează
Pe nivelul 2 se închid 3 ramuri (care? de ce?), etc…
)}
333
(
,
),
311
{(
)},
233
(
,
),
211
{(
)},
133
(
,
),
111
{( 3
2
1 

 

 S
S
S

2.2. Branch and bound
În plus, fiecare nod are asociată o limită (bound) a funcţiei
obiectiv pe submulţimea corespunzătoare nodului.
Când limita arată că pe ramura respectivă nu se poate
găsi o soluţie, ramura se închide şi deci submulţimea
corespunzătoare este eliminată.
Backtracking / Branch and bound:
• Limita (bound) este de aşteptat să închidă mai curând
ramuri, deci Branch and bound să fie mai rapid.
• Nu există reţetă pentru găsirea limitei. Dacă limita este
slab aleasă, atunci închiderea este întârziată.

Problema este de minimizare. Se caută o limită inferioară
(lower bound). Se alege:
lower_bound(nod) = suma elementelor minime de pe fiecare
rând nealocat.
Nu trebuie să fie realizabilă! Back la slide 5
16
5
4
7
)
(
_
6
1
3
2
)
(
_
13
1
3
9
)
(
_
)}
333
(
,
),
311
{(
)},
233
(
,
),
211
{(
)},
133
(
,
),
111
{(
6
1
3
2
)
(
_
)}
333
(
),
332
(
),
331
(
,
),
113
(
),
112
(
),
111
{(
3
2
1
3
2
1




















S
bound
lower
S
bound
lower
S
bound
lower
S
S
S
S
bound
lower
S





Parcurgere pe lăţime. Pentru nivelul 1 se partiţionează la fel
Se continuă cu nodul cel mai promiţător de pe nivel (al doilea).
)}
333
(
,
),
311
{(
)},
233
(
,
),
211
{(
)},
133
(
,
),
111
{( 3
2
1 

 

 S
S
S
)}
233
(
),
232
(
),
231
{(
)},
223
(
),
222
(
),
221
{(
)},
213
(
),
212
(
),
211
{( 23
22
21 

 S
S
S

se închide
Cel mai promiţător nod (primul) se expandează. Se închid primii doi fii.
f((213))=9. Se compară această valoare cu toate limitele nodurilor
neînchise. Toate valorile rămase sunt mai mari, deci toate se închid.
10
5
3
2
)
(
_
9
1
6
2
)
(
_
23
22
21








S
bound
lower
S
S
bound
lower

Backtracking:
• a necesitat 10 expandări;
• nu optimizează, ci generează toate soluţiile fezabile.
Branch and bound:
• a necesitat 3 expandări;
• optimizează, deci generează doar soluţiile.
Ambele sunt metode exacte.

Bibliografie
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=8F21042F327
F09D82513A121EF269861?doi=10.1.1.5.7475&rep=rep1&type=p
df
http://www.youtube.com/watch?v=BUGIhEecipE
http://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/07a
ssignment.pdf
http://www.mutah.edu.jo/userhomepages/CS252/branchandbound.html
http://mat.gsia.cmu.edu/orclass/integer/node13.html#SECTION000420
00000000000000
http://intelligence.worldofcomputing.net/ai-search/brute-force-
search.html
https://www.youtube.com/watch?v=0PM10vOtd6o

�ݺ�ߣ

5 optimizare combinatorie logica critical

More Related Content

5 optimizare combinatorie logica critical