Witam, mam następujący problem:
"Fabuła"
Są dwie wyróżnione wyspy. Jeden "S" (start), drugi "P" (koniec)". Pomiędzy nimi są mniejsze wyspy, każda oddalona bardziej na północ od poprzedniej ( "S" jest najbardziej na południu, "P" najbardziej na północy ). Rano statek może podróżować tylko na północ, południem tylko na południe. Statek musi odwiedzić wszystkie ( niekoniecznie tylko podczas jednej drogi) wyspy, dotrzeć do "P" ( ostatniego punktu ) i wrócić do "S". Statek może odwiedzać wyspy podczas drogi na północ lub południe. Trzeba znaleźć optymalną drogę. Waga każdej krawędzi jest znana, oczywiście wyspy mogą znajdować dowolnie daleko "na zachód" lub "na wschód". Jakby co mogę wstawić obrazek nakreślający problem.
Problem
Pomijam kwestie samego rozwiązania Problemu Komiwojażera, na to są algorytmy. Problemem moim jest to, że nie wiem jak połączyć fakt, że niektóre wierzchołki trzeba odwiedzić podczas pierwszej drogi na północ ( z "S" do "P" ) , a niektóre podczas drogi powrotnej na południe ( z "P" do "S") i dopiero to da optymalny wynik.
Jedyna (być może) wskazówka to taka, że ten temat na wykładzie był poruszany tylko podczas omawiania Algorytmu Kruskala i rozwiązywania PK z użyciem minimalnych drzew rozpinających.
Pytania:
- Ma ktoś jakiś pomysł jak to ugryźć?
- Spotkał się ktoś z tym problemem?
- Może ktoś zarzucić linkiem dotyczącym tego problemu? Ja nie znalazłem nic na anglojęzycznych stronach.
Każda pomoc jest mile widziana.
Po namyśle - czy fakt, że "rano" można poruszać się tylko na północ i "po południu" można poruszać się tylko na południe sugeruje, że to problem Bitonicznego Komiwojażera? A jeśli tak, to jak wybierać odpowiednie wyspy do ścieżki "porannej" i "południowej"? :/