Zagadnienie TSP (komiwojażer) złożoność obl. O(n2) 1 tablicę, istnieje droga zagadnienie m*d"m z m+1 miastami (m* - określa
x := 1, dla : j = 1,2,..., s
j
Zagadnienie to jest opisane: (G,a) nam liczbę komiwojażerów)  określone tablicą A o długość równej
G- graf, długości drogi l. x := 0,dla : j = s + 2,...,n
j
a  funkcja. Składowa s+1, ten przedmiot dzielimy.
a " E R+
s
G=(V,E) łuki i wierzchołki - tyle ładujemy
b - a
" j
j=1
Alg. NN_TSP (nearest neighbour TSP)
Metoda podziału ograniczeń (B&B Breanch And Bound) 4
xs+1 :=
Założenie: Każde miasto ma obchodzić raz. (tak działa ten alg.), Więc w
(Jeżeli obliczenia będą trwały do końca to otrzymamy rozwiązanie as+1
n
�ł śł
�ł �ł
rozwiązaniu każdy wierzchołek pojawi się tylko raz a co dalej prowadzi do
optymalne. Jeżeli przerwiemy obliczenia wcześniej to otrzymamy
a �ł
�łcs+1�łb - " j przedmiotu ile jest miejsca w plecaku, gdzie
śł
s �ł �ł
wniosku, że rozwiązania będą permutacjami wszystkich miast. j =1
�ł �ł łł śł
rozwiązanie przybliżone. Skracanie czasu obliczeń jest podstawową
UB := +
"c j s
�ł śł
as s-max liczba taka, że: .
j =1 +1
metodą optymalizacji w przypadku skomplikowanych problemów)
Ą = (Ą (1),Ą (2),...,Ą (n)) �ł śł
�ł śł d" b
�ł �ł "a j
1. dowolne miasto,
Problem:
Ą (1) := j=i
v(P) = min{Q)x : x " X (P)} Wniosek: 7
2.Dla j=2 do n oblicz:
Dokonujemy podziału problemu P na mniejsze. Podziałem problemu P
Ą ( j) := arg min{aĄ ( j-1)k : k "{V -{Ą (1),...,Ą ( j -1)}}}
- cecha jest dlatego, że funkcja celu musi przyjąć wartość całkowitą.
będziemy nazywać ciągi:
Złożoność obliczeniowa dla kroku 2:
- jeżeli spełniony jest warunek:
Szukamy minimum od j =2 do n, więc P1, P2 ,..., Pq
C1[(n -1) + (n - 2) + ... +1] - jest to wielomian stopnia 2 , więc , gdzie:
q v(Pi ) min{Q(x) : x " X (Pi )} Złożoność obliczeniowa Algorytmu SL:
SL - musimy użyć algorytmu sortowania i to jest koszt
O(n log n)
złożoność obliczeniowa wynosi O(n2).
X (Pi ) = X (P)
U
Metoda optymalizacji lokalnej. i=1 sortowania, wszystkie algorytmy bazujące na SL mają podobną złożoność
Klasyczny (podstawowy) algorytm optymalizacji lokalnej (OL) Często przyjmuje się: obliczeniową, są to bardzo szybkie algorytmy.
1.Wybierz xstartowe i podstaw x:=xst. ( xst wyznaczamy przy pomocy - nie jest to warunek konieczny !!! Złożoność obliczeniowa.
X (Pi ) )" X (Pj ) = 0
algorytmu konstrukcyjnego) NP.  problemy decyzyjne (rozw. W czasie wielomianowym przez
2.Spróbuj znalez
ć x takie, że:(dla minimalizacji) niedetermistyczną maszynę Turinga)
Jeżeli spełniony jest powyższy warunek to obszar jest przeszukiwany tylko
- N(x) jest otoczeniem, P  problemy wielomianowe, odpowiedz
uzyskuje się w czasie
raz.
Q(x') < Q(x) _ dla _ x'" N(x)
ograniczonym przez wielomian charakteryzujący problem.
Jeżeli rozwiążemy każdy podproblem to: .
3.Jeżeli istnieje x to podstaw x:=x i przejdz
do kroku 2) v(P) = min v(Pi )
Zagadnienie NP. interpretujemy jako takie, które można rozwiązać
Inaczej x0:=x , // x0 rozwiązanie optymalne w otoczeniu N(x)
przeglądając rozwiązania na drzewie stosując pełny przegląd rozwiązań
Analiza podproblemu (oparta na zasadzie relaksacji)
Algorytm MSLS (LO) (Multiple Start Local Search)
częściowych za pomocą algorytmu cofania (Back Track Search ...)
(relaksacje przeprowadzamy tak długo aż otrzymamy problem
(algorytm ten wykorzystuje większą liczbę rozwiązań początkowych)
P  rozwiązanie problemu otrzymujemy w czasie ograniczonym przez
rozwiązywalny w czasie wielomianowym)
(przykład dla minimalizacji)
wielomian
- X(RP)  zrelaksowany, X(P)  wyjściowy
X (P) �" X (RP)
0.(krok podstawowy)
Jak stwierdzić czy problem należy do klasy problemów wielomianowych?
(DDL  dostatecznie duża liczba)
Wykazać, że algorytm znajduje rozwiązanie (TAK/NIE)
Qmin := "
v(RP) = min{Q(x) : x " X (RP)}
Prześledzić złożoność algorytmu i wykazać, że
1.Wybierz x I podstaw x:=x
st. st.
Własność 1) złożoność jest wielomianowa
2.Spróbuj znalez
ć x takie, że:
Jeżeli warunki są spełnione to problem należy do P.
Jeżeli (sprzeczny) -> z tego
X (RP) = 0 �! X (Pi ) = 0
Q(x') < Q(x) _ dla _ x'" N(x)
- zachodzi
P �" NP
3.Jeśli istnieje x to x:=x i idz
do punktu 2 wynika pierwsze kryterium zamykania KZ1
4.Podstaw i i - nie można stwierdzić (jak na razie prof. Wala nie znalazł
P = NP
Qmin := min{Qmin ,Q(x)} , // Q(x) lokalnie optymalne KZ1: Jeżeli X(RP)=0 to P zamykamy.
Własność 2)
odpowiedzi na to niezwykle fascynujące pytanie ...)
Jeśli koniec (warunek stopu dla tego algorytmu był ponoć podawany na
Jeżeli <- dalsze ograniczenie dla
NP.-zupełne
v(Pi ) e" v(RPi ) v(Pi )
poprzednim wykładzie) to STOP inaczej idz
do 1
Def:
____________________________________________________________ (P1 " NP - zupeln e) �! ("P " NP : P " P1)
KZ2  drugie kryterium zamykania
Kolejny algorytm klasyczny: 2
KZ2: Jeżeli (V*- wartość odcinająca, wartość funkcji celu W klasie NP. wyróżniamy klasę problemów trudnych.
v(RPi ) e" v*
Algorytm ze zmiennym otoczeniem VNS (Variable Neighbour Search)
Z powyższej definicji wynika następujący wniosek:
1.Wybierz p i q takie, że pnajlepszego rozwiązania) to Pi zamykamy.
istnieje algorytm wielomianowy dla
2.Wybierz (x ) x i x:=x P = NP �!
startowe st st
Warto na początku przy pomocy dobrych algorytmów znalez
ć dobre
3.Spróbuj znalez
ć x
rozwiązanie wtedy łatwiej będzie zamykać podproblemy (np. całe
P " NP - zupel.
dla -// najmniejszego otoczenia poddrzewa).
Q(x') < Q(x) x'" Np(x)
Jak wykazać , że badany problem jest problemem NP.-zupełnym?
____________________________________________________________
4.Jeżeli istnieje x to x:=x i przejdz
do 3
Własność 3) 5
?
, wiemy, że jakiś problem
5.Dla r=p+1 do q, spróbuj znalez
ć x P1 " NP - zupel.
Jeżeli rozwiązanie optymalne RP jest rozwiązaniem dopuszczalnym dla P P2 NP
i i
dla // q nie może być zbyt duże bo
to rozwiązanie to jest rozwiązaniem optymalnym P czyli:
Q(x') < Q(x) x'" Nr(x) i
"
.
wystarczy więc wykazać:
rośnie czas obliczeń v(Pi ) = v(RPi )
6.Jeżeli znaleziono x to x:=x i przejdz
do 3
(P2 " P1) �! P2 " NP - zupel.
KZ3: Jeżeli rozwiązanie optymalne RPi jest dopuszczalne dla Pi to Pi
Inaczej .................
zamykamy.
Algorytm TS (Tabu Search) (eksploatuje pamięć, gdzie zawarte są
{wszystkie}" P1 " P2 , {wszystkie}" P2
(otrzymaliśmy nowe rozwiązanie, trzeba sprawdzić czy nie jest lepsze od
informacje n/t procesu przeszukiwania)
V*, ten warunek umieszczamy w KZ3 a nie w algorytmie ... trochę to
________________________________________________
Rozwiązania, które podczas przeszukiwania uznaliśmy za optymalne
dziwne .... ale prof.K.Wala tak chciał)
Twierdzenia: 8
umieszczamy na liście TL (Tabu List), jest to podstawowa zasada
Jeżeli jest lepsze od V* to .
działania algorytmu TS. Istnieje jednak pewien problem z każdym v(RPi ) v* := v(RPi )
TW1: Następujące problemy są NP.-trudne:
krokiem na TL będzie pojawiać się coraz więcej rozwiązań, porównywanie
Algorytm podziału ograniczeń. 1.PODZIAA
: dany jest skończony zbiór T i liczby ,
j "T
ich za każdym razem powoduje powstanie DUŻYCH kosztów a " N
Tworzymy listę kandydatów na której znajdują się wszystkie nie j
obliczeniowych.
zamknięte problemy.
Pytanie czy takie, że (tzn. czy można
"s "T
TL - x = {x1, x2 ,..., xn} Algorytm B&B
=
"a j "a j
1.
Aby udoskonalić algorytm wprowadzono listę krótkoterminową 
LK := {P} - LK  lista kandydatów
j"s j"T -s
rozwiązania są na liście tylko kilka iteracji.
( albo jeżeli znamy xprzybl. to , xprzybl podzielić na dwa dokładnie równe)
T  parametr określający długość przebywania rozwiązania na liście TL.
v* := "
v* = Q(xprzybl )
Na liście są umieszczane tylko atrybuty ruchu, które zabraniają pewnego 2.ZAA
ADUNEK: dane są liczy całkowite
a1, a2 ,...,an oraz b
typu przejścia. Może się jednak zdarzyć sytuacja, kiedy poprzez znajdujemy pewnym algorytmem)  V* - wartość odcinająca
wprowadzenie ograniczeń nie będzie możliwe przejście do innych stanów 2.Wybór kandydata
Pytanie czy takie, że: (czy można
"s �" {1,..., n}
leżących w bliskim sąsiedztwie rozwiązania znajdującego się na TL. Aby
Jeżeli = b
LK = {0} to STOP V* jest rozwiązaniem optymalnym "a j
uniknąć takich sytuacji przeglądamy też rozwiązania zabronione i jeżeli
j"s
wśród nich jest bardzo dobre rozwiązanie to zdejmujemy z niego (dokładniej V* jest wartością rozwiązania optymalnego, ale oczywiście za
kryterium TABU. Opisane tutaj postępowanie nosi nazwę Kryterium każdym razem kiedy zapamiętujemy wartość to pamiętamy też plecak dokładnie załadować)
rozwiązanie jej odpowiadające i vice versa !!! ) 3.CYKL HAMILTONA: dane jest graf G zwykły/skierowany
aspiracji.
Inaczej KP:=wybór z listy kandydatów (KP- kandydat problemu). Pytanie czy istnieje cykl zwykły/skierowany HAMILTONA (jest to
Algorytm TS {pamięć krótkotrwałą, kryterium aspiracji}
1.Wybierz x i podstaw x =x , x :=x , Q :=Q(x ) // zapamiętanie Wyboru KP dokonujemy przy pomocy reguł zdroworozsądkowych. decyzyjna wersja TSP)
st a st min st min st
bieżącego najlepszego rozw. TL:={0} // zbiór pusty 1.Rozwiąż PKB (zrelaksowanego KP) stosując algorytm, który wyznacza Algorytm wyznaczanie Harmonogramowania
rozwiązanie optymalne. Algorytm LPT
2.Nowe rozwiązanie
1.Uporządkuj zadania w ciąg
Ą = (Ą (1),...,Ą (n)) , tak aby:
xn := arg min{Q(x) : x " N(xa ), x "TL, x `" xa} - dozwolone 2.Analiza KP za pomocą kryteriów KZ1, KZ2, KZ3
3.Jeżeli KP jest zamknięty to usuń z listy i przejdz
do kroku 2
Stosujemy regułę największej poprawy (opisana wcześniej  patrz W2) Podziel KP i jego następniki dołącz do listy LK i przejdz
do kroku 2.
i
PĄ ( j) e" PĄ ( j+1) // O(nlogn)
xtabu := arg min{Q(x) : x " N (xa ), x "TL} - zabronione Algorytm szeregowania listowego (krótki wstęp)
2.Dla i=1 do m podstaw T(i):=0
- poszczególnym składowym przyporządkujemy
x , j = 1,2,...,n
3.Przejście j 3.j=1 do n wykonaj:
a) x :=x jeżeli to x :=x ,
a nowe min a priorytet Wj, (na podstawie pewnych niejasnych
i* = arg min{T (i) : i "{1,...,m}},
Q(xa ) < Qmin Qmin = Q(xa )
x �ł wj
�ł
j
// O(n)
b) (kryterium aspiracji)
parametrów prawdopodobnie zależnych od problemu itp.) CĄ ( j) = T (i*) := T (i*) + pĄ ( j)
Jeżeli: (
Składowe porządkujemy zgodnie z priorytetem -> otrzymujemy listę
Q(xzabr ) < Qmin to: xa:=xtabu , xmin:=xtabu, Qmin = Q(xzabr )
4.Oblicz ,
składowych. Kolejnym składowym z listy przyporządkowujemy max lub Cmax e" LB
Cmax = max c
zdejmujemy status zabronione dla danego rozwiązania) j
min (dopuszczalne) wartości. W ten sposób konstruujemy jedną ścieżkę
j
4.Modyfikowanie TL
(z korzenia drzewa do rozwiązania końcowego)
ół �ł ,
j =1
- // nie są to rozwiązania tylko atrybuty przejść m
j
____________________________________________________________
TL := TL *"{xa}
j " żł
Cmax e" LB = C* max (Pm | przerw | Cmax ) = max�łmax p ,
Algorytm SL (szeregowania listowego) 6 j
ńł p �ł
n
oraz usuń rozwiązania, które było na TL dłużej niż T iteracji.
1. oblicz Wj (priorytet)
"j
5.Warunek stopu
Pj -najdłuższe zadanie może limitować czas rozwiązania problemu. To
Jeżeli STOP (ponoć warunek STOP u może być dowolny: np. gdy słońce
2.Tworzymy listę  L  poszczególne składowe rozwiązania (zmienne
oszacowanie obowiązuje dla każdego algorytmu bo otrzymaliśmy je za
wzejdzie na zachodzie to STOP) to drukuj: (xmin, Qmin  najlepsze
decyzyjne) porządkujemy od największego/najmniejszego priorytetu
pomocą relaksacji.
rozwiązania znalezione przez algorytm)
Wybierz kolejną współrzędną i przedziel jej największą/najmniejszą
_________________________________________________________
Inaczej przejdz
do 2.
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:
3
TSP a" MTSP
c1 c2 cn
(Multiple TSP  zagadnienie z wieloma komiwojażerami)
w1 = e" e" ... e" = wj
1.mTSP a1 a2 an
a)m  liczba komiwojażerów znajdujących się w mieście początkowym o
2. Dla maksymalizacji:
numerze (n+1) gdzie (n+1) jest też miastem końcowym.
Dla j=1 do n wykonaj
b)Każdy z komiwojażerów musi odwiedzić przynajmniej jedno miasto
GKP: 0-1 KP:
Każde miasto musi być odwiedzone
ńł �ł
�ł śł�ł
�ł śł �ł b
b
funkcja celu: minimalizacja łącznej długości drogi komiwojażerów.
xj = min�ł1,
xj = �ł śł �ł śłżł
aj
Odległość między miastami standardowo są opisane w tablicy �ł �ł śł�ł
�łaj śł
�ł �ł �ł �ł�ł
ół
[aij] = A
- zmniejszamy pojemność plecaka
(n+1)(n +1 _
b := b - aj x
j
Zamieniamy problem MTSP na TSP
Znajdujemy rozwiązanie przybliżone, trzeba je oszacować -> relaksacja.
Zwiększamy pozornie liczbę miast (wprowadzamy dodatkowe pozorne
Znalezione przez powyższy algorytm<-
miasto (n+2), które jest kopią miasta (n+1) )
(Qprzybliżrz e)QSL
Po wprowadzeniu dodatkowych miast musimy dla nich stworzyć tablicę.
<- oszacowane
Powiększamy o m-1 miast, więc łącznie otrzymamy n+m miast. 0-1KP
UB = v( ) e" Q* e" QSL
Tw1: RGKP
Dla każdej drogi l o skończonej długości zagadnienie jednego Jak wygląda relaksacja dla tego problemu? Przyjmujemy, że przedmiot
komiwojażera z n+m miastami odległość, których określa tablica A można podzielić.
m
istnieje droga do zagadnienia m  komiwojażerów z N+1 miastami Oszacowanie dla GKP:
b
określona przez macierz A o długości równej długości drogi l.
v(R - GKP) = c1
2) m*d" mTSP
d"
d"
d"
a1
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ę (*** Przyjmuje się, że: cj , aj - są całkowite �! funkcja celu
komiwojażerów)
m* d" m komiwojażerów jest w mieście n+1 przyjmuje wartości całkowite ***)
każdy z m* komiwojażerów odwiedza przynajmniej
�ł b śł
jedno miasto v(R - GKP)= e" Q* e" QSL
�łc1 śł
a1
każde miasto musi być odwiedzone �ł �ł
A E
Am d"m =
* , A,E,G takie same jak w poprzednim przypadku, TW: Dantzig a
G F
dopuszczamy jednak przejścia z miasta pozornego do Rozwiązanie optymalne 0-1 KP z relaksacją:
pozornego koszt=0, ten komiwojażer pozostanie w bazie, F=[0].
0 d" x d" 1 - tzn, że można uciąć przedmiot
j
Tw2:
Dla każdej drogi l o skończonej długości zagadnienie 1 komiwojażera z n+
ma postać:
m* miastami (m* - ograniczone z góry) określonym przez powyższą
(będzie tylko jedna współrzędna różna od 0 lub 1)
 2.Poprawa górnego oszacowania (w każdym kroku będziemy poprawiać v( GKP )
ńł �ł
�ł łł�ł ńł �ł łł
b b
oszacowanie tj)Dla wykonaj:
j "T
D =
�ł0,1,...,�ł śłżł�...� �ł0,1,...,�ł śłżł
�ła1 �ł �łan �ł
ół �ł ół �ł
jeżeli to podstaw
sost + aost, j < t t := sost + aost. j
j j
X = {x " D : x d" b}
"a j j
poprzednik
( j) := ost
2. Nieliniowe zagadnienie załadunku
3.Powiększanie S funkcja celu:
n
j*:= arg min{t : j "T}, T := T -{ j*}, S := S *"{ j*}, s := t ,
j j* j* Q(x) = (x ) max
"g j j
j =1
ost := j *
ograniczenie: całkowite / ciągłe
4.Czy koniec?
n
Jeżeli to stop, optymalna długość drogi wynosi S ; inaczej idz
do 2.
k0
x d" b 0 d" x d" d x
j* = k0 "a j j j j j
j=1
Analiza złożoności obliczeniowej algorytmu:
ZAMIANA PROBLEMU DECYZYJNEGO (NIELINIOWEGO) NA WIELOETAPOWY:
f (n) = c1[(n -1) + (n - 2) + ... +1]+ c2[(n -1) + (n - 2) + ... +1]+
dj-maksymalna liczba elementów typu j
n
c2 (n -1) = (c1 + c2 ) (n -1) + c3 (n -1)
2
Algorytm (wyznaczający rozw. Dopuszczalne ) 9
wielomian 2-go stopnia SP" P
�!
1.podstaw j:=1,
Ą ( j) := 1, N := {2,3,..., n} - zbiór zadań C , C ,C O(n2 )
1 2 3- koszt wykonania odpowiednio punktów 2, 3, 4
jeszcze nie przydzielonych
y-ilość miejsca w plecaku
yn e" 0
2.Jeżeli wykonaj
N `" {"}
funkcja przejścia
y = y - a x j = 1,2,..., n
ALGORYTM FLOYD A  koszt połączenia pomiędzy dwoma węzłami O(n3) C
a)j=j+1, określ zbiór S (S  zbiór zadań swobodnych, których j j-1 j j
Połączenia mogą mieć wagi ujemne, ale suma wag w każdym konturze
poprzedniki zostały już przydzielone)
(wieloboku skierowanym) musi być dodatnia.
ńł łł�ł
/* �ł yn-1
S := {j " N : if (ij) " E,then : i " N}*/ " yn-1 �łd żł
"[0,b] f1(yn-1
) = max gn (xn )�! xn* = xn *(yn-1 n �ł śł
) �n = ,
k 0d"xn d"�n
an
ół �ł �ł�ł
(wybieramy za pomocą jakiejś reguły) dij - minimalna długość drogi pomiędzy wierzchołkami i, j, która
j* := wybór(S)
"yn-2"[0,b] f2(yn-2)=0d"max{gn-1(xn-1)+f1(yn-1)}=maxn-1(xn-1)+f1(yn-2-an-1xn-1)}
{g
d"�n-1
wykorzystuje jako wierzchołki pośrednie tylko wierzchołki xn-1
{1,2,..., k}
oraz ,
N := N -{j*} Ą ( j) := j*
0
algorytm rekurencyjny:
GAP (uogólnione zagadnienie przydziału)
"i dii := 0
aij i, j " E
ńł
j=1,2,...n i=1,2,...n
di0 =
j �ł
ół" i, j " E
- koszt realizacji zadania i przy pomocy zasobu j
[cij ]
1.
nxn k := 1
- ilość zasobu potrzebna do wykonania j-tego zadania za tablica pomocnicza, służy do znalezienia najkrótszej
[aij] "i, j rij := 0 �!
nxn
drogi (wyznacza przez jakie wierzchołki trzeba przechodzić szukając drogi
pomocą środka j
pomiędzy 2 zadanymi wierzchołkami)
- ilość zasobu jaki ma środek i
[bi ]
n 2.dla wykonaj
1 d" i, j d" n
Rozwiązanie jest dopuszczalne jeśli:
oceniamy -1 k k
k k
Wszystkie zadania są wykonane,
dij := min{dij , dik-1 + dkj-1}; modyfikujemy ri,j
Nie przekroczone są koszty zasobów jakie mamy do
dyspozycji
Zmienna decyzyjna:
1 if , j i
ńł
xij =
�ł0 WPP
jeżeli k=n to stop; inaczej k++ i przechodzimy do punktu 2.
ół
funkcja celu:
ALGORYTM CPM (critical path method)
n n
Procedura 1  numerowanie wierzchołków grafu tak, ażeby wierzchołek z
(jest to wyrażenie liniowe)
numerem większym nie poprzedzał wierzchołka z numerem mniejszym
�" xij min
""cij
1.przydziel wierzchołkowi swobodnemu (bez poprzedników) nr. i=1
i=1 j=1
2.usuwamy łuki łączące wierzchołki ponumerowane z nieponumerowanymi
Ograniczenia: 3.wierzchołkom swobodnym przydzielamy kolejne numery i+1,i+2...
Każde zadanie musi być wykonane 4.jeżeli nie ponumerowaliśmy wszystkich wierzchołków to idz do 2.
Złożoność algorytmu CPM
n
dla j=1,2,...n
Procedura 1: C1- numeracja jednego wierzchołka, C2- czas usunięcia łuku
= 1
"xij
f (n) = c1n + c2[(n -1) + (n - 2) + ... + 1] = c1n + c2 1 n(n -1) = O(n2 )
2
i=1
procedury 2, 3, 4  O(n2)
Ograniczenie na zasoby
n dla i=1,2,...n
ZA
OŻONOŚĆ OBLICZENIOWA  PODSUMOWANIE:
�" xij d" bi Teoria złożoności obliczeniowej zajmuje się analizą modeli procesów
"aij
obliczeniowych pod względem ich efektywności
j=1
1. złożoność obliczeniowa algorytmów
xij "{0,1}"i, j 2. ustalanie klas problemów
Jest to problem NP.-trudny (nie istnieje algorytm wielomianowy)
Tw: Problem P ma złożoność obliczeniową wielomianową
_________________________________________________________________
( jeżeli istnieje algorytm A taki, że , gdzie p(n)-
P " P ) t(A,n) < p(n)
Algorytm Dijkstry-Prim a: A
T  zbiór wierzchołków drzewa wielomian n,
, gdzie
t(A, n) = max{t(A, z, n) : z " P '" rozmiar(z) = n}
j : (ą , � )
j j
- czas rozwiązania zadania o rozmiarze n za pomocą algorytmu A.
, czyli najmniejsza odległość t(A, z, n)
� = min{aij : i "T}
j
_________________________________________________________________
od wierzchołka j do jakiegoś wierzchołka w drzewie T
- wierzchołki sąsiednie.
N = {i "V :{i, j}" E}
j
1.początek:
A := "
T := {s}- wybieramy dowolny wierzchołek,
2.początkowe cechowanie:
dla każdego ustal cechę
j `" s
(ą , � )
j j
jeżeli
j " Ns :ą := s � := asj
j j
j " Ns :ą := 0 � := "
n
j j
(ze wzorów Stirlinga)
2h e" n!
n
3.powiększanie rozwiązania
n!E" c�ł �ł
�ł �ł
e
szukamy �ł łł
j "T
min{� : j "T} (wybór gwarantuje brak cyklu) h e" log n!
j
k e" c[n log n -1.4n]�! h e" O(n log n)
dodajemy wierzchołek
j*:= arg min{� : j "T}
j
Tw: o minimalnej złożoności obliczeniowej algorytmu
Jeżeli rozwiązanie problemu zależy istotnie od n danych to jego złożoność
T := T *"{ j*} A := A *"{ą , j*}
j*
obliczeniowa jest co najmniej rzędu n.
ZAGADNIENIE ZAA
ADUNKU:
jeżeli to stop (T=V)
| T |= n(| A |= n -1)
1. Liniowe zagadnienie załadunku (zagadnienie plecakowe -KP)
a)binarne zagadnienie załadunkowe ( 0-1 KP )
Q(V , A) = Q(A) = b- udz
wig plecaka (lub objętość)
"aij
- przedmioty
{i, j}"A
j = 1,2,...,n
4.zmiana cechowania
aj- waga j-tego przedmiotu (lub objętość)
Dla wykonaj:
Cj- zysk z danego przedmiotu
( j "T ) '" ( j " N )
j*
zmienna decyzyjna
j do plecaka
jeżeli to
1
� > a ą := j*, � := a ńł
j jj* jj*
x = w przeciwnym przypadku
j �ł
ół0
Przejdz
do punktu 3. (n-1 iteracji)
ZA
OŻONOŚĆ OBLICZENIOWA ALGORYTMU Zysk: n
x max
"c j j
j=1
n
rozmiar problemu  parametr złożoności algorytmu ( w przypadku grafu  n) Ograniczenia:
" x "{0,1}
_________________________________________________________________ j j
x d" b
"a j j
j=1
B
X = {0,1}
j
Def: Funkcja jest rzędu [ ] jeżeli
f (n) "c>0
W (n) O(W (n))
________________________________________________________________
v( 0-1 KP )
E
takie, że dla zachodzi .
2
n > n = max{"c x : x " X}
f (n) d" cW(n)
j j
- wartość dopuszczalna
X = {x " D = {0,1}n : x d" b}
Do oceniania czasu obliczeń bierzemy najgorszy przypadek danych "a j j
f (n) =c1[(n-1)+(n-2)+...+1]+c2(n-1)+c3[(n-1)+(n-2)+...+1]=
b)uogólnione zagadnienie plecakowe ( GKP )
b  udz
wig plecaka
=(c1+c3)n(n-1)+c2(n-1)=ąn2+�n+c
2
- przedmioty
j = 1,2,..., n
złożoność stopnia wielomianowego
O(n2 )
aj- waga j-tego przedmiotu
C1-koszt wykonania porównania � podczas Cj- zysk z danego przedmiotu
min{� : j "T}
j Xj- liczba przedmiotów typu j do plecaka
Zysk: n
C
2-koszt operacji
x max
"c j j
| T |= n
T := T *"{ j*} A := A *"{ą , j*},
j*
j=1
Ograniczenia:
C3 - koszt
( j " N ) � j > a jj* , ą := j*, � := a
j*
jj* n
i całkowite
" x e" 0 �ł łł
Algorytm Dijkstry b
j j
x d" b
"a j j
x d"
�ł śł
1.Początek j
j=1
�ła j śł
dla �ł �ł
j "T
s := {p0}, s := 0, T := V -{p0}, t := "
p0 j
zmienna pomocnicza ostatni wierzchołek ost:=p0