To tylko jedna z 4 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Problem komiwojażera
Problem trudny obliczeniowo:
Algorytmy dokładne (szukanie rozwiązania optymalnego może trwać dłużej)
Algorytmy przybliżone (heurystyki): szybkie, nie zawsze doprowadzają do rozwiązania optymalnego.
Algorytm dokładny (z rodziny algorytmów podziału i ograniczeń, branch and bound) (Little'a)
A
B
C
D
E
A
∞
2
1
3
4
B
1
∞
6
5
7
C
4
3
∞
8
2
D
5
7
4
∞
1
E
2
3
5
2
∞
Procedura A: Zredukować macierz - by w każdym wierszu i w każdej kolumnie było przynajmniej jedno 0: odejmowanie od wierszy minimalnego elementu, a potem od kolumn minimalnego elementu. Suma odjętych wartości jest wartością redukcji. Procedura B (wyznaczenie elementu o maksymalnym żalu): wyznaczenie dla każdego zerowego elementu macierzy sumę minimum z wiersza (poza danym elementem) i minimum z kolumny (poza danym elementem), wyznaczenie elementu, dla którego ta suma jest maksymalna.
1. bieżący wierzchołek macierz: macierz zredukowana: A(0) - szczyt drzewa, aktualne ograniczenie: wartości redukcji, aktualna długość trasy: nieskończoność.
2. Wyznaczyć w bieżącym wierzchołku element o maksymalnym żalu
3. Narysować dwóch potomków bieżącego wierzchołka: jeden odpowiada trasom zawierającym element o maksymalnym żalu, drugi - trasom nie zawierającym tego elementu
4. Dla pierwszego potomka: eliminujemy wiersz i kolumnę odpowiadajże wybranemu elementowi, zabraniamy cykli, redukujemy macierz, dodajemy wartość redukcji do ograniczenia rodzica, otrzymując ograniczenie potomka
5. Dla drugiego potomka: blokujemy zabronioną trasę, redukujemy macierz, dodajemy wartość redukcji do ograniczenia rodzica, otrzymując ograniczenie potomka
6. Jeśli w którymś z niezamkniętym wierzchołków końcowych jest pełna trasa, zapisujemy jej długość (aktualna długość trasy), jeśli jest mniejsza od aktualnej długości trasy i zamykamy ten wierzchołek. 7. Jeśli istnieje wierzchołek końcowy niezamknięty, w którym ograniczenie jest niższe niż aktualna długość trasy, wybieramy ten, w którym to ograniczenie jest najmniejsze. Wracamy do kroku 3. W przeciwnym przypadku koniec.
Odp.
... zobacz całą notatkę
Komentarze użytkowników (0)