sem pierwszego wierzchołka, znajdującego się po vi na najkrótszej drodze z vi do v1, która przechodzi przez wszystkie wierzchołki należące do A dokładnie raz...

Pokaż mi serce nie opętane zwodniczymi marzeniami, a pokażę ci człowieka szczęśliwego.

∅
⊆! !"#$ $% &
! ' ≠ !( (!) '
∈
! *+!!" ,(,,
≤≤
! *+!!" ,(,,
Zanim pokażemy, w jaki sposób można otrzymać optymalną trasę na podstawie
tablicy P, przeanalizujemy algorytm. Po pierwsze, potrzebne jest nam twierdzenie.
Twierdzenie 3.1
Dla każdego n ≥ 1
n
n
n 1
∑k
= n2 −
 
k 1
=
k 
Dowód. Jako ćwiczenie dla Czytelnika pozostawiono wykazanie, że:
n
n −1
k
=
  n

k 
k −1
Stąd:
n
n
n
n −1
∑k =
  ∑ 
n

k 1
=
k  k 1= k −1
n 1
− n −1
= n∑

k=0  k 
n 1
= n2 −
150
Podstawy algorytmów z przykładami w C++
Ostatnie równanie otrzymano dzięki wykorzystaniu wyniku z przykładu A.10
z dodatku A.
Poniżej przedstawiono analizę algorytmu 3.11.
Złożoność czasowa i przestrzenna w każdym przypadku
Analiza
algorytmu
(algorytm programowania dynamicznego dla problemu komiwojażera)
3.11.
Operacja podstawowa: czas wykonania pierwszej i ostatniej pętli można pominąć w porównaniu z czasem wykonania pętli środkowej, ponieważ zawiera ona różne poziomy zagnieżdżenia. Stąd jako operację podstawową będziemy traktować instrukcje wykonywane dla każdej wartości vj. Należy do nich instrukcja dodawania.
Rozmiar danych wejściowych: n, liczba wierzchołków w grafie.
Dla każdego zbioru A zawierającego k wierzchołków musimy rozpatrzyć n–1–k
wierzchołków, a dla każdego z tych wierzchołków operacja podstawowa jest wyko-
nywana k razy. Liczba podzbiorów A zbioru V–{v1}, zawierających k wierzchoł-
ków, wynosi (n 1− , więc całkowitą liczbę powtórzeń operacji podstawowej określa
k )
zależność:
n 2
n 1
T (n) = ∑−
 − 
(n −1− k)k

(3.8)
k =1
 k 
Nietrudno wykazać, że:
n − 
1
n − 2
(n −1− k)
= (n −


1 )

 k 
 k 
Podstawiając to równanie do równania 3.8 otrzymujemy:
n 2
n 2
T (n) = (n −1)∑−  − 
k

k =1
 k 
Ostatecznie, stosując twierdzenie 3.1, otrzymujemy:
n
T (n) = (n −1)(n − 2)2 −3 ∈ Θ( 2 n
n 2 )
Ze względu na fakt, że algorytm używa również dużej ilości pamięci, przeanalizu-
jemy także jego złożoność pamięciową, którą określimy symbolem M(n). Pamięć
użyta do przechowania tablic D[vi][A] oraz P[vi][A] stanowi oczywiście główny
składnik poziomu zajętości pamięci. Określimy więc rozmiar tych tablic. Ze względu
na fakt, że zbiór V–{v1} zawiera n–1 wierzchołków, możemy zastosować wyniki
otrzymane w przykładzie A.10 w dodatku A, stwierdzając, że posiada on 2n–1
podzbiorów A. Pierwszy indeks tablic D i P należy do zakresu od 1 do n. Stąd:
n 1
−
n
M (n) = 2 × n2 = n2 ∈ Θ( n
n2 )
Rozdział 3. Programowanie dynamiczne
151
W tym momencie Czytelnik może się zastanawiać, co osiągnęliśmy, skoro nasz
algorytm jest rzędu Θ(n22n). Poniższy przykład pokazuje jednak, że nawet algorytm
o złożoności na takim poziomie może być niekiedy przydatny.
Przykład 3.12.
Rudolf i Natalia współzawodniczą o tę samą posadę sprzedawcy. Szef powiedział im
w piątek, że ta osoba, która od poniedziałku szybciej odbędzie podróż po całym
rewirze, na którego obszarze leży 20 miast, zdobędzie posadę. Na obszarze rewi-
ru znajduje się biuro główne, do którego należy powrócić po odwiedzeniu innych
miejscowości. Z każdego miasta istnieje droga do każdego innego miasta. Rudolf
stwierdził, że ma cały weekend na opracowanie trasy, więc postanowił po prostu
uruchomić na swoim komputerze algorytm siłowy, który rozpatrzyłby wszystkie
(20–1)! tras. Natalia przypomniała sobie algorytm programowania dynamiczne-
go, który poznała na zajęciach z algorytmiki. Stwierdzając, że musi wykorzystać
każdą nadarzającą się okazję, uruchomiła ten algorytm na swoim komputerze.