Czy łączenie wysp z pontonami NP-zupełne?

Mam w głowie problem, myślę, że jest to problem NPC, ale nie wiem, jak to udowodnić.

Oto problem:

Istnieje k wyspy w bardzo dużym jeziorem, a tam są n kształcie wachlarza pontony. Te pontony są tego samego rozmiaru, ale mają różne początkowe kierunki i znajdują się w różnych oryginalnych pozycjach w jeziorze. Pontony mogą swobodnie obracać się wokół środka masy, bez rotacji.

Teraz musimy przenieść te pontony, aby wszystkie wyspy w jeziorze mogły zostać połączone. Możemy zagwarantować, że liczba pontonów wystarczy do połączenia wszystkich wysp.

[Uwaga]: Nie możemy ponownie wykorzystać pontonów !!

Zadaniem jest znalezienie rozwiązania mającego minimalną całkowitą odległość ruchomych pontonów, aby połączyć wszystkie wyspy. Odległość przemieszczenia jednego pontonu można obliczyć jako odległość między środkiem pierwotnej pozycji masy a jej położeniem rozłożonym.

Aby to wyjaśnić, narysowałem taką liczbę. Załóżmy, że mamy 3 wyspy A, B i C. Znajdują się one gdzieś w jeziorze. I mam kilka pantoonów w kształcie wachlarza. Teraz rozwiązaniem jest znalezienie sumy minimalnej odległości ruchu łączącej A, B i C, pokazanej w dolnej części rysunku. Mam nadzieję, że pomoże to zrozumieć problem. :)

Wygląda na to, że problemem jest NPC, ale nie wiem, jak to udowodnić. Czy ktoś może mi z tym pomóc?

Po pierwsze: to nie jest problem podróżującego sprzedawcy. TSP wymaga identyfikacji cyklu hamiltonowskiego o minimalnej wadze; ten cykl nie wymaga cyklu, ani nawet minimalnej ścieżki ciężaru. Wymaga to minimalnego kosztu budowy łączącego zestawu krawędzi, gdzie koszt budowy opiera się na przemieszczaniu pontonów.

Po drugie: nie jest to problem dotyczący drzewa rozpinającego minimalną wagę. Patrz wyżej - wymagamy minimalnego kosztu konstrukcji, a nie minimalnej identyfikacji ciężaru.

Po trzecie: Wygląda na to, że zbudowana ścieżka będzie drzewem łączącym, ale niekoniecznie drzewem o minimalnej wadze. Alternatywą jest to, że byłoby to drzewo opinające plus dodatkowe krawędzie, które skutkowałyby cyklem; ale jeśli zaczniemy od konfiguracji bez krawędzi, wówczas każda krawędź ma pewien dodatni koszt i zawsze możemy znaleźć drzewo rozpinające mniejszą wagę, po prostu nie konstruując dodatkowych krawędzi.

Po czwarte: Mówisz, że pontony obracają się swobodnie; Zakładam, że oznacza to, że z obrotami pontonów nie wiążą się żadne koszty. Nie określasz jednak, o czym obracają się pontony: ich punkty? Ich centra masy? Jakikolwiek punkt wewnętrzny? (Jeśli jakikolwiek punkt zewnętrzny, to mielibyśmy konstrukcje o zerowej wadze, tak?)

Jest to nieco subtelne, ponieważ jeśli obracamy się o 90 stopni wokół punktu wewnętrznego, powiedzmy, środka masy, jaki jest koszt? Nic, bo to rotacja? Jakaś skończona kwota, ponieważ punkt się przesunął? Teraz musimy również poznać rozmiar pontonów.

Po piąte: Zakłada się, że zarówno pontony, jak i wyspy są zatopione w płaszczyźnie euklidesowej?

Po zapoznaniu się z nowymi schematami widzę, że możesz potrzebować wielu pontonów, aby przepłynąć między wyspami. Biorąc to pod uwagę, można bardzo zbliżyć się do rozwiązania problemu Steiner Tree , przekształcając węzły w wyspy i tworząc wystarczająco różnorodną kolekcję pontonów o małych łukach. Wikipedia mówi, że w rzeczywistości istnieje problem PTAS dla problemu drzewa Steinera, więc nie mogę od razu powiedzieć, że powoduje to NP-kompletność. Jednak spojrzenie na szczegóły drzewa Steiner może albo dać ci dobre przybliżone rozwiązanie, albo pokazać, że problem dotyczy NP-Complete.

Po losowaniu nadal jest to problem NPC. Nawet jeśli ograniczymy problem do każdego pontonu, możemy przyjąć 1 z n pozycji (tj. Znane linie łączące. Aby uzyskać najbardziej optymalną odpowiedź, musielibyśmy wypróbować każdy ponton w każdej pozycji, dodając ich odległość, aby dostać się do tych powtarzalnych pozycji każdego czas i porównanie ze wszystkimi innymi. jeśli każdy ponton musi zostać przetestowany w każdej pozycji, to musi istnieć n! kombinacji.

Wybrałem edycję oryginalnych zdjęć plakatu z kilkoma dodatkami, aby pokazać pomysły na wykresy stojące za tym problemem.

Poniższy obrazek pokazuje wszystkie (minus 2, aby uprościć) pontony w różnych kolorach, ze wszystkimi potencjalnymi lokalizacjami końcowymi pontonu w kolorze CZERWONYM. Narysowałem tylko linie między 3 pontonami i wszystkimi końcowymi lokalizacjami, ale widać było, jak SZALONY może to być.

Powiedzmy, że dla samej cholery, wybieramy, aby turkusowy ponton został umieszczony w końcowej lokalizacji najbliżej niego jako pierwszy krok (chociaż Z TSP wiemy, że może to nie być optymalne na końcu).

Poniżej dokładnie to widzimy, ponton i odległość (czyli ważona odległość podróży), jaką będzie musiał pokonać.

Stąd można utworzyć wirtualny węzeł z dwoma końcowymi lokalizacjami obok właśnie umieszczonej lokalizacji. Odległość od ustawionego węzła i dwa sąsiednie węzły w obrębie wirtualnego węzła mają wirtualną odległość podróży wynoszącą 0.

Poniżej widzimy wirtualny węzeł utworzony ze WSZYSTKIM potencjalnym obciążnikiem odległości, jaki można tam umieścić.

Widząc, jak to będzie kontynuowane i jak najbardziej optymalnym rozwiązaniem (jak wielokrotnie widziane z TSP) nie zawsze będzie wybór najkrótszej odległości dla każdego wyboru, musielibyśmy przetestować zasadniczo wszystkie ścieżki dla wszystkich węzłów / wirtualnych węzłów.

Ostatecznie pierwszym węzłem problemu (TSP) może być dowolny z potencjalnych punktów końcowych pontonu, a linie z niego narysowane to odległości od tego punktu końcowego do wszystkich innych pontonów. wszystkie inne węzły stają się następnie węzłami wirtualnymi, jak to przedstawiłem, z ich liniami opadającymi jako odległości / ciężary do wszystkich pozostałych pontonów, i tak dalej. Jak ten problem z grafem NIE jest DOKŁADNIE problemem dla podróżujących sprzedawców bez OSTATNIEJ SKOKU z cyklu hamiltonowskiego jest poza mną. Aby uzyskać dokładną odpowiedź, należy przetestować wszystkie ścieżki na wykresie.