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.

	A	B	C	D	E
A	∞	3	4	5	4
B	3	∞	2	2	1
C	4	2	∞	1	2
D	5	2	1	∞	3
E	4	1	2	3	∞

Heurystyki

1. Heurystyka najbliższego sąsiada

2. Najlepszego włączenia

3. Algorytm dwuoptymalny: tworzymy trasę, dla każdej pary łuków niesąsiadujących (i,k) i (k,l) zastępujemy je łukami (i,l) i (k,l), aż otrzymamy lepszą trasę, na niej powtarzamy to samo.

Algorytmy genetyczne

1. Populacja (Adam i Ewa)

2. Określona pojemność planety, jeśli za dużo osobników, niektórzy giną

3. Rodzice mają potomków

4. Najczęściej słabsi giną, ale nie zawsze

5. mutacje

Potomkowie: część genów od jednego rodzica, część od drugiego

3 8

3: 0011

8: 0100

Potomkowie: miejsce krzyżowania 3:

0010 - 2

0101 - 9

Mutacja 0011 na m.3 - 0001

Dla komiwojażera: kod - dowolny ciąg o tylu elementach, ile jest punktów do odwiedzenia, np. 23541

Kodowanie trasy 12345(1)

23541: 5

2354: 51

354: 511

54: 5112

5: 51121

Odkodowywanie 51121:

23451: 1

2345: 12

345: 123

54: 1234

5: 12345

Inne kodowania: trasa 12345

2	3	4	5	1
Z 1	Z 2	Z 3	Z 4	5

Dzieci pobierają zamiennie odcinki od jednego rodzica i drugiego, a jeśli to jest niemożliwe, połączenie jest generowane losowo.

A0/8

nBA

BA

A2/12

A1/8

nAC

AC

nDE

DE

A4/13

A3/8

A5/15

A7/12

nCE

CE

A6/14

A5/13

nBD

BD

A12/15

A9/12

nEA

EA

A11/17

A10/12

---