W październiku 2022 roku napisałem tu, że korzystając z obwiedni wypukłych można wyznaczyć trasę komiwojażera (ang. Salesman problem).
Rzecz dzieje się na płaszczyźnie, mamy n miast, należy wyznaczyć trasę między wszystkimi miastami o najmniejszym koszcie, Tutaj potrzebuję współrzędnych miast, nie tylko symetrycznej macierzy kosztów podróży. Te dodatkowe informacje są potrzebne do wyznaczenia obwiedni wypukłych.
Heurystyka wyznacza najpierw obwiednię wypukłą A, która finalnie przekształci się w trasę komiwojażera K. Następnie wyznacza z pozostałych miast obwiednię wypukłą B. Miasta z B będą przemieszczane do A i równocześnie do K jako nadzbioru A.
Drobny kłopot związany z pierwszą krawędzią, oraz posiłkując się kolejnymi miastami obwiedni, dwa z A oraz najbliższe kolejne dwa z obwiedni B siłowo wyznaczam (dodatkowo ustalone już jest miasto startowe), kończę na obwiedni na której przesuwam się o miasto według orientacji.
Cały czas korzystam z pary miast, dwa z obwiedni A oraz miast doń przyległych wyznaczonej trasy; drugie z obwiedni B. Zatem mam do czynienia z trzech do czterech miast ułożonych liniowo dla wyznaczenia kosztu podróży, by przesunąć miasto z B do A. Permutacja jest tylko między sposobami zazębiania grafów. Np. a,c in A; b,d in B, trasy: acbd, abdc, abcd, także przed/za miasto zca, cde gdzie z, e in K są sąsiadami odpowiednio a oraz c trasy K.
Kiedy zamknę cykl, obwiednie przekształcą się w cykliczny graf skierowany przechodzące trasą przez wszystkie uwzględnione miasta, myślałem, że o najmniejszej długości.
W październiku brałem do nowo generowanego w kolejnych iteracjach A miasta obwiedni B, oraz wyznaczałem nową obwiednię B z miast jeszcze nie odwiedzonych. I tu pojawia się kłopot. Ta trasa niekoniecznie jest optymalną.
Potrafi wystąpić przypadek niezbyt intuicyjny, kiedy trasa biegnie miastami obwiedni zewnętrznej, oraz suma długości trasy jest MNIEJSZA od odległości sąsiednich miast obwiedni wewnętrznej. Oszacowałem trasę, i wydaje mi się, że w tym przypadku miasta takie nie mogą być usuwane z A podczas przechodzenia do kolejnej iteracji, nowa obwiednia A powinna składać się z miast obwiedni B oraz dodatkowo tych miast.
Przy tej modyfikacji naprawia się przypadek, kiedy jakieś miasto z B leży daleko od miast październikowej obwiedni A, ale wystarczajaco blisko trasy K, by je połączyć w jedną trasę od miast K.
Oczywiście, podobnie jak w pażdzierniku, kiedy zbiór nieodwiedzonych jeszcze miast staje sie pusty, wyznaczony graf cykliczny skierowany staje się bardziej optymalną trasą komiwojażera.
