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
:
Algorytm (
wyznaczający rozw. Dopuszczalne )
9
1.podstaw j:=1,
1
:
)
(
=
j
π
,
{
}
n
N
,...,
3
,
2
:
=
- zbiór zadań
jeszcze nie przydzielonych
2.Jeżeli
{ }
∅
≠
N
wykonaj
a)j=j+1, określ zbiór S (S –
zbiór zadań swobodnych, których
poprzedniki zostały już przydzielone)
/*
{
}
N
i
then
E
ij
if
N
j
S
∉
∈
∈
=
:
,
)
(
:
:
*/
)
(
:
*
S
wybór
j
=
(wybieramy za pomocą jakiejś reguły)
oraz
{ }
*
:
j
N
N
−
=
,
*
:
)
(
j
j
=
π
GAP (
uogólnione zagadnienie przydziału
)
j=1,2,...n i=1,2,...n
[ ]
nxn
ij
c
- koszt realizacji zadania i przy pomocy zasobu j
[ ]
nxn
ij
a
- ilość zasobu potrzebna do wykonania j-tego zadania za
pomocą środka j
[ ]
n
i
b
- ilość zasobu jaki ma środek i
Rozwiązanie jest dopuszczalne jeśli:
Wszystkie zadania są wykonane,
Nie przekroczone są koszty zasobów jakie mamy do
dyspozycji
Zmienna decyzyjna:
→
=
WPP
i
j
if
x
ij
0
,
1
funkcja celu:
∑∑
=
=
→
⋅
n
i
n
j
ij
ij
x
c
1
1
min
(jest to wyrażenie liniowe)
Ograniczenia:
Każde zadanie musi być wykonane
∑
=
=
n
i
ij
x
1
1
dla j=1,2,...n
Ograniczenie na zasoby
∑
=
≤
⋅
n
j
i
ij
ij
b
x
a
1
dla i=1,2,...n
{ }
j
i
x
ij
,
1
,
0
∀
∈
Jest to problem NP.-trudny (nie istnieje algorytm wielomianowy)
_________________________________________________________________
Algorytm Dijkstry-Prim’a:
A
T – zbiór wierzchołków drzewa
)
,
(
:
j
j
j
β
α
, gdzie
}
:
min{
T
i
a
ij
j
∈
=
β
, czyli najmniejsza odległość
od wierzchołka j do jakiegoś wierzchołka w drzewie T
}
}
,
{
:
{
E
j
i
V
i
N
j
∈
∈
=
- wierzchołki sąsiednie.
1.początek:
}
{
:
s
T
=
- wybieramy dowolny wierzchołek,
∅
=
:
A
2.początkowe cechowanie:
dla każdego
s
j
≠
ustal cechę
)
,
(
j
j
β
α
jeżeli
∞
=
=
∉
=
=
∈
:
0
:
:
:
:
:
j
j
s
sj
j
j
s
N
j
a
s
N
j
β
α
β
α
3.powiększanie rozwiązania
szukamy
}
:
min{
T
j
j
∉
β
(wybór
T
j
∉
gwarantuje brak cyklu)
dodajemy wierzchołek
}
:
min{
arg
:
*
T
j
j
j
∉
=
β
*}
,
{
:
*}
{
:
*
j
A
A
j
T
T
j
α
∪
=
∪
=
jeżeli
)
1
|
(|
|
|
−
=
=
n
A
n
T
to stop (T=V)
∑
∈
=
=
A
j
i
ij
a
A
Q
A
V
Q
}
,
{
)
(
)
,
(
4.zmiana cechowania
Dla
)
(
)
(
*
j
N
j
T
j
∈
∧
∉
wykonaj:
jeżeli
*
jj
j
a
>
β
to
*
:
*,
:
jj
a
j
=
=
β
α
Przejdź do punktu 3. (n-1 iteracji
)
Z
ŁOŻONOŚĆ OBLICZENIOWA ALGORYTMU
rozmiar problemu – parametr złożoności algorytmu ( w przypadku grafu – n)
_________________________________________________________________
B
Def: Funkcja
)
(n
f
jest rzędu
)
(n
W
[
(
)
)
(n
W
O
] jeżeli
0
>
∃
c
takie, że dla
n
n
′
>
zachodzi
)
(
)
(
n
cW
n
f
≤
.
Do oceniania czasu obliczeń bierzemy najgorszy przypadek danych
[
]
[
]
=
+
+
−
+
−
+
−
+
+
+
−
+
−
=
1
...
)
2
(
)
1
(
)
1
(
1
...
)
2
(
)
1
(
)
(
3
2
1
n
n
c
n
c
n
n
c
n
f
c
n
n
n
c
n
c
c
n
+
+
=
−
+
−
+
=
β
α
2
2
2
3
1
)
1
(
)
1
(
)
(
złożoność stopnia wielomianowego
)
(
2
n
O
C
1
-koszt wykonania porównania
β
podczas
}
:
min{
T
j
j
∉
β
C
2
-koszt operacji
*}
,
{
:
*}
{
:
*
j
A
A
j
T
T
j
α
∪
=
∪
=
,
n
T
=
|
|
C
3
- koszt
)
(
*
j
N
j
∈
*
jj
j
a
>
β
,
*
:
*,
:
jj
a
j
=
=
β
α
Algorytm Dijkstry
1.Początek
∞
=
−
=
=
=
:
},
{
:
,
0
:
},
{
:
0
0
0
j
p
t
p
V
T
s
p
s
dla
T
j
∈
zmienna pomocnicza ostatni wierzchołek ost:=p
0
2.Poprawa górnego oszacowania (w każdym kroku będziemy poprawiać
oszacowanie t
j
)Dla
T
j
∈
wykonaj:
jeżeli
j
j
ost
ost
t
a
s
<
+
,
to podstaw
j
ost
ost
j
a
s
t
.
:
+
=
poprzednik
ost
j
=
:
)
(
3.Powiększanie S
*
:
,
:
*},
{
:
*},
{
:
},
:
min{
arg
:
*
*
*
j
ost
t
s
j
S
S
j
T
T
T
j
t
j
j
j
j
=
=
∪
=
−
=
∈
=
4.Czy koniec?
Jeżeli
0
*
k
j
=
to stop, optymalna długość drogi wynosi S
k0
; inaczej idź do 2.
Analiza złożoności obliczeniowej algorytmu:
[
] [
]
)
1
(
)
1
(
)
(
)
1
(
1
...
)
2
(
)
1
(
1
...
)
2
(
)
1
(
)
(
3
2
2
1
2
2
1
−
+
−
+
=
−
+
+
+
−
+
−
+
+
+
−
+
−
=
n
c
n
c
c
n
c
n
n
c
n
n
c
n
f
n
wielomian 2-go stopnia
)
(
2
n
O
⇒
SP
∈
P
C
1
, C
2
,C
3
- koszt wykonania odpowiednio punktów 2, 3, 4
A
LGORYTM
F
LOYD
’
A
– koszt połączenia pomiędzy dwoma węzłami O(n
3
)
C
Połączenia mogą mieć wagi ujemne, ale suma wag w każdym konturze
(wieloboku skierowanym) musi być dodatnia.
k
ij
d
- minimalna długość drogi pomiędzy wierzchołkami i, j, która
wykorzystuje jako wierzchołki pośrednie tylko wierzchołki
}
,...,
2
,
1
{
k
algorytm rekurencyjny:
∉
∞
∈
=
E
j
i
E
j
i
a
d
ij
ij
,
,
0
0
:
0
=
∀
ii
i
d
1.
1
:
=
k
←
=
∀
0
:
,
ij
j
i
r
tablica pomocnicza, służy do znalezienia najkrótszej
drogi (wyznacza przez jakie wierzchołki trzeba przechodzić szukając drogi
pomiędzy 2 zadanymi wierzchołkami)
2.dla
n
j
i
≤
≤
,
1
wykonaj
oceniamy
}
,
min{
:
1
1
1
−
−
−
+
=
k
kj
k
ik
k
ij
k
ij
d
d
d
d
; modyfikujemy r
i,j
jeżeli k=n to stop; inaczej k++ i przechodzimy do punktu 2.
A
LGORYTM
CPM (critical path method)
Procedura 1 – numerowanie wierzchołków grafu tak, ażeby wierzchołek z
numerem większym nie poprzedzał wierzchołka z numerem mniejszym
1.przydziel wierzchołkowi swobodnemu (bez poprzedników) nr. i=1
2.usuwamy łuki łączące wierzchołki ponumerowane z nieponumerowanymi
3.wierzchołkom swobodnym przydzielamy kolejne numery i+1,i+2...
4.jeżeli nie ponumerowaliśmy wszystkich wierzchołków to idz do 2.
Złożoność algorytmu CPM
Procedura 1: C
1
- numeracja jednego wierzchołka, C
2
- czas usunięcia łuku
)
(
)
1
(
]
1
...
)
2
(
)
1
[(
)
(
2
2
1
2
1
2
1
n
O
n
n
c
n
c
n
n
c
n
c
n
f
=
−
+
=
+
+
−
+
−
+
=
procedury 2, 3, 4 – O(n
2
)
Z
ŁOŻONOŚĆ OBLICZENIOWA
–
PODSUMOWANIE
:
Teoria złożoności obliczeniowej zajmuje się analizą modeli procesów
obliczeniowych pod względem ich efektywności
1.
złożoność obliczeniowa algorytmów
2.
ustalanie klas problemów
Tw:
Problem P ma złożoność obliczeniową wielomianową
(
)
P
∈
P
jeżeli istnieje algorytm A taki, że
)
(
)
,
(
n
p
n
A
t
<
, gdzie p(n)-
wielomian n,
{
}
n
z
P
z
n
z
A
t
n
A
t
=
∧
∈
=
)
(
rozmiar
:
)
,
,
(
max
)
,
(
)
,
,
(
n
z
A
t
- czas rozwiązania zadania o rozmiarze n za pomocą algorytmu A.
_________________________________________________________________
!
log
!
2
n
h
n
h
≥
≥
n
e
n
c
n
≅
!
(ze wzorów Stirlinga)
[
]
)
log
(
4
.
1
log
n
n
O
h
n
n
n
c
k
≥
⇒
−
≥
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ść
obliczeniowa jest co najmniej rzędu n.
Z
AGADNIENIE ZAŁADUNKU
:
1. Liniowe zagadnienie załadunku (zagadnienie plecakowe -KP)
a)binarne zagadnienie załadunkowe (
0-1 KP )
b- udźwig plecaka (lub objętość)
n
j
,...,
2
,
1
=
- przedmioty
a
j
- waga j-tego przedmiotu (lub objętość)
C
j
- zysk z danego przedmiotu
zmienna decyzyjna
=
0
1
j
x
→
j
do plecaka
w przeciwnym przypadku
Zysk:
∑
=
→
n
j
j
j
x
c
1
max
Ograniczenia:
∑
=
≤
n
j
j
j
b
x
a
1
}
1
,
0
{
∈
∀
j
j
x
}
1
,
0
{
=
j
X
________________________________________________________________
v( 0-1 KP )
{
}
∑
∈
=
X
x
x
c
j
j
:
max
E
{
}
∑
≤
=
∈
=
b
x
a
D
x
X
j
j
n
:
}
1
,
0
{
- wartość dopuszczalna
b)uogólnione zagadnienie plecakowe (
GKP )
b – udźwig plecaka
n
j
,...,
2
,
1
=
- przedmioty
a
j
- waga j-tego przedmiotu
C
j
- zysk z danego przedmiotu
X
j
- liczba przedmiotów typu j do plecaka
Zysk:
∑
=
→
n
j
j
j
x
c
1
max
Ograniczenia:
∑
=
≤
n
j
j
j
b
x
a
1
0
≥
∀
j
j
x
i całkowite
≤
j
j
a
b
x
v( GKP )
×
×
=
n
a
b
a
b
D
,...,
1
,
0
...
,...,
1
,
0
1
{
}
∑
≤
∈
=
b
x
a
D
x
X
j
j
:
2. Nieliniowe zagadnienie załadunku
funkcja celu:
max
)
(
)
(
1
→
=
∑
=
n
j
j
j
x
g
x
Q
ograniczenie:
∑
=
≤
≤
≤
n
j
j
j
j
j
j
x
d
x
b
x
a
1
0
całkowite / ciągłe
Z
AMIANA PROBLEMU DECYZYJNEGO
(
NIELINIOWEGO
)
NA WIELOETAPOWY
:
dj-maksymalna liczba elementów typu j
y-ilość miejsca w plecaku
0
≥
n
y
funkcja przejścia
n
j
x
a
y
y
j
j
j
j
,...,
2
,
1
1
=
−
=
−
=
=
⇒
=
∈
∀
−
−
≤
≤
−
−
n
n
n
n
n
n
n
n
n
x
n
n
a
y
d
y
x
x
x
g
y
f
b
y
n
n
1
1
0
1
1
1
,
)
(
*
*
)
(
max
)
(
]
,
0
[
ξ
ξ
{
} {
}
)
(
)
(
max
)
(
)
(
max
)
(
]
,
0
[
1
1
2
1
1
1
1
1
1
1
0
2
2
2
1
1
−
−
−
−
−
−
−
−
≤
≤
−
−
−
+
=
+
=
∈
∀
−
−
n
n
n
n
n
n
n
n
x
n
n
x
a
y
f
x
g
y
f
x
g
y
f
b
y
n
n
ξ
Wyszukiwarka
Podobne podstrony:
Ścieki ściąga(egzamin), Studia, 1-stopień, inżynierka, Ochrona Środowiska, Technologie stosowane w o
Ściąga egzamin trzoda chlewna
sciaga egzamin 14
ściąga egzamin
sciąga egzamin
Ściaga sortowania, algorytmy i struktury danych
Teoria sprotu - ściąga egzamin, AWF Biała Podlaska (SPORT), 2 ROK, Teoria sportu
ściąga egzamin prof Karpuś analiza finansowa
ściąga egzamin z mechaniki
ściąga egzamin wytrzymałość folia
sciaga egzamin
Biologia ściaga egzamin
Ściąga egzamin Manikowski, lamerska stylistyka
sciaga egzamin społeczna, studia, ściągi
ściąga egzamin B.K, Budownictwo PCz, Technologia betonów i zapraw, Ściągi
Ściąga-egzamin planowanie, 1
ściąga 2 egzamin
ściąga egzamin
więcej podobnych podstron