3-opc
W optymalizacji 3-opt to prosty algorytm wyszukiwania lokalnego służący do rozwiązywania problemu komiwojażera i powiązanych problemów optymalizacji sieci. W porównaniu z prostszym 2-opt jest wolniejszy, ale może generować rozwiązania o wyższej jakości.
Analiza 3-opt polega na usunięciu 3 połączeń (lub krawędzi) w sieci (lub trasie), aby utworzyć 3 trasy podrzędne. Następnie analizowanych jest 7 różnych sposobów ponownego podłączenia sieci w celu znalezienia optymalnego. Ten proces jest następnie powtarzany dla innego zestawu 3 połączeń, aż wszystkie możliwe kombinacje zostaną wypróbowane w sieci. Pojedyncze wykonanie 3-opt ma złożoność czasową . Iterowany 3-opt ma wyższą złożoność czasową.
Jest to mechanizm, za pomocą którego 3-opt swap manipuluje daną trasą:
def reverse_segment_if_better ( tour , i , j , k ): """Jeśli odwrócenie trasy [i:j] skróciłoby trasę, zrób to.""" # Biorąc pod uwagę trasę [...AB...CD.. .EF...] A , B , C , D , E , F = trasa [ i - 1 ], trasa [ i ], trasa [ j - 1 ], trasa [ j ], trasa [ k - 1 ], trasa [ k % len ( trasa )] d0 = odległość ( A , B ) + odległość ( C , D ) + odległość ( E , F ) d1 = odległość ( A , C ) + odległość ( B , D ) + odległość ( E , fa ) d2 = odległość ( A , B ) + odległość ( C , E ) + odległość ( re , fa ) d3 = odległość ( A , re ) + odległość ( mi , b ) + odległość ( do , fa ) d4 = odległość ( F , B ) + odległość ( C , D ) + odległość ( E , A ) jeśli d0 > d1 : trasa [ i : j ] = odwrócona ( trasa [ i : j ]) powrót - d0 + d1 elif d0 > d2 : trasa [ j : k ] = odwrócone ( trasa [ j : k ]) powrót - d0 + d2 elif d0 > d4 : trasa [ i : k ] = odwrotność ( trasa [ i : k ]) powrót - d0 + d4 elif d0 > d3 : tmp = trasa [ j : k ] + trasa [ i : j ] trasa [ i : k ] = tmp powrót - d0 + d3 powrót 0
Zasada jest dość prosta. Obliczasz pierwotną odległość koszt każdej modyfikacji. Jeśli znajdziesz lepszy koszt, zastosuj modyfikację i zwróć koszt względny) To jest kompletna 3-optyczna zamiana wykorzystująca powyższy mechanizm:
0
0
0 def three_opt ( tour ): """Poprawa iteracyjna oparta na 3 wymianach.""" while True : delta = for ( a , b , c ) in all_segments ( len ( tour )): delta += reverse_segment_if_better ( tour , a , b , c ) if delta >= : break return tour def all_segments ( n : int ): """Wygeneruj wszystkie kombinacje segmentów""" return (( i , j , k ) for i in range ( n ) for j in range ( ja + 2 , n ) dla k w przedziale ( j + 2 , n + ( ja > )))
Dla danej wycieczki generujesz wszystkie kombinacje segmentów i dla każdej kombinacji próbujesz ulepszyć wycieczkę, odwracając segmenty. Gdy znajdziesz lepszy wynik, ponownie uruchom proces, w przeciwnym razie zakończ.
Zobacz też
- F.BOCK (1965). Algorytm rozwiązywania komiwojażerów i związanych z nimi problemów optymalizacji sieci . niepublikowany manuskrypt związany z referatem wygłoszonym na XIV ORSA .
- S. LIN (1965). Komputerowe rozwiązania problemu komiwojażera . System dzwonka Technika J.44, 2245-2269. Dostępne w formacie PDF [ stały martwy link ]
- S. LIN I BW KERNIGHAN (1973). Efektywny algorytm heurystyczny dla problemu komiwojażera . Operacje Rez. 21, 498-516. Dostępne w formacie PDF [ stały martwy link ]
- Heurystyka wyszukiwania lokalnego. (nd) Pobrano 16 czerwca 2008 r. z http://www.tmsk.uitm.edu.my/~naimah/csc751/slides/LS.pdf [ stały martwy link ]