Drzewo poszukiwań

dopuszczalnej

konfiguracji

- przegląd zupełny

Poszukiwa
nia w głąb

A
1

B
1

B
3

B
2

B
4

B
1

B
2

B
3

B
4

B
1

B
2

B
3

B
4

N - niekompatybilność

Nawro
ty

F - fail, konfiguracja

D - za duża cena

C
1

N

C
2

N

C
1

N

C
1

N

C
1

N

C
1

N

C
2

N

C
2

N

C
2

N

C
2

N

C
2

N

C
2

N

C
1

D

C
2

D

C
1

D

C
1

D

C
2

D

C
2

F

C
1

F

C
2

F

C
1

F

C
1

N

C
1

D

C
2

D

A3

A
2

Drzewo

inteligentnych

poszukiwań

dopuszczalnej

konfiguracji

Poszukiwa
nia
w głąb

A
1

B
1

B
2

B
3

B
1

B
4

B
4

N

B
2

C
1

N

C
2

N

C
1

N

C
1

N

B
3

N

N - niekompatybilność

Nawro
ty

F - fail, konfiguracja

D - za duża cena

C
1

F

C
2

F

C
2

D

C
2

F

C
2

N

B
1

D

B
2

D

B
4

D

C
2

N

C
1

F

C
1

D

A3

A
2

B
3

N

Drzewo

poszukiwań

optymalnej

konfiguracji

(„branch and

bound”)

Poszukiwa
nia
w głąb

A
1

B
1

B
2

B
3

B
1

B
4

B
4

N

B
2

C
1

N

C
2

N

C
1

N

C
1

N

B
3

N

N - niekompatybilność

Nawro
ty

Oi - konfiguracja optymalna i-
ta

Gi - konfiguracja gorsza od
Oi

C
1

O2

190

0

C
2

O2

190

0

C
2

G2

C
2

G2

C
2

N

C
2

N

C
1

G
2

C
1

G2

A3

A
2

C
1

O1

2900

B
1

C
2

G1

C
1

G1

B
2

C
2

N

C
1

G1

B
4

C
2

G1

B
3

N

O0 =
5000

Inne metody przybliżone

optymalizacji

kombinatorycznej

• Metody genetyczne
• Tabu Search
• Simmulated Annealing