Zagadnienie TSP (komiwojażer) złożoność obl.
O(n
2
)
1
Zagadnienie to jest opisane: (G,a)
G- graf,
a – funkcja.
+
→
∈
R
E
a
G=(V,E) łuki i wierzchołki
Alg. NN_TSP (
nearest neighbour TSP
)
Założenie: Każde miasto ma obchodzić raz. (tak działa ten alg.), Więc w
rozwiązaniu każdy wierzchołek pojawi się tylko raz a co dalej prowadzi do
wniosku, że rozwiązania będą permutacjami wszystkich miast.
(
)
)
(
),...,
2
(
),
1
(
n
π
π
π
π
=
1.
=
:
)
1
(
π
dowolne miasto,
2.Dla j=2 do n oblicz:
{
}
)}}
1
(
),...,
1
(
{
{
:
min
arg
:
)
(
)
1
(
−
−
∈
=
−
j
V
k
a
j
k
j
π
π
π
π
Złożoność obliczeniowa dla kroku 2:
Szukamy minimum od j =2 do n, więc
[
]
1
...
)
2
(
)
1
(
1
+
+
−
+
−
n
n
C
- jest to wielomian stopnia 2 , więc
złożoność obliczeniowa wynosi
O(n
2
).
Metoda optymalizacji lokalnej.
Klasyczny (podstawowy) algorytm optymalizacji lokalnej (OL)
1.Wybierz x
startowe
i podstaw x:=x
st
.
( x
st
wyznaczamy przy pomocy
algorytmu konstrukcyjnego)
2.Spróbuj znaleźć x’ takie, że:(dla minimalizacji)
)
(
'
_
_
)
(
)
'
(
x
N
x
dla
x
Q
x
Q
∈
<
- N(x) jest otoczeniem,
3.Jeżeli istnieje x’ to podstaw x:=x’ i przejdź do kroku 2)
Inaczej x
0
:=x
, // x
0
rozwiązanie optymalne w otoczeniu N(x)
Algorytm MSLS (LO) (
Multiple Start Local Search
)
(algorytm ten wykorzystuje większą liczbę rozwiązań początkowych)
(przykład dla minimalizacji)
0.(krok podstawowy)
∞
=
:
min
Q
(DDL –dostatecznie duża liczba)
1.Wybierz x
st.
I podstaw x:=x
st.
2.Spróbuj znaleźć x’ takie, że:
)
(
'
_
_
)
(
)
'
(
x
N
x
dla
x
Q
x
Q
∈
<
3.Jeśli istnieje x’ to x:=x’ i idź do punktu 2
4.Podstaw
{
}
)
(
,
min
:
min
min
x
Q
Q
Q
=
,
// Q(x) lokalnie optymalne
Jeśli koniec
(warunek stopu dla tego algorytmu był ponoć podawany na
poprzednim wykładzie)
to STOP inaczej idź do 1
____________________________________________________________
Kolejny algorytm klasyczny:
2
Algorytm ze zmiennym otoczeniem VNS (
Variable Neighbour Search
)
1.Wybierz p i q takie, że p<q<n
2.Wybierz (x
startowe
) x
st
i x:=x
st
3.Spróbuj znaleźć x’
)
(
)
'
(
x
Q
x
Q
<
dla
)
(
'
x
Np
x
∈
-// najmniejszego otoczenia
4.Jeżeli istnieje x’ to x:=x’ i przejdź do 3
5.Dla r=p+1 do q, spróbuj znaleźć x’
)
(
)
'
(
x
Q
x
Q
<
dla
)
(
'
x
Nr
x
∈
// q nie może być zbyt duże bo
rośnie czas obliczeń
6.Jeżeli znaleziono x’ to x:=x’ i przejdź do 3
Inaczej .................
Algorytm TS
(Tabu Search)
(eksploatuje pamięć, gdzie zawarte są
informacje n/t procesu przeszukiwania)
Rozwiązania, które podczas przeszukiwania uznaliśmy za optymalne
umieszczamy na liście TL
(Tabu List),
jest to podstawowa zasada
działania algorytmu TS. Istnieje jednak pewien problem z każdym
krokiem na TL będzie pojawiać się coraz więcej rozwiązań, porównywanie
ich za każdym razem powoduje powstanie DUŻYCH kosztów
obliczeniowych.
{
}
n
x
x
x
x
TL
,...,
,
2
1
=
−
Aby udoskonalić algorytm wprowadzono listę krótkoterminową –
rozwiązania są na liście tylko kilka iteracji.
T – parametr określający długość przebywania rozwiązania na liście TL.
Na liście są umieszczane tylko atrybuty ruchu, które zabraniają pewnego
typu przejścia. Może się jednak zdarzyć sytuacja, kiedy poprzez
wprowadzenie ograniczeń nie będzie możliwe przejście do innych stanów
leżących w bliskim sąsiedztwie rozwiązania znajdującego się na TL. Aby
uniknąć takich sytuacji przeglądamy też rozwiązania zabronione i jeżeli
wśród nich jest bardzo dobre rozwiązanie to zdejmujemy z niego
kryterium
TABU
. Opisane tutaj postępowanie nosi nazwę Kryterium
aspiracji.
Algorytm TS {
pamięć krótkotrwałą, kryterium aspiracji
}
1.Wybierz x
st
i podstaw x
a
=x
st
, x
min
:=x
st
, Q
min
:=Q(x
st
)
// zapamiętanie
bieżącego najlepszego rozw.
TL:={0}
// zbiór pusty
2.Nowe rozwiązanie
{
}
a
a
n
x
x
TL
x
x
N
x
x
Q
x
≠
∉
∈
=
,
),
(
:
)
(
min
arg
:
- dozwolone
Stosujemy regułę największej poprawy
(opisana wcześniej – patrz W2)
{
}
TL
x
x
N
x
x
Q
x
a
tabu
∈
∈
=
),
(
:
)
(
min
arg
:
- zabronione
3.Przejście
a) x
a
:=x
nowe
jeżeli
min
)
(
Q
x
Q
a
<
to x
min
:=x
a
,
)
(
min
a
x
Q
Q
=
b)
(kryterium aspiracji)
Jeżeli:
min
)
(
Q
x
Q
zabr
<
to: x
a
:=x
tabu
, x
min
:=x
tabu
,
)
(
min
zabr
x
Q
Q
=
(
zdejmujemy status zabronione dla danego rozwiązania)
4.Modyfikowanie TL
{ }
a
x
TL
TL
∪
=
:
-
// nie są to rozwiązania tylko atrybuty przejść
oraz usuń rozwiązania, które było na TL dłużej niż T iteracji.
5.Warunek stopu
Jeżeli STOP
(ponoć warunek STOP’u może być dowolny: np. gdy słońce
wzejdzie na zachodzie to STOP)
to drukuj: (x
min
, Q
min
–
najlepsze
rozwiązania znalezione przez algorytm
)
Inaczej przejdź do 2.
____________________________________________________________
MTSP
TSP
≡
3
(Multiple TSP – zagadnienie z wieloma komiwojażerami)
1.mTSP
a)m – liczba komiwojażerów znajdujących się w mieście początkowym o
numerze (n+1) gdzie (n+1) jest też miastem końcowym.
b)Każdy z komiwojażerów musi odwiedzić przynajmniej jedno miasto
Każde miasto musi być odwiedzone
funkcja celu: minimalizacja łącznej długości drogi komiwojażerów.
Odległość między miastami standardowo są opisane w tablicy
[ ]
A
a
n
n
ij
=
+
+
_
1
)(
1
(
Zamieniamy problem MTSP na TSP
Zwiększamy pozornie liczbę miast (wprowadzamy dodatkowe pozorne
miasto (n+2), które jest kopią miasta (n+1) )
Po wprowadzeniu dodatkowych miast musimy dla nich stworzyć tablicę.
Powiększamy o m-1 miast, więc łącznie otrzymamy n+m miast.
Tw1:
Dla każdej drogi l o skończonej długości zagadnienie jednego
komiwojażera z n+m miastami odległość, których określa tablica A
m
istnieje droga do zagadnienia m – komiwojażerów z N+1 miastami
określona przez macierz A o długości równej długości drogi l.
2) m
*
≤≤≤≤
mTSP
m
*
- zmienna decyzyjna
od góry jest ograniczona liczba komiwojażerów (jest ich tyle, aby suma
całkowitej długości trasy była minimalna, tak dobieramy liczbę
komiwojażerów)
m
*
≤
m komiwojażerów jest w mieście n+1
każdy z m
*
komiwojażerów odwiedza przynajmniej
jedno miasto
każde miasto musi być odwiedzone
, A,E,G takie same jak w poprzednim przypadku,
dopuszczamy jednak przejścia z miasta pozornego do
pozornego koszt=0, ten komiwojażer pozostanie w bazie, F=[0].
Tw2:
Dla każdej drogi l o skończonej długości zagadnienie 1 komiwojażera z n+
m
*
miastami (m
*
- ograniczone z góry) określonym przez powyższą
tablicę, istnieje droga zagadnienie m
*
≤
m z m+1 miastami (m
*
- określa
nam liczbę komiwojażerów) – określone tablicą A o długość równej
długości drogi l.
Metoda podziału ograniczeń (B&B Breanch And Bound)
4
(Jeżeli obliczenia będą trwały do końca to otrzymamy rozwiązanie
optymalne. Jeżeli przerwiemy obliczenia wcześniej to otrzymamy
rozwiązanie przybliżone. Skracanie czasu obliczeń jest podstawową
metodą optymalizacji w przypadku skomplikowanych problemów)
Problem:
{
}
)
(
:
)
min
)
(
P
X
x
x
Q
P
v
∈
=
Dokonujemy podziału problemu P na mniejsze. Podziałem problemu P
będziemy nazywać ciągi:
q
P
P
P
,...,
,
2
1
- jeżeli spełniony jest warunek:
U
q
i
i
P
X
P
X
1
)
(
)
(
=
=
, gdzie:
{
}
)
(
:
)
(
min
)
(
i
i
P
X
x
x
Q
P
v
∈
Często przyjmuje się:
0
)
(
)
(
=
∩
j
i
P
X
P
X
- nie jest to warunek konieczny !!!
Jeżeli spełniony jest powyższy warunek to obszar jest przeszukiwany tylko
raz.
Jeżeli rozwiążemy każdy podproblem to:
)
(
min
)
(
i
P
v
P
v
=
.
Analiza podproblemu (
oparta na zasadzie relaksacji
)
(relaksacje przeprowadzamy tak długo aż otrzymamy problem
rozwiązywalny w czasie wielomianowym)
)
(
)
(
RP
X
P
X
⊂
- X(RP) – zrelaksowany, X(P) – wyjściowy
{
}
)
(
:
)
(
min
)
(
RP
X
x
x
Q
RP
v
∈
=
Własność 1)
Jeżeli
0
)
(
0
)
(
=
⇒
=
i
P
X
RP
X
(sprzeczny) -> z tego
wynika pierwsze kryterium zamykania KZ1
KZ1: Jeżeli X(RP
i
)=0 to P
i
zamykamy.
Własność 2)
Jeżeli
)
(
)
(
i
i
RP
v
P
v
≥
<- dalsze ograniczenie dla
)
(
i
P
v
KZ2 – drugie kryterium zamykania
KZ2: Jeżeli
*
)
(
v
RP
v
i
≥
(V*-
wartość odcinająca, wartość funkcji celu
najlepszego rozwiązania
) to P
i
zamykamy.
Warto na początku przy pomocy dobrych algorytmów znaleźć dobre
rozwiązanie wtedy łatwiej będzie zamykać podproblemy (np. całe
poddrzewa).
____________________________________________________________
Własność 3)
5
Jeżeli rozwiązanie optymalne RP
i
jest rozwiązaniem dopuszczalnym dla P
i
to rozwiązanie to jest rozwiązaniem optymalnym P
i
czyli:
)
(
)
(
i
i
RP
v
P
v
=
.
KZ3: Jeżeli rozwiązanie optymalne RP
i
jest dopuszczalne dla P
i
to P
i
zamykamy.
(
otrzymaliśmy nowe rozwiązanie, trzeba sprawdzić czy nie jest lepsze od
V*, ten warunek umieszczamy w KZ3 a nie w algorytmie ... trochę to
dziwne .... ale prof.K.Wala tak chciał
)
Jeżeli
)
(
i
RP
v
jest lepsze od V* to
)
(
:
*
i
RP
v
v
=
.
Algorytm podziału ograniczeń.
Tworzymy listę kandydatów na której znajdują się wszystkie nie
zamknięte problemy.
Algorytm B&B
1.
{ }
P
LK
=
:
- LK – lista kandydatów
∞
=
:
*
v
( albo jeżeli znamy x
przybl.
to
)
(
*
przybl
x
Q
v
=
,
x
przybl
znajdujemy pewnym algorytmem
) – V* -
wartość odcinająca
2.Wybór kandydata
Jeżeli
}
0
{
=
LK
to STOP V* jest rozwiązaniem optymalnym
(
dokładniej V* jest wartością rozwiązania optymalnego, ale oczywiście za
każdym razem kiedy zapamiętujemy wartość to pamiętamy też
rozwiązanie jej odpowiadające i vice versa !!!
)
Inaczej
KP:=wybór z listy kandydatów
(KP- kandydat problemu).
Wyboru KP dokonujemy przy pomocy reguł zdroworozsądkowych.
1.Rozwiąż PKB (zrelaksowanego KP) stosując algorytm, który wyznacza
rozwiązanie optymalne.
2.Analiza KP za pomocą kryteriów
KZ1, KZ2, KZ3
3.Jeżeli
KP
jest zamknięty to usuń z listy i przejdź do kroku 2
Podziel KP
i
i jego następniki dołącz do listy LK i przejdź do kroku 2.
Algorytm szeregowania listowego (krótki wstęp)
n
j
x
j
,...,
2
,
1
,
=
- poszczególnym składowym przyporządkujemy
priorytet W
j
,
j
j
w
x
→
(na podstawie pewnych niejasnych
parametrów prawdopodobnie zależnych od problemu itp.)
Składowe porządkujemy zgodnie z priorytetem -> otrzymujemy listę
składowych. Kolejnym składowym z listy przyporządkowujemy max lub
min (dopuszczalne) wartości. W ten sposób konstruujemy jedną ścieżkę
(z korzenia drzewa do rozwiązania końcowego)
____________________________________________________________
Algorytm SL (szeregowania listowego)
6
1.
j
∀
oblicz W
j
(priorytet)
2.Tworzymy listę
‘L’
– poszczególne składowe rozwiązania (zmienne
decyzyjne) porządkujemy od największego/najmniejszego priorytetu
Wybierz kolejną współrzędną i przedziel jej największą/najmniejszą
dopuszczalną wartość (musi działać kryterium KZ1)
Algorytm SL dla 0-1 KP(binarne plecakowe) i GKP(plecakowe)
1.Uporządkuj obiekty (numery – nazwy obiektów) tak aby:
j
n
n
w
a
c
a
c
a
c
w
=
≥
≥
≥
=
...
2
2
1
1
1
2. Dla maksymalizacji:
Dla j=1 do n wykonaj
GKP:
=
j
j
a
b
x
0-1 KP:
=
j
j
a
b
x
,
1
min
j
j
x
a
b
b
−
=
:
- zmniejszamy pojemność plecaka
Znajdujemy rozwiązanie przybliżone, trzeba je oszacować -> relaksacja.
Znalezione przez powyższy algorytm<-
(
)
SL
e
przybliżrz
Q
Q
SL
KP
GKP
Q
Q
v
UB
R
≥
≥
=
−
*
1
0
)
(
<- oszacowane
Jak wygląda relaksacja dla tego problemu? Przyjmujemy, że przedmiot
można podzielić.
Oszacowanie dla GKP:
(
)
1
1
a
b
c
GKP
R
v
=
−
(*** Przyjmuje się, że:
j
j
a
c ,
- są całkowite
⇒
funkcja celu
przyjmuje wartości całkowite ***)
(
)
SL
Q
Q
a
b
c
GKP
R
v
≥
≥
=
−
*
1
1
TW: Dantzig’a
Rozwiązanie optymalne 0-1 KP z relaksacją:
1
0
≤
≤
j
x
- tzn, że można uciąć przedmiot
ma postać:
(będzie tylko jedna współrzędna różna od 0 lub 1)
s
j
dla
x
j
,...,
2
,
1
:
,
1
:
=
=
n
s
j
dla
x
j
,...,
2
:
,
0
:
+
=
=
Składowa s+1, ten przedmiot dzielimy.
1
1
1
:
+
=
+
∑
−
=
s
s
j
j
s
a
a
b
x
- tyle ładujemy
przedmiotu ile jest miejsca w plecaku, gdzie
s-max liczba taka, że:
∑
=
≤
s
i
j
j
b
a
.
Wniosek:
7
- cecha jest dlatego, że funkcja celu musi przyjąć wartość całkowitą.
Złożoność obliczeniowa Algorytmu SL:
SL
)
log
(
n
n
O
- musimy użyć algorytmu sortowania i to jest koszt
sortowania, wszystkie algorytmy bazujące na SL mają podobną złożoność
obliczeniową, są to bardzo szybkie algorytmy.
Złożoność obliczeniowa.
NP. – problemy decyzyjne (rozw. W czasie wielomianowym przez
niedetermistyczną maszynę Turinga)
P –problemy wielomianowe, odpowiedź uzyskuje się w czasie
ograniczonym przez wielomian charakteryzujący problem.
Zagadnienie NP. interpretujemy jako takie, które można rozwiązać
przeglądając rozwiązania na drzewie stosując pełny przegląd rozwiązań
częściowych za pomocą algorytmu cofania (Back Track Search ...)
P – rozwiązanie problemu otrzymujemy w czasie ograniczonym przez
wielomian
Jak stwierdzić czy problem należy do klasy problemów wielomianowych?
Wykazać, że algorytm znajduje rozwiązanie (TAK/NIE)
Prześledzić złożoność algorytmu i wykazać, że
złożoność jest wielomianowa
Jeżeli warunki są spełnione to problem należy do P.
NP
P
⊂
- zachodzi
NP
P
=
- nie można stwierdzić (jak na razie prof. Wala nie znalazł
odpowiedzi na to niezwykle fascynujące pytanie ...)
NP.-zupełne
Def:
(
) (
)
1
1
:
ln
P
P
NP
P
e
zupe
NP
P
∝
∈
∀
⇔
−
∈
W klasie NP. wyróżniamy klasę problemów trudnych.
Z powyższej definicji wynika następujący wniosek:
⇔
=
NP
P
istnieje algorytm wielomianowy dla
.
zupel
NP
P
−
∈
Jak wykazać , że badany problem jest problemem NP.-zupełnym?
NP
P
∈
?
2
, wiemy, że jakiś problem
.
1
zupel
NP
P
−
∈
wystarczy więc wykazać:
(
)
.
2
1
2
zupel
NP
P
P
P
−
∈
⇒
∝
{
}
2
1
P
P
wszystkie
∝
∝
,
{
}
2
P
wszystkie
∝
________________________________________________
Twierdzenia:
8
TW1: Następujące problemy są NP.-trudne:
1.PODZIAŁ: dany jest skończony zbiór T i liczby
N
a
j
∈
,
T
j
∈
Pytanie czy
T
s
∈
∃
takie, że
∑
∑
∈
−
∈
=
s
j
s
T
j
j
j
a
a
(tzn. czy można
podzielić na dwa dokładnie równe)
2.ZAŁADUNEK: dane są liczy całkowite
n
a
a
a
,...,
,
2
1
oraz b
Pytanie czy
{
}
n
s
,...,
1
⊂
∃
takie, że:
b
a
s
j
j
=
∑
∈
(czy można
plecak dokładnie załadować)
3.CYKL HAMILTONA: dane jest graf G zwykły/skierowany
Pytanie czy istnieje cykl zwykły/skierowany HAMILTONA (jest to
decyzyjna wersja TSP)
Algorytm wyznaczanie Harmonogramowania
Algorytm LPT
1.Uporządkuj zadania w ciąg
(
)
)
(
),...,
1
(
n
π
π
π =
, tak aby:
)
1
(
)
(
+
≥
j
j
P
P
π
π
// O(nlogn)
2.Dla i=1 do m podstaw T(i):=0
3.j=1 do n wykonaj:
{
}
{
}
m
i
i
T
i
,...,
1
:
)
(
min
arg
*
∈
=
,
)
(
*
*
)
(
)
(
:
)
(
j
j
p
i
T
i
T
C
π
π
+
=
=
// O(n)
4.Oblicz
j
j
c
C
max
max
=
,
LB
C
≥
max
(
)
=
=
≥
∑
=
n
j
j
j
j
m
m
p
p
C
przerw
P
C
LB
C
1
max
max
*
max
,
max
max
|
|
,
P
j
-najdłuższe zadanie może limitować czas rozwiązania problemu. To
oszacowanie obowiązuje dla każdego algorytmu bo otrzymaliśmy je za
pomocą relaksacji.
_________________________________________________________
F
G
E
A
A
m
m
=
≤
*
∑
∑
=
+
=
+
−
+
=
s
j
s
n
j
j
s
j
a
a
b
c
c
UB
1
1
1
1
:
