Problem komiwojażera - omówienie

Nasza ocena:

3
Pobrań: 203
Wyświetleń: 1344
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
Problem komiwojażera - omówienie - strona 1 Problem komiwojażera - omówienie - strona 2 Problem komiwojażera - omówienie - strona 3

Fragment notatki:

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)

Zaloguj się, aby dodać komentarz