Ist die Verbindung der Inseln mit den Pontons NP-vollständig?

10

Ich habe ein Problem im Kopf, ich denke, es ist ein NPC-Problem, aber ich weiß nicht, wie ich es beweisen soll.

Hier ist das Problem:

Es gibt k Inseln in einem sehr großen See und es gibt n fächerförmige Pontons. Diese Pontons haben die gleiche Größe, aber unterschiedliche Anfangsrichtungen und befinden sich an unterschiedlichen ursprünglichen Positionen im See. Die Pontons können sich frei um ihren Schwerpunkt drehen, ohne dass mit der Rotation Kosten verbunden sind.

Jetzt müssen wir diese Pontons bewegen, damit alle Inseln im See verbunden werden können. Wir können garantieren, dass die Anzahl der Pontons ausreicht, um alle Inseln zu verbinden.

[Anmerkung]: Wir können die Pontons nicht wiederverwenden !!

Die Aufgabe besteht darin, die Lösung mit dem minimalen Gesamtabstand der sich bewegenden Pontons zu finden, um alle Inseln miteinander zu verbinden. Die Entfernung, um einen Ponton zu bewegen, kann als die Entfernung zwischen der ursprünglichen Position des Massenschwerpunkts und seiner ausgefahrenen Position berechnet werden.

Um es klar zu machen, habe ich eine solche Figur gezeichnet. Angenommen, wir haben 3 Inseln A, B und C. Sie befinden sich irgendwo im See. Und ich habe mehrere fächerförmige Pantoons. Die Lösung besteht nun darin, eine minimale Bewegungsdistanzsummierung für die Verbindung von A, B und C zu finden, die im unteren Teil der Abbildung dargestellt ist. Hoffe, es hilft, das Problem zu verstehen. :) :)

Geben Sie hier die Bildbeschreibung ein

Es scheint, dass das Problem ein NPC ist, aber ich weiß nicht, ob ich es beweisen soll. Kann mir jemand dabei helfen?

Tsuyoshi Ito
quelle
@vsaxena Nein, ich glaube nicht, dass die endgültige Lösung eine gerade Linie ist, manchmal, wenn sie bereits einen Bogen bildet, aber wir müssen keinen von ihnen bewegen. In den meisten Fällen ist eine gerade Linie gut, aber da die Pontons dichter werden, ist die Lösung möglicherweise keine gerade Linie. Die Abbildung ist nur ein Beispiel. :)
1
Scheint sehr nah an Steiner Tree. In einem metrischen Raum arbeiten viele Techniken zur Lösung beider Probleme. en.wikipedia.org/wiki/…
Nicholas Mancuso
@NicholasMancuso Die Brücken sind Knoten zu Knoten, es handelt sich also nicht um einen klassischen Steiner-Baum, bei dem die Brücke mehrere Knoten verbindet. Es gibt viele Probleme im VLSI-Layout, die ähnliche Eigenschaften aufweisen.
VSOverFlow
1
@vsaxena: Das Problem ist nicht genau spezifiziert. Angenommen, ich habe drei Inseln A, B, C in einem gleichseitigen Dreieck, und die Pontons bilden anfänglich eine verbundene Y-Form mit den Inseln an den Enden. Ist nichts eine gültige Lösung oder müssen die Pontons weiter verschoben werden? Wenn diese Lösung nicht gültig ist, was genau macht dann eine gültige Konfiguration der Pontons aus?
JeffE
1
@vsaxena: Und wenn wir schon dabei sind, sind die Inseln nur Punkte oder Kreise oder eine kompliziertere Form, die in der Eingabe angegeben ist? Sind die Pontons Liniensegmente oder Ellipsen oder eine andere Form? Sind alle Inseln gleich groß und gleich geformt oder können sie unterschiedlich sein? Haben alle Pontons die gleiche Größe und Form oder können sie unterschiedlich sein?
JeffE

Antworten:

1

Erstens: Dies ist nicht das Problem des Handlungsreisenden. Der TSP erfordert die Identifizierung eines Hamilton-Zyklus mit minimalem Gewicht; Dieser Zyklus erfordert weder einen Zyklus noch einen minimalen Gewichtspfad. Es erfordert einen minimalen Kosten Aufbau eines Verbindungs Satz von Kanten, wo die Baukosten die Pontons auf bewegen basiert.

Zweitens: Dies ist nicht das Problem des Spanning Tree mit minimalem Gewicht. Siehe oben - wir benötigen eine Konstruktion mit minimalen Kosten und keine minimale Gewichtsidentifikation.

Drittens: Es scheint, dass der konstruierte Pfad ein Spanning Tree sein wird, aber nicht unbedingt ein mit minimalem Gewicht. Die Alternative ist, dass es sich um einen Spannbaum mit einigen zusätzlichen Kanten handelt, die zu einem Zyklus führen. Wenn wir jedoch in einer Konfiguration ohne Kanten beginnen, hat jede Kante einige positive Kosten und wir können immer einen Spanning Tree mit geringerem Gewicht finden, indem wir einfach keine zusätzlichen Kanten konstruieren.

