Post by Filip SielimowiczPost by NewsChodzi mi algorytm wyzanaczania najdłuższej ścieżki prostej w grafie.
Wydaje mi się, że algorytm jest NP-zupełny, ponieważ, jeśli dobrze
myślę, łatwo da się do niego transformować problem komiwojażera
(najkrótszy cykl w grafie zawierający wszystkie wierzchołki).
Transformacja wyglądałaby tak: mamy graf A to budujemy graf
B z takimi samymi wierzchołkami i połączeniami, ale zmieniamy wagi
połączeń wg. prostej reguły Wb = C - Wa, gdzie C to długość
najdłuższej krawędzi w A. Najdłuższa droga w A jest najkrótszą w B,
zgadza się ?
Czyli nie ma dobrego algorytmu.
IMHO nie jest aż tak źle.
Problem polegał na odnalezieniu najdłuższej __ścieżki_prostej__ (tzw.
elementarnej), czyli takiej, której wierzchołki nie powtarzają się (być
może poza początkowym i końcowym), stąd nie można domniemywać, że musisz
zaraz pokryć wszystkie węzły (jak w przytoczonym problemie
przedstawiciela handlowego...).
Jednak wskazówka Twoja może być tu cenna, bo dla Twojego grafu
transformacji (B) można by algorytm Dijkstry zaprząc i najkrótsze
"znalezisko" traktować właśnie za najdłuższą ścieżkę elementarną.
Jedyny problem jaki dostrzegam to fakt, że w przypadku algorytmu
Dijkstry możliwość wspólnego końca i początku odpada z założenia, a tak
rozpięta ścieżka elementarna jest potencjalnym rozwiązaniem niniejszego
zadania.
I tu można by sklecić takiego "dwufazowego Dijkstrę", czyli po
znalezieniu najkrótszej ścieżki (dla uproszczenia mówię w liczbie
pojedynczej), wyciąć z grafu jej wszystkie węzły (poza oczywiście
pierwszym i ostatnim) i w powstałym tak grafie ponownie wyszukać
najkrótszej drogi, ale już tylko pomiędzy początkiem a końcem ścieżki
odnalezionej wcześniej.
Za rozwiązanie zaś traktować najkrótsze złożenie(a) wyników.
Oczywiście drugi etap to musi być lekko zmodyfikowany Dijkstra, lub
(jeśli jest, a pewnie jest) inny wręcz algorytm szukania najkrótszej
ścieżki między podanymi węzłami (nie wiem czy to aby do tego, ale gdzieś
mi się jakiś pomysł Dinica czy jakoś tak kołacze, nie wiem, do
sprawdzenia...).
Jest tu też jeszcze pewna wątpliwość, której nie potrafię już tak sobie
łatwo wyjaśnić, czy aby tak odnaleziona "sklejka" jest też najkrótszym z
możliwych złożeń?
Z pewnością jest tak w przypadku gdy druga faza poszukiwań nie
przyniesie rezultatu (jest tylko jedna najkrótsza droga, więc już żadne
inne złożenie nie będzie krótsze).
Trochę inaczej jednak ma się sytuacja w drugim przypadku, bo choć
intuicyjnie wygląda, że też tak będzie, to jakoś nie dostrzegam tu
jednoznacznego dowodu potwierdzającego słuszność takiej tezy (może jakiś
śnieg zgarniać, czy coś by się dało, no nie wiem, TBD...).
No ale dość na tym, bo pewnie zaraz ktoś z Szanownych Grupowiczów poda
jakieś prostsze rozwiązanie i wszystko będzie jasne.
Z mojej tyle.
Pozdrawiam
piotr