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

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

    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, weisen jedoch unterschiedliche Anfangsrichtungen auf und befinden sich in unterschiedlichen ursprünglichen Positionen im See. Die Pontons können sich frei um ihren Massenschwerpunkt drehen, und es entstehen keine mit der Rotation verbundenen Kosten.

    Nun müssen wir diese Pontons so verschieben, dass alle Inseln im See miteinander verbunden werden können. Wir können garantieren, dass die Anzahl der Pontons ausreicht, um alle Inseln miteinander zu verbinden.

    [strong] [Anmerkung]: Die Pontons können nicht wiederverwendet werden.

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

    Um es deutlich 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 gezeigt wird. Ich hoffe es hilft das Problem zu verstehen. :)

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

    Anscheinend handelt es sich bei dem Problem um einen NPC, aber ich weiß nicht, ob ich es beweisen kann . Kann mir da jemand weiterhelfen?

    08 June 2012
    David McGraw
3 answers
  • Nachdem ich mir die neuen Diagramme angesehen habe, sehe ich, dass Sie möglicherweise mehrere Pontons benötigen, um die Inseln zu überqueren. Angesichts dessen könnten Sie einer Lösung des Steiner Tree-Problems sehr nahe kommen, indem Sie die Knoten in umwandeln Inseln und schaffen eine ausreichend abwechslungsreiche Sammlung von Pontons mit kleinen Bögen. Wikipedia gibt an, dass es tatsächlich ein PTAS für das Steiner-Baumproblem gibt, daher kann ich nicht sofort sagen, dass es dadurch NP-vollständig wird. Wenn Sie jedoch die Details des Steiner-Baums betrachten, erhalten Sie entweder eine gute ungefähre Lösung oder zeigen, dass das Problem NP-Complete ist.

    07 June 2012
    Raphael
  • Erstens: Dies ist nicht das Problem des reisenden Verkäufers. Der TSP erfordert die Identifizierung eines Hamiltonschen Zyklus mit minimalem Gewicht. Dieser Zyklus erfordert keinen Zyklus oder gar einen minimalen Gewichtungspfad. Es erfordert einen minimalen Aufbau eines Verbindungssatzes von Kanten, wobei die Konstruktionskosten darauf basieren, dass die Pontons bewegt werden.

    Zweitens: Dies ist nicht der Fall das Problem des minimalen Gewichtungsspannungsbaums. Oben: Wir benötigen einen minimalen Aufbau und nicht die Ermittlung des minimalen Gewichts.

    Drittens: Es scheint, dass der konstruierte Pfad ein aufspannender Baum ist, aber nicht unbedingt ein minimales Gewicht. Die Alternative ist, dass es sich um einen Spannbaum plus einige zusätzliche Kanten handelt, die zu einem Zyklus führen. Wenn wir jedoch in einer Konfiguration ohne Kanten beginnen, hat jede Kante positive Kosten und wir können immer einen Baum mit geringerem Gewicht finden, indem Sie einfach die zusätzlichen Kanten nicht 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 Massenzentren? Irgendein innerer Punkt? (Wenn es einen externen Punkt gibt, hätten wir Null-Gewichtskonstruktionen, ja?)

    Dies ist etwas subtil, denn wenn wir uns um einen internen Punkt um 90 Grad drehen, Sagen wir, der Massenschwerpunkt, wie hoch sind die Kosten? Nichts, weil es eine Rotation ist? Eine endliche Menge, weil sich der Punkt verschoben hat? Nun 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.

    07 June 2012
    Novak
  • Nach der Zeichnung ist dies immer noch ein NPC-Problem. Selbst wenn wir das Problem reduzieren, kann jeder Ponton 1 von n Positionen (dh bekannte Verbindungslinien) einnehmen. Um die bestmögliche Antwort zu erhalten, müssten wir jeden Ponton in jeder Position ausprobieren, indem er seinen Abstand addiert, um diese entsprechenden Positionen zu erreichen Zeit und Vergleich mit allen anderen: Wenn jeder Ponton in jeder Position getestet werden muss, müssen n! -Kombinationen getestet werden.

    Ich habe mich für die Bearbeitung des ursprünglichen Posters entschieden Bilder mit einigen Ergänzungen, um die Diagrammideen für dieses Problem darzustellen.

    Das Bild unten zeigt alle (minus 2, um es einfacher zu machen) Pontons in verschiedenen Farben mit allen potenziellen Ponton-Endlagen Ich habe nur die Grenzen zwischen 3 Pontons und allen Endstandorten gezeichnet, aber man könnte sehen, wie verrückt dies wird.

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

    Sagen Sie einfach, dass der türkisfarbene Ponton als erster Schritt am nächstgelegenen Endstandort platziert wird (obwohl AB THE TSP wissen, dass dies der Fall ist) kann am Ende nicht optimal sein.

    Unten sehen wir genau das, den Ponton und die Entfernung (a.k.a. gewichtete Fahrstrecke) muss es reisen.

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

    Ab hier ein virtueller Knoten mit den beiden Endstandorten auf den gerade platzierten Standort kann gemacht werden. Die Entfernung vom gesetzten Knoten und die beiden benachbarten Knoten innerhalb des virtuellen Knotens haben eine virtuelle Fahrdistanz von 0.

    Nachfolgend sehen Sie den virtuellen Knoten, der mit ALLEN potenziellen Fahrdistanzgewichten erstellt wurde kann dort platziert werden.

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

    Sehen Sie, wie dies weitergehen würde und wie die optimalste Lösung (wie viele zu sehen sind) Mal mit dem TSP) ist es nicht immer so, dass für jede Auswahl die kürzeste Entfernung gewählt wird, wir müssten im Wesentlichen alle Pfade für alle Knoten / virtuellen Knoten testen.

    Am Ende der Der erste Knoten des (TSP) Problems könnte irgendeiner der potentiellen Endpunktpunkte sein und die Linien f

    07 June 2012
    trumpetlicks