Viertens: Sie sagen, die Pontons drehen sich frei; Ich gehe davon aus, dass mit dem Drehen der Pontons keine Kosten verbunden sind. Sie geben jedoch nicht an, um was sich die Pontons drehen: Ihre Punkte? Ihre Massenschwerpunkte? Irgendein interner Punkt? (Wenn irgendein externer Punkt, dann hätten wir Nullgewichtskonstruktionen, ja?)

Dies ist ein wenig subtil, denn wenn wir uns um 90 Grad um einen internen Punkt drehen, beispielsweise den Schwerpunkt, wie hoch sind die Kosten? Nichts, weil es eine Rotation ist? Eine endliche Menge, weil sich der Punkt bewegt hat? Jetzt müssen wir auch die Größe der Pontons kennen.

Fünftens: Man nimmt an, dass sowohl die Pontons als auch die Inseln in die euklidische Ebene eingebettet sind?

Novak
quelle
Vielen Dank für Ihre Antwort. Die Drehung erfolgt um den Schwerpunkt und keine mit der Drehung verbundenen Kosten, nur die Bewegung ist mit Kosten verbunden. Ja, sowohl Pontons als auch die Inseln sind in die euklidische Ebene eingebettet. Ich werde den Beitrag ändern, um es klar zu machen.
Ich bin nicht der Meinung, dass dies nicht im Wesentlichen der TSP ist. Dieser ganze Pfosten ist in der Terminologie um die Achse gewickelt, aber Tatsache ist, dass, wenn man eine Linie zwischen jedem Ponton und jeder möglichen Endpontonposition zeichnet und den Abstand jeder Linie als Gewicht berechnet, dann mit Ausnahme Wenn der Endpunkt zum Startpunkt zurückkehrt, sieht der gebildete Graph fast genau (zu einem Abschlag) wie der TSP aus. Ein Ponton oder eine Endposition ist ein Knoten in der Grafik, und die Gewichte setzen sich aus den Abständen zusammen. Der Hamilton-Zyklus bedeutet NUR, dass er dort endet, wo er begonnen hat.
2
Dies ist keine Antwort, sondern eine Reihe von Kommentaren.
Raphael
1

Nachdem ich mir die neuen Diagramme angesehen habe, sehe ich, dass Sie möglicherweise mehrere Pontons benötigen, um zwischen Inseln zu wechseln. Angesichts dessen könnten Sie einer Lösung des Steiner-Baum-Problems sehr nahe kommen, indem Sie die Knoten in Inseln verwandeln und eine ausreichend vielfältige Sammlung von Pontons mit kleinen Bögen erstellen. Wikipedia sagt, dass es tatsächlich ein PTAS für das Steiner-Baum-Problem gibt, daher kann ich nicht sofort sagen, dass dies es NP-vollständig macht. Wenn Sie sich jedoch die Details des Steiner-Baums ansehen, erhalten Sie möglicherweise entweder eine gute ungefähre Lösung oder zeigen, dass das Problem NP-vollständig ist.

mcdowella
quelle
Was Sie beschreiben, ist ein ungefährer Algorithmus, um zu einer nahezu optimalen Lösung zu gelangen. Wie können Sie jedoch überprüfen, ob die Lösung optimal ist?
Ich denke, das eigentliche Problem ist, dass Sie mehrere Pontons benötigen, um zwischen Inseln zu wechseln, was dazu führt, dass dies einem Steiner-Baum sehr ähnlich sieht. In Branch and Bound erfahren Sie, wie Sie von einer Untergrenze (z. B. durch Vernachlässigung einer Einschränkung) zu einer bekannten optimalen Lösung gelangen.
Mcdowella
2
@mcdowella Es ist kein Steiner-Baum, da jeder Ponton nur auf einer Brücke erscheinen kann. Es ist ein Punkt-zu-Punkt-System. Da die Kostenfunktion die Bewegung von Pontons ist, können Sie einen Fall haben, in dem die Brücke in weiten Bögen gebildet wird, die immer noch geringere Kosten als die geradlinige Lösung haben.
VSOverFlow
Dies kann unmöglich der Steiner aus einer anderen Perspektive sein. WIR KÖNNEN KEINE PUNKTE HINZUFÜGEN, nur um unseren Bedürfnissen zu entsprechen.
Trompetenlicks
1
Wenn Y-Übergänge zulässig sind, ist dies mindestens so schwierig wie das Steiner-Baum-Problem, da jedes Steiner-Baum-Problem in eines dieser Probleme umgewandelt werden kann. Erstellen Sie einfach viele Pontons und platzieren Sie sie so weit von den Inseln entfernt, dass dies nicht der Fall ist Es ist wirklich wichtig, welchen Ponton Sie wo verwenden. Wenn Sie dies lösen könnten, könnten Sie das Steiner-Baum-Problem lösen: Für dieses Argument spielt es keine Rolle, dass es einige Konfigurationen von Pontons gibt, die nicht zu Steiner-Baum-Problemen führen. Wenn Y-Übergänge nicht zulässig sind, müssen wir die Regeln genau kennen. Kreuzen sich die Wege an der Kreuzung?
Mcdowella
0

