Untitled
unknown
plain_text
2 years ago
35 kB
11
Indexable
\documentclass[polish,10pt]{beamer}
\usepackage[T1]{fontenc}
\usepackage{polski}
\usepackage{babel}
\usepackage{tikz}
\usepackage{graphicx}
\usetheme{Madrid}
\title{Problem komiwojażera}
\author{Aleksander Błaszkiewicz}
\date{2022}
\begin{document}
\frame{\titlepage}
\begin{frame}{Definicja}
\begin{center}
\includegraphics[scale=0.15]{tsp.png}
\end{center}
\begin{block}{Problem komiwojażera}
(ang. travelling salesman problem, TSP) – zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.
\end{block}
\end{frame}
\begin{frame}{Definicja}
Najpierw podzielmy sobie grafy na:
\begin{itemize}
\item Bez wag / z wagami
\item pełne / niepełne
\end{itemize}
\end{frame}
\begin{frame}[fragile]{Graf bez wag}
\begin{center}
\begin{tikzpicture}
\node[shape=circle,draw=black] (A) at (0,0) {A};
\node[shape=circle,draw=black] (B) at (0,2) {B};
\node[shape=circle,draw=black] (C) at (2,2) {C};
\node[shape=circle,draw=black] (D) at (2,0) {D};
\path[-]
(A) edge node {} (B)
(B) edge node {} (C)
(C) edge node {} (D)
(D) edge node {} (A)
(A) edge node {} (C)
(B) edge node {} (D)
;
\end{tikzpicture}
\end{center}
\end{frame}
\begin{frame}{Graf z wagami}
\begin{center}
\begin{tikzpicture}
\node[shape=circle,draw=black] (A) at (0,0) {A};
\node[shape=circle,draw=black] (B) at (0,2) {B};
\node[shape=circle,draw=black] (C) at (2,2) {C};
\node[shape=circle,draw=black] (D) at (2,0) {D};
\path[-]
(A) edge node[left] {$5$} (B)
(B) edge node[above] {$5$} (C)
(C) edge node[right] {$5$} (D)
(D) edge node[below] {$5$} (A)
(A) edge node[left] {$1$} (C)
(B) edge node[right] {$1$} (D)
;
\end{tikzpicture}
\end{center}
\begin{block}{Graf z wagami}
Graf, który krawędziom przypisuje etykiety liczbowe zwane wagami
\end{block}
\end{frame}
\begin{frame}[fragile]{Graf pełny}
\begin{center}
\begin{tikzpicture}
\node[shape=circle,draw=black] (A) at (0,0) {A};
\node[shape=circle,draw=black] (B) at (0,2) {B};
\node[shape=circle,draw=black] (C) at (2,2) {C};
\node[shape=circle,draw=black] (D) at (2,0) {D};
\path[-]
(A) edge node {} (B)
(B) edge node {} (C)
(C) edge node {} (D)
(D) edge node {} (A)
(A) edge node {} (C)
(B) edge node {} (D)
;
\end{tikzpicture}
\end{center}
\begin{block}{Graf pełny}
Graf prosty, nieskierowany, w którym dla każdej pary węzłów istnieje krawędź je łącząca
\end{block}
\end{frame}
\begin{frame}[fragile]{Graf, który nie jest pełny}
\begin{center}
\begin{tikzpicture}
\node[shape=circle,draw=black] (A) at (0,0) {A};
\node[shape=circle,draw=black] (B) at (0,2) {B};
\node[shape=circle,draw=black] (C) at (2,2) {C};
\node[shape=circle,draw=black] (D) at (2,0) {D};
\path[-]
(A) edge node {} (B)
(B) edge node {} (C)
(C) edge node {} (D)
(D) edge node {} (A)
;
\end{tikzpicture}
\end{center}
\end{frame}
\begin{frame}{Definicja}
Musimy omówić następujące definicje
\begin{itemize}
\item cykl Hamiltona
\item minimalny cykl Hamiltona
\end{itemize}
\end{frame}
\begin{frame}{Cykl hamiltona w grafie bez wag}
\begin{center}
\begin{tikzpicture}
\node[shape=circle,draw=black] (A) at (0,0) {A};
\node[shape=circle,draw=black] (B) at (0,2) {B};
\node[shape=circle,draw=black] (C) at (2,2) {C};
\node[shape=circle,draw=black] (D) at (2,0) {D};
\path[-]
(A) edge[draw=red] node {} (B)
(B) edge[draw=red] node {} (C)
(C) edge[draw=red] node {} (D)
(D) edge[draw=red] node {} (A)
(A) edge node {} (C)
(B) edge node {} (D)
;
\end{tikzpicture}
\end{center}
\begin{block}{Cykl hamiltona}
Taki cykl w grafie, w którym każdy wierzchołek grafu odwiedzany jest dokładnie raz (oprócz pierwszego wierzchołka)
\end{block}
\end{frame}
\begin{frame}{Ścieżka Hamiltona}
\begin{center}
\begin{tikzpicture}
\node[shape=circle,draw=black] (A) at (0,0) {A};
\node[shape=circle,draw=black] (B) at (0,2) {B};
\node[shape=circle,draw=black] (C) at (2,2) {C};
\node[shape=circle,draw=black] (D) at (2,0) {D};
\path[-]
(A) edge[draw=red] node {} (B)
(B) edge[draw=red] node {} (D)
(D) edge[draw=red] node {} (C)
(D) edge node {} (A)
(A) edge node {} (C)
(B) edge node {} (C)
;
\end{tikzpicture}
\end{center}
\begin{block}{Ścieżka Hamiltona}
Ścieżka w grafie przechodząca przez wszystkie wierzchołki
\end{block}
\end{frame}
\begin{frame}{Minimalny cykl hamiltona}
\begin{center}
\begin{tikzpicture}
\node[shape=circle,draw=black] (A) at (0,0) {A};
\node[shape=circle,draw=black] (B) at (0,2) {B};
\node[shape=circle,draw=black] (C) at (2,2) {C};
\node[shape=circle,draw=black] (D) at (2,0) {D};
\path[-]
(A) edge[draw=red] node[left] {$5$} (B)
(B) edge node[above] {$5$} (C)
(C) edge[draw=red] node[right] {$5$} (D)
(D) edge node[below] {$5$} (A)
(A) edge[draw=red] node[left] {$1$} (C)
(B) edge[draw=red] node[right] {$1$} (D)
;
\end{tikzpicture}
\end{center}
\begin{block}{Minimalny cykl hamiltona}
Taki cykl hamiltona, którego suma wag jest najniższa
\end{block}
\begin{alertblock}{Ważne}
Minimalny cykl hamiltona występuje tylko w grafach ważonych
\end{alertblock}
\end{frame}
\begin{frame}{Grafy hamiltonowskie i półhamiltonowskie}
\begin{block}{Graf hamiltonowski}
Graf, który posiada ścieżkę hamiltona
\end{block}
\begin{block}{Graf półhamiltonowski}
Graf, który posiada tylko jedną ścieżkę hamiltona
\end{block}
\end{frame}
\begin{frame}{Historia}
Historia problemu komiwojażera sięga roku 1832, kiedy to niemiecki komiwojażer opublikował tekst opisujący jego profesję.
W tekście podkreślił, że bardzo ważne jest wcześniejsze zaplanowanie trasy, ponieważ taki zabieg oszczędza mu bardzo dużo czasu.
\end{frame}
\begin{frame}{Dygresja}
Kiedyś byłem kurierem
\end{frame}
\begin{frame}{Zastosowania}
\begin{center}
Logistyka
\end{center}{}
\begin{center}
\includegraphics[scale=0.5]{magazyn.png}
\end{center}{}
\end{frame}
\begin{frame}{Zastosowania}
\begin{center}
Elektronika
\end{center}{}
\begin{center}
\includegraphics[scale=0.5]{robot.png}
\end{center}{}
\end{frame}
\begin{frame}{Zastosowania}
Bioinformatyka
\\~\\
Odwzorowywanie drzew ewolucyjnych
\\~\\
Analizowanie interakcji białek
\end{frame}
\begin{frame}{Możliwe rozwiązania}
Rozwiązania problemu można podzielić na grupy:
\begin{itemize}
\item dokładne
\item heurystyki
\end{itemize}
\end{frame}
\begin{frame}{Rozwiązania dokładne}
\begin{itemize}
\item sprawdzenie wszystkich wariantów
\item algorytm Helda-Karpa
\end{itemize}
\end{frame}
\begin{frame}{Sprawdzenie wszystkich wariantów}
\begin{center}
\includegraphics[scale=0.07]{graph-10-nodes.png}
\end{center}
\pause
Liczba cykli hamiltona:
$$L_h=10*9*8*7*6*5*4*3*2*1=362880$$
\pause
Dla $n$ wierzchołków:
$$L_h=(n-1)!$$
\pause
Przy czym dla symetrycznej odmiany problemu:
$$L_h=\frac{(n-1)!}{2}$$
\end{frame}
\begin{frame}{Algorytm Helda-Karpa}
Załóżmy, że mamy graf liczący $n$ wierzchołków ponumerowanych $1,2,\ldots, n$.
Niech początkowym wierzchołkiem będzie wierzchołek $1$.
Jako $d_{i,j}$ oznaczmy odległość między wierzchołkami $i$ oraz $j$.
\\~\\
Oznaczmy jako $D(S,p)$ optymalną długość ścieżki wychodzącej z punktu 1 i przechodzącej przez wszystkie punkty zbioru $S$, tak aby zakończyć się w punkcie $p$, $p\in S$.
\\~\\
Przykładowo, zapis $D(\{2,5,6\},5)$ to optymalna długość ścieżki wychodzącej z punktu 1, przechodzącej przez punkty 2 i 6 oraz kończącej się w punkcie 5. Liczbę punktów w zbiorze $S$ oznaczmy jako $s$.
\end{frame}
\begin{frame}{Algorytm Helda-Karpa}
$$
D(S,p)=\begin{cases}
d_{1,p},&\text{gdy }s=1\\
min_{x\in(S-\{p\})}(D(S-\{p\},x)+d_{x,p}),&\text{gdy }s>1\\
\end{cases}
$$
\end{frame}
\begin{frame}{Algorytm Helda-Karpa}
\begin{center}
\begin{tikzpicture}
\node[shape=circle,draw=black] (4) at (0,0) {4};
\node[shape=circle,draw=black] (2) at (3,2) {2};
\node[shape=circle,draw=black] (1) at (3,0) {1};
\node[shape=circle,draw=black] (3) at (5,2) {3};
\path[-]
(4) edge node[above] {$50$} (2)
(4) edge node[below] {$40$} (1)
(4) edge node[below] {$67$} (3)
(1) edge node[right] {$30$} (2)
(1) edge node[right] {$36$} (3)
(3) edge node[above] {$20$} (2)
;
\end{tikzpicture}
\end{center}
$$d_{1,2}=d_{2,1}=30$$
$$d_{1,3}=d_{3,1}=36$$
$$d_{1,4}=d_{4,1}=40$$
$$d_{2,3}=d_{3,2}=20$$
$$d_{2,4}=d_{4,2}=50$$
$$d_{3,4}=d_{4,3}=67$$
\end{frame}
\begin{frame}{Algorytm Helda-Karpa}
\begin{center}
\begin{tikzpicture}
\node[shape=circle,draw=black] (4) at (0,0) {4};
\node[shape=circle,draw=black] (2) at (3,2) {2};
\node[shape=circle,draw=black] (1) at (3,0) {1};
\node[shape=circle,draw=black] (3) at (5,2) {3};
\path[-]
(4) edge node[above] {$50$} (2)
(4) edge[draw=blue] node[below] {$40$} (1)
(4) edge node[below] {$67$} (3)
(1) edge[draw=red] node[right] {$30$} (2)
(1) edge[draw=green] node[right] {$36$} (3)
(3) edge node[above] {$20$} (2)
;
\end{tikzpicture}
\end{center}
Na początku wyznaczmy wartości $D(S,p)$ dla jednoelementowych zbiorów $S (s=1)$
$$\color{red}D(\{2\},2)=d_{1,2}=30$$
$$\color{green}D(\{3\},3)=d_{1,3}=36$$
$$\color{blue}D(\{4\},4)=d_{1,4}=40$$
\end{frame}
\begin{frame}{Algorytm Helda-Karpa}
Następny krok to wyznaczenie wartości dla zbiorów dwuelementowych
$$D(\{2, 3\}, 2) = min( D(\{3\}, 3) + d_{3,2} ) = min(36 + 20) = min(56) = 56 [3]$$
$$D(\{2, 3\}, 3) = min( D(\{2\}, 2) + d_{2,3} ) = min(30 + 20) = min(50) = 50 [2]$$
$$D(\{2, 4\}, 2) = min( D(\{4\}, 4) + d_{4,2} ) = min(40 + 50) = min(90) = 90 [4]$$
$$D(\{2, 4\}, 4) = min( D(\{2\}, 2) + d_{2,4} ) = min(30 + 50) = min(80) = 80 [2]$$
$$D(\{3, 3\}, 3) = min( D(\{4\}, 4) + d_{4,3} ) = min(40 + 67) = min(107) = 107 [4]$$
$$D(\{3, 4\}, 4) = min( D(\{3\}, 3) + d_{3,4} ) = min(36 + 67) = min(103) = 103 [3]$$
\end{frame}
\begin{frame}{Algorytm Helda-Karpa}
Kolejny krok to wyznaczenie wartości dla zbiorów trójelementowych
$$D(\{2, 3, 4\}, 2) = min( D(\{3, 4\}, 3) + d_{3,2}, D(\{3, 4\}, 4) + d_{4,2} ) =$$
$$=min(107 + 20,103 + 50) = min(127, 153) = 127 [3]$$
\\~\\
$$D(\{2, 3, 4\}, 3) = min( D(\{2, 4\}, 2) + d_{2,3}, D(\{2, 4\}, 4) + d_{4,3} ) =$$
$$min(90 + 20, 80 + 67) = min(110, 147) = 110 [2]$$
\\~\\
$$D(\{2, 3, 4\}, 4) = min( D(\{2, 3\}, 2) + d_{2,4}, D(\{2, 3\}, 3) + d_{3,4} ) =$$
$$min(56 + 50, 50 + 67) = min(106, 117) = 106 [4]$$
\end{frame}
\begin{frame}{Algorytm Helda-Karpa}
Ostatni krok. Rozwiązanie równania.
$$min( D(\{2, 3, 4\}, 2) + d_{2,1}, D(\{2, 3, 4\}, 3) + d_{3,1}, D(\{2, 3, 4\}, 4) + d_{4,1},) =$$
$$= min(127 + 30, 110 + 36, 106 + 40) =$$
$$= min(157, 146, 146) = 146 [3]$$
Długość optymalnej trasy to 146. Dodatkowo optymalną trasę możemy odtworzyć, wybierając po kolei liczby z indeksów:
$$1-3-2-4-1$$
\pause
Czy wynika z tego coś jeszcze?
\end{frame}
\begin{frame}{Algorytm Helda-Karpa}
Algorytm ma złożoność czasową $O(n^22^n)$, co jest o wiele szybsze niż algorytm ze wszystkimi wariantami - $O(n!)$
\\~\\
Należy jednak pamiętać, że najprostszy algorytm zapewnia stałą złożoność pamięciową, a w przypadku tego algorytmu to $O(n2^n)$
\end{frame}
\begin{frame}{Algorytm Helda-Karpa}
Dlaczego algorytm działa szybko i skąd taka złożoność pamięciowa?
\\~\\
\pause
Programowanie dynamiczne
\end{frame}
\begin{frame}{Programowanie dynamiczne}
technika projektowania algorytmów polegająca na rozwiązywaniu podproblemów i zapamiętywania ich wyników.
\\~\\
W przypadku natrafienia na ten sam podproblem nie trzeba go ponownie rozwiązywać, a można go wczytać z tabeli, do której dostęp zwykle jest stały.
\end{frame}
\begin{frame}{Rozwiązania przybliżone}
\begin{itemize}
\item algorytm najbliższego sąsiada\
\item algorytm RNN
\item algorytm najmniejszej krawędzi
\item algorytm Christofidesa
\end{itemize}
\end{frame}
\begin{frame}{Algorytm najbliższego sąsiada}
Algorytm rozpoczyna działanie od wybranego wierzchołka (nazwijmy go wierzchołkiem początkowym) i polega na kolejnym przechodzeniu do najbliższego nieodwiedzonego sąsiada ostatnio dodanego wierzchołka
\end{frame}
\begin{frame}{Algorytm najbliższego sąsiada}
Formalnie:
\begin{itemize}
\item Wierzchołek początkowy oznaczamy jako odwiedzony i ustawiamy jako aktualny
\item Znajdujemy najkrótszą spośród krawędzi łączących aktualny wierzchołek z jeszcze nieodwiedzonymi wierzchołkami
\item Dołączamy do rozwiązania krawędź znalezioną w punkcie 2
\item Wierzchołek będący drugim końcem krawędzi znalezionej w punkcie 2 oznaczamy jako odwiedzony i ustawiamy jako aktualny
\item Jeśli są jeszcze nieodwiedzone wierzchołki, przechodzimy do punktu 2
\item Dołączamy krawędź łączącą ostatnio dodany wierzchołek z wierzchołkiem początkowym. Zamykamy w ten sposób cykl
\end{itemize}
\end{frame}
\begin{frame}{Algorytm najbliższego sąsiada}
\begin{center}
\begin{tikzpicture}
\node[shape=circle,draw=black] (1) at (2,2) {1};
\node[shape=circle,draw=black] (2) at (0.5,2) {2};
\node[shape=circle,draw=black] (3) at (0,0) {3};
\node[shape=circle,draw=black] (4) at (2,4) {4};
\node[shape=circle,draw=black] (5) at (6,1) {5};
\onslide<2->\path[-] (1) edge node {} (2);
\onslide<3->\path[-] (2) edge node {} (3);
\onslide<4->\path[-] (3) edge node {} (4);
\onslide<5->\path[-] (4) edge node {} (5);
\onslide<6->\path[-] (5) edge node {} (1);
\end{tikzpicture}
\end{center}
\end{frame}
\begin{frame}{Algorytm najbliższego sąsiada}
Złożoność czasowa takiego algorytmu to $O(n^2)$
\\~\\
Złożoność pamięciowa jest bardzo niewielka, ponieważ algorytm musi przechowywać tylko listę odwiedzonych wierzchołków oraz listę krawędzi budujących rozwiązanie
\\~\\
Trzeba pamiętać o tym, że nie jest to algorytm dokładny. Przyjmuje się, że znalezione rozwiązania są średnio 25\% gorsze od optymalnych. Istnieją jednak przypadki, w których algorytm daje najgorsze możliwe rozwiązanie.
\end{frame}
\begin{frame}{Algorytm najbliższego sąsiada}
\begin{center}
\begin{tikzpicture}
\node[shape=circle,draw=black] (A) at (0,0) {A};
\node[shape=circle,draw=black] (B) at (2,0) {B};
\node[shape=circle,draw=black] (C) at (3,0) {C};
\node[shape=circle,draw=black] (D) at (7,0) {D};
\path[-]
(B) edge[below] node {$1$} (C)
(A) edge[below] node {$2$} (B)
(C) edge[below] node {$4$} (D)
;
\onslide<2->\path[->] (B) edge[bend left] node {} (C);
\onslide<3->\path[->] (C) edge[bend right] node {} (A);
\onslide<4->\path[->] (A) edge[bend left] node {} (D);
\onslide<5->\path[->] (D) edge[bend left] node {} (B);
\end{tikzpicture}
\end{center}
Dla przykładu jak na rysunku przy założeniu punktu początkowego B, algorytm zwróci cykl o długości 16:
$$B-C-A-D-B$$
Tymczasem pozostałe rozwiązania mają długość 12:
$$B-A-C-D-B$$
$$B-C-D-A-B$$
\end{frame}{}
\begin{frame}{Algorytm najbliższego sąsiada}
Załóżmy, że graf ma $n$ wierzchołków.
Zatem dla każdego z wierzchołków trzeba wyznaczyć optymalny wierzchołek:
$$\sum_{i=0}^n$$
Wyznaczanie optymalnego wierzchołka to przeiterowanie po pozostałych wierzchołkach (których z każdym następnym krokiem jest o jeden mniej):
$$\sum_{j=i}^n$$
Dla każdego takiego wierzchołka wykonuje się wyliczenie dystansu, co jest operacją o stałej złożoności czasowej, dlatego całość to:
$$\sum_{i=0}^n\sum_{i=j}^n 1 = \sum_{i=0}^n (n-i) = \sum_{i=0}^n n - \sum_{i=0}^n i = n^2 - \frac{1}{2}n(n+1) = \frac{n^2}{2} - \frac{n}{2}$$
Złożoność czasowa to $O(n^2)$
\end{frame}
\begin{frame}{Algorytm najbliższego sąsiada}
Czy macie pomysł na ulepszenie?
\end{frame}{}
\begin{frame}{Algorytm RNN}
RNN (repetitive nearest neighbour) - algorytm polega na wykonaniu algorytmu najbliższego sąsiada dla każdego wierzchołka początkowego i wybraniu najlepszego rozwiązania.
\\~\\
\pause
Jaka jest złożoność algorytmu?
\pause
$$O(n^3)$$
\\~\\
\pause
Czy algorytm jest dokładny?
\pause
Czy algorytm ma gwarancję znalezienia cyklu w grafie, który nie jest pełny?
\end{frame}
\begin{frame}{Algorytm najmniejszej krawędzi}
Algorytm polega na kolejnym dołączaniu do rozwiązania najkrótszych spośród dopuszczalnych krawędzi.
\\~\\
Działanie można zapisać następująco:
\begin{itemize}
\item Posortuj wszystkie krawędzie rosnąco według ich wag, umieść je w kolejce
\item Pobierz z kolejki krawędź o najmniejszej wadze, usuń ją z kolejki
\item Sprawdź, czy dołączenie tej krawędzi do rozwiązania nie spowoduje utworzenia cyklu (nie dotyczy ostatniej iteracji) lub powstania wierzchołka, z którego wychodzą trzy krawędzie. Jeśli nie, dołącz krawędź do rozwiązania
\item Jeśli liczba krawędzi dołączonych do rozwiązania jest równa liczbie wierzchołków, zakończ działanie algorytmu. W przeciwnym razie przejdź do punktu 2
\end{itemize}
\end{frame}
\begin{frame}{Algorytm najmniejszej krawędzi}
\begin{center}
\begin{tikzpicture}
\node[shape=circle,draw=black] (A) at (0,0) {A};
\node[shape=circle,draw=black] (B) at (1,1) {B};
\node[shape=circle,draw=black] (C) at (0,3) {C};
\node[shape=circle,draw=black] (D) at (5,0) {D};
\path[-]
(B) edge node {} (C)
(B) edge node {} (A)
(B) edge node {} (D)
;
\end{tikzpicture}
\end{center}
\begin{alertblock}{Uwaga}
Powstanie wierzchołka, z którego wychodzą 3 krawędzie
\end{alertblock}
\end{frame}
\begin{frame}{Algorytm najmniejszej krawędzi}
\begin{center}
\begin{tikzpicture}
\node[shape=circle,draw=black] (A) at (0,0) {A};
\node[shape=circle,draw=black] (B) at (1,1) {B};
\node[shape=circle,draw=black] (C) at (0,3) {C};
\node[shape=circle,draw=black] (D) at (5,0) {D};
\path[-]
(B) edge node {} (C)
(C) edge node {} (D)
(B) edge node {} (D)
;
\end{tikzpicture}
\end{center}
\begin{alertblock}{Uwaga}
Powstanie cyklu przed ostatnią iteracją
\end{alertblock}
\end{frame}
\begin{frame}{Algorytm najmniejszej krawędzi}
\begin{center}
\begin{tikzpicture}
\node[shape=circle,draw=black] (A) at (1,0) {A};
\node[shape=circle,draw=black] (B) at (1,3) {B};
\node[shape=circle,draw=black] (C) at (2,3) {C};
\node[shape=circle,draw=black] (D) at (2,6) {D};
\node[shape=circle,draw=black] (E) at (6,4) {E};
\node[shape=circle,draw=black] (F) at (6,2) {F};
\onslide<2->\path[-] (B) edge node {} (C);
\onslide<3->\path[-] (E) edge node {} (F);
\onslide<4->\path[-] (B) edge node {} (A);
\onslide<5->\path[-] (D) edge node {} (C);
\onslide<6->\path[-] (D) edge node {} (E);
\onslide<7->\path[-] (A) edge node {} (F);
\end{tikzpicture}
\end{center}
\end{frame}
\begin{frame}{Algorytm najmniejszej krawędzi}
Złożoność czasowa algorytmu to:
$$O(n^2\log n)$$
\\~\\
\pause
Należy pamiętać, że to algorytm przybliżony. Podaje się, że jego rozwiązanie jest średnio 16\% gorsze od optymalnego
\end{frame}
\begin{frame}{Algorytm Christofidesa}
Mając graf $G$:
\begin{itemize}
\item stworzyć minimalne drzewo rozpinające $T$,
\item stworzyć zbiór $S$ wierzchołków, które mają nieparzysty stopień w $T$,
\item znaleźć skojarzenie doskonałe $M$ z $S$,
\item dodać $M$ do $T$, aby zbudować graf $C$, w którym wszystkie wierzchołki mają parzysty stopień,
\item stworzyć cykl eulera z $C$,
\item usunąć powtórzone wierzchołki z $C$,
\end{itemize}{}
\end{frame}
\begin{frame}{Algorytm Christofidesa}
\begin{center}
Graf $G$
\end{center}
\begin{center}
\begin{tikzpicture}
\node[shape=circle,draw=black] (A) at (0,0) {A};
\node[shape=circle,draw=black] (B) at (2,-1) {B};
\node[shape=circle,draw=black] (C) at (4,0) {C};
\node[shape=circle,draw=black] (D) at (1,1) {D};
\node[shape=circle,draw=black] (E) at (3,1) {E};
\path[-]
(A) edge node {} (B)
(A) edge node {} (C)
(A) edge node {} (D)
(A) edge node {} (E)
(B) edge node {} (C)
(B) edge node {} (D)
(B) edge node {} (E)
(C) edge node {} (D)
(C) edge node {} (E)
(D) edge node {} (E)
;
\end{tikzpicture}
\end{center}
\end{frame}
\begin{frame}{Algorytm Christofidesa}
\begin{center}
Minimalne drzewo spinające $T$
\end{center}
\begin{center}
\begin{tikzpicture}
\node[shape=circle,draw=black] (A) at (0,0) {A};
\node[shape=circle,draw=black] (B) at (-2,-2) {B};
\node[shape=circle,draw=black] (C) at (0,-2) {C};
\node[shape=circle,draw=black] (D) at (2,-2) {D};
\node[shape=circle,draw=black] (E) at (2,-4) {E};
\path[-]
(A) edge node {} (B)
(A) edge node {} (C)
(A) edge node {} (D)
(D) edge node {} (E)
;
\end{tikzpicture}
\end{center}
\pause
\begin{center}
Zbiór wierzchołków o nieparzystym stopniu: $\{B,C,A,E\}$
\end{center}
\end{frame}
\begin{frame}{Algorytm Christofidesa}
\begin{center}
Skojarzenie doskonałe $\{B,C,A,E\}$
\end{center}
\begin{center}
\begin{tikzpicture}
\node[shape=circle,draw=black] (A) at (0,0) {A};
\node[shape=circle,draw=black] (B) at (2,0) {B};
\node[shape=circle,draw=black] (C) at (2,2) {C};
\node[shape=circle,draw=black] (D) at (0,2) {D};
\path[-]
(B) edge node {} (C)
(A) edge node {} (D)
;
\end{tikzpicture}
\end{center}
\end{frame}
\begin{frame}{Algorytm Christofidesa}
\begin{center}
Połączenie minimalnego drzewa rozpinającego:
\end{center}
\begin{center}
\begin{tikzpicture}[thick,scale=0.4, every node/.style={scale=0.5}]
\node[shape=circle,draw=black] (A) at (0,0) {A};
\node[shape=circle,draw=black] (B) at (-2,-2) {B};
\node[shape=circle,draw=black] (C) at (0,-2) {C};
\node[shape=circle,draw=black] (D) at (2,-2) {D};
\node[shape=circle,draw=black] (E) at (2,-4) {E};
\path[-]
(A) edge node {} (B)
(A) edge node {} (C)
(A) edge node {} (D)
(D) edge node {} (E)
;
\end{tikzpicture}
\end{center}
\begin{center}
Ze skojarzeniem doskonałym
\end{center}
\begin{center}
\begin{tikzpicture}[thick,scale=0.4, every node/.style={scale=0.5}]
\node[shape=circle,draw=black] (A) at (0,0) {A};
\node[shape=circle,draw=black] (B) at (2,0) {B};
\node[shape=circle,draw=black] (C) at (2,2) {C};
\node[shape=circle,draw=black] (E) at (0,2) {E};
\path[-]
(B) edge node {} (C)
(A) edge node {} (E)
;
\end{tikzpicture}
\end{center}
\begin{center}
Daje w efekcie:
\end{center}
\begin{center}
\begin{tikzpicture}[thick,scale=0.4, every node/.style={scale=0.5}]
\node[shape=circle,draw=black] (A) at (0,0) {A};
\node[shape=circle,draw=black] (B) at (-2,-2) {B};
\node[shape=circle,draw=black] (C) at (0,-2) {C};
\node[shape=circle,draw=black] (D) at (2,-2) {D};
\node[shape=circle,draw=black] (E) at (2,-4) {E};
\path[-]
(A) edge node {} (B)
(A) edge node {} (C)
(A) edge node {} (D)
(D) edge node {} (E)
(A) edge node {} (E)
(B) edge node {} (C)
;
\end{tikzpicture}
\end{center}
\end{frame}
\begin{frame}{Algorytm Christofidesa}
\begin{center}
Wyznaczenie cyklu eulera
\end{center}
\begin{center}
\begin{tikzpicture}
\node[shape=circle,draw=black] (A) at (0,0) {A};
\node[shape=circle,draw=black] (B) at (-2,-2) {B};
\node[shape=circle,draw=black] (C) at (0,-2) {C};
\node[shape=circle,draw=black] (D) at (2,-2) {D};
\node[shape=circle,draw=black] (E) at (2,-4) {E};
\path[-]
(A) edge node {} (B)
(A) edge node {} (C)
(A) edge node {} (D)
(D) edge node {} (E)
(A) edge node {} (E)
(B) edge node {} (C)
;
\end{tikzpicture}
\end{center}
\begin{center}
Należy zacząć od dowolnego wierzchołka i prowadzić taką ścieżkę, która nie podzieli grafu na dwa oddzielone zbiory wierzchołków
\end{center}
\pause
\begin{center}
$\{A,B,C,A,E,D,A\}$
\end{center}
\end{frame}
\begin{frame}{Algorytm Christofidesa}
Następnie z wcześniej ustalonego zbioru
\begin{center}
$\{A,B,C,A,E,D,A\}$
\end{center}
\pause
Należy usunąć duplikaty
\begin{center}
$\{A,B,C,E,D\}$
\end{center}
\pause
\begin{center}
\begin{tikzpicture}
\node[shape=circle,draw=black] (A) at (0,0) {A};
\node[shape=circle,draw=black] (B) at (-2,-2) {B};
\node[shape=circle,draw=black] (C) at (0,-2) {C};
\node[shape=circle,draw=black] (D) at (2,-2) {D};
\node[shape=circle,draw=black] (E) at (2,-4) {E};
\path[-]
(A) edge node {} (B)
(B) edge node {} (C)
(C) edge node {} (E)
(E) edge node {} (D)
(D) edge node {} (A)
;
\end{tikzpicture}
\end{center}
\end{frame}
\begin{frame}{Algorytm Christofidesa}
Algorytm jest $\frac{3}{2}$ optymalny, co oznacza, że gwarantuje znalezienie rozwiązania maksymalnie $\frac{3}{2}$ gorszego od optymalnego.
\\~\\
Złożoność czasowa w najgorszym przypadku to $O(n^3)$
\\~\\
Złożoność pamięciowa to $O(n)$
\end{frame}
\begin{frame}{Rój mrówek}
Marco Dorigo w 1993 roku opisał metodę heurystyczną rozwiązania problemu komiwojażera używając symulacji kolonii mrówek. Metoda odwzorowuje zachowanie rzeczywistych mrówek, które szukają najkrótszych tras pomiędzy jedzeniem a mrowiskiem.
\end{frame}
\begin{frame}{Rój mrówek}
Każda mrówka wybiera miasto, do którego następnego pójdzie na podstawie losowości, dystansu do miasta oraz ilości feromonu na drodze do tego miasta. Po zakończeniu iteracji, mrówka, która znalazła najkrótszą trasę, zostawia na niej ilość feromonu odwrotnie proporcjonalną do długości drogi
\begin{center}
\includegraphics[scale=0.3]{mrowki.png}
\end{center}
\end{frame}
\begin{frame}{Heurystyka genetyczna}
Ciekawym podejściem do problemu komiwojażera jest heurystyka genetyczna.
\pause
\\~\\
Metoda na początku dla zadanej wielkości populacji tworzy losowe cykle.
\pause
\\~\\
Następnie robi operacje krzyżowania i mutacji.
\pause
\\~\\
Następnie sortuje ścieżki i odrzuca wykraczające poza populację.
\pause
\\~\\
Metoda powtarza się zadaną liczbę razy.
\end{frame}
\begin{frame}{Heurystyka genetyczna}
Metoda przyjmuje parametry:
\begin{itemize}
\item liczba iteracji,
\item rozmiar populacji,
\item liczba krzyżowań,
\item liczba mutacji,
\end{itemize}{}
\end{frame}
\begin{frame}{Heurystyka genetyczna}
Rozważmy rozmiar populacji $3$ i tak wygenerowane cykle:
$$B-D-H-E-G-F-I-C$$
$$B-I-E-C-H-D-G-F$$
$$E-F-D-C-G-I-H-B$$
\pause Skrzyżujmy cykl trzeci z drugim:
\pause$$E-F-D-C-B-I-H-G$$
\pause Przeprowadźmy mutację w pierwszym cyklu:
\pause$$C-D-H-E-G-F-I-B$$
\end{frame}
\begin{frame}{Heurystyka genetyczna}
W rezultacie dostajemy nową populację:
$$B-D-H-E-G-F-I-C$$
$$B-I-E-C-H-D-G-F$$
$$E-F-D-C-G-I-H-B$$
$$E-F-D-C-B-I-H-G$$
$$C-D-H-E-G-F-I-B$$
Należy ją teraz posortować i odrzucić przypadki wychodzące poza limit populacji
\end{frame}
\begin{frame}{Źródła}
\begin{enumerate}
\item https://en.wikipedia.org/wiki/Travelling\_salesman\_problem
\item http://algorytmy.ency.pl/problem\_komiwojazera\_algorytm\_genetyczny
\item https://www.youtube.com/watch?v=dNCwtFJLsKI (wytłumaczony algorytm Christofidesa)
\item http://algorytmy.ency.pl/artykul/problem\_komiwojazera (wytłumaczone algorytm Helda-Karpa, NN, RNN)
\item https://www.math.uwaterloo.ca/tsp/d15sol/dhistory.html
\item https://vc.bridgew.edu/undergrad\_rev/vol7/iss1/17/
\end{enumerate}{}
\end{frame}{}
\end{document}
Editor is loading...