Nach dem Zeichnen ist dies immer noch ein NPC-Problem. Selbst wenn wir das Problem auf jeden Ponton reduzieren, können wir 1 von n Positionen einnehmen (dh bekannte Verbindungslinien. Um die bestmögliche Antwort zu erhalten, müssten wir jeden Ponton in jeder Position ausprobieren und seinen Abstand addieren, um jeweils zu diesen jeweiligen Positionen zu gelangen Zeit und Vergleich mit allen anderen. Wenn jeder Ponton in jeder Position getestet werden muss, müssen n! Kombinationen getestet werden.

Ich habe mich entschieden, die Bilder des Originalplakats mit einigen Ergänzungen zu bearbeiten, um die Grafikideen hinter diesem Problem zu zeigen.

Das folgende Bild zeigt alle (zur Vereinfachung minus 2) Pontons in unterschiedlichen Farben mit allen potenziellen Pontonendpositionen in ROT. Ich habe nur die Linien zwischen 3 Pontons und allen Endpositionen gezogen, aber man konnte sehen, wie VERRÜCKT dies werden könnte.

Sagen wir, dass wir nur zum Teufel den türkisfarbenen Ponton als ersten Schritt an der ihm am nächsten gelegenen Endstelle platzieren (obwohl wir vom TSP wissen, dass dies am Ende möglicherweise nicht optimal ist).

Unten sehen wir genau das, den Ponton und die Entfernung (auch bekannt als gewichtete Fahrstrecke), die er zurücklegen muss.

Geben Sie hier die Bildbeschreibung ein

Von hier aus kann ein virtueller Knoten mit den zwei Endpositionen neben der gerade platzierten Position erstellt werden. Die Entfernung vom festgelegten Knoten und die beiden benachbarten Knoten innerhalb des virtuellen Knotens haben eine virtuelle Verfahrstrecke von 0.

Unten sehen wir den virtuellen Knoten, der mit ALLEN möglichen Reisewegegewichten erstellt wurde, die dort platziert werden können.

Geben Sie hier die Bildbeschreibung ein

Um zu sehen, wie dies weitergehen würde und wie die optimalste Lösung (wie oft beim TSP zu sehen) nicht immer darin besteht, für jede Auswahl den kürzesten Abstand zu wählen, müssten wir im Wesentlichen alle Pfade für alle Knoten / virtuellen Knoten testen.

Am Ende könnte der erste Knoten des (TSP) -Problems einer der potenziellen Endpontonpunkte sein, und die daraus gezogenen Linien sind die Abstände von diesem Endpunkt zu allen anderen Pontons. Alle anderen Knoten werden danach zu virtuellen Knoten, wie ich dargestellt habe, wobei ihre Linien als Abstände / Gewichte zu allen verbleibenden Pontons usw. abfallen. Wie dieses Grafikproblem NICHT GENAU das Problem des reisenden Verkäufers ohne die LAST JUMP-Anforderung aus dem Hamilton-Zyklus ist, ist mir ein Rätsel. Um die genaue Antwort zu erhalten, müssen alle Pfade durch das Diagramm getestet werden.

Trompeten
quelle
1
Abgesehen davon, ob dies ein vernünftiges Modell des angegebenen Problems ist oder ob es sich tatsächlich um ein TSP-Modell handelt, funktionieren NP-Reduktionen nicht so. Sie zeigen nicht, dass Ihr Zielproblem als Instanz eines NPC-Problems eingestuft werden kann. Sie müssen zeigen, dass eine Instanz eines NPC-Problems als Ihr Zielproblem festgelegt werden kann.
2
Ach je. Wenn Sie sich die Mühe gemacht haben, meinen Kommentar und den von mir bereitgestellten Link zu lesen, haben Sie erfahren, dass der referenzierte Algorithmus genau ist (sie beweisen dies) und daher Ihrem Verständnis widerspricht. Beachten Sie, dass Ihre Meinung nahe legt, dass P! = NP - dies ist noch eine offene Frage. Also nein, du hast das nicht verstanden, sorry. (Selbst wenn es wahr wäre, dass NP-vollständige Probleme nicht besser als naiv gelöst werden könnten, wäre die Argumentation, die Sie verwenden, falsch.)
Raphael
2
O(1.3n)n
3
@ JeffE: Mit anderen Worten, diese Antwort beweist nur, dass das Problem wahrscheinlich NP-vollständig ist.
Tsuyoshi Ito