Beweisen Sie, dass das Droid-Händler-Problem np-komplett ist

Question

Diese Frage stammt aus Kapitel 8, Übung 35, Algorithmus-Design von Kleinberg und Tardos.

Ein Spieler im Spiel steuert ein Raumschiff und versucht, Geld zu verdienen Kaufen und Verkaufen von Droiden auf verschiedenen Planeten. Es gibt $ n $ Verschiedene Arten von Droiden und $ K $ verschiedene Planeten. Jeder Planet $ P $ hat die folgenden Eigenschaften: Es gibt $ s (j, p) \ geq 0 $ Droiden von Typ $ J $ Verfügbar zum Verkauf, zu einem Festpreis von $ x (j, p) \ geq 0 $ jeweils für $ J= 1, 2, \ Punkte, n $ , und es besteht die Nachfrage nach $ d (j , p) \ geq 0 $ Droiden des Typs $ J $ , zu einem festen Preis von $ y ( j, p) \ geq 0 $ jeweils. (Wir gehen davon aus, dass ein Planet nicht gleichzeitig beide hat positive Versorgung und eine positive Nachfrage nach einem einzelnen Droid-Typ; so Für jeden $ J $ , mindestens einer der $ s (j, p) $ oder $ d (j, p) $ ist gleich $ 0 $ .)

Der Spieler beginnt auf dem Planeten $ s $ mit $ Z $ Geldeinheiten und muss enden bei Planet $ T $ ; Es gibt eine gerichtete azyklische Grafik $ g $ auf dem Set von Planeten, so dass $ S $ - $ T $ Pfade in $ G $ entsprechen gültigen Routen von der Spieler. (G wird als azyklisch gewählt, um willkürlich langes zu verhindern Spiele.) Für einen bestimmten $ s $ - $ T $ path $ P $ in $ g $ , kann der Spieler eingreifen Transaktionen wie folgt. Wann immer der Spieler bei einem Planeten ankommt $ P $ Auf dem Pfad $ P $ kann sie bis zu $ s (j, p) $ Droiden von kaufen Type $ J $ für $ x (j, p) $ Geldeinheiten jeweils (vorausgesetzt sie hat ausreichend Geld Hand) und / oder verkaufen bis $ d (j, p) $ Droiden des Typs $ J $ für $ y (j, p) $ Geldeinheiten (also gehe ich davon aus, dass Sie mehrere Kaufen / Verkäufe anstellen können jeder Planet). Die endgültige Punktzahl des Spielers ist der Gesamtbetrag von Geld Sie hat an der Hand, wenn sie bei Planet $ T $ ankommt.

Ich versuche, dieses Problem zu beweisen, ist schwieriger als ein np-vollständige Problem, aber ich bin ziemlich stecken. Da die Planeten in einem DAG organisiert sind, denke ich, dass die "Härte" des Problems von der Tatsache kommt, dass Sie an jedem Planeten viele verschiedene Arten von Droiden kaufen und verkaufen können. Dieses Problem ist auch ein Maximationsproblem, und ich kenne nicht viele np-komplette Maximierungsprobleme als die quadratische Zuordnung.

Mein Gedankenprozess ist, dass die Droiden etwas darstellen müssen, beispielsweise die Auswahl von Ecken eines Diagramms. Dann spiegelt der Preis des Droides den 'Wert' in irgendeiner Weise wider; Zum Beispiel wäre der Droid, der den Vertex $ I $ repräsentiert, einen Verkaufspreis entspricht, der dem Grad des Vertex entspricht> $ i $ zum Beispiel.

Etwas, das für mich für die letzten 30 Übungen gut funktioniert hat, sollte eine sehr einfache Version des Problems in Betracht ziehen. In diesem Fall galt ich in diesem Fall die Fälle, in denen die Planeten nur ein Liniengraph waren, oder es gibt nur zwei Arten von Droiden, oder es gibt nur zwei Arten von Droiden, oder jeder Planeten verkauft genau 1 Droid-Typ und kauft 1 Trottyp (somit können Sie den Spieler zu kaufen / verkaufen, anstatt nur an ihr Geld zu halten). Ich versuche auf diese Weise zu vereinfachen und zu sehen, ob es anfängt, anderen NP-harten Problemen zu ähneln, weshalb ich vermute, dass es eine Scheitelpunktabdeckung oder eine 3-Sat-Reduktion sein sollte.

Alle Tipps würden ersichtlich, z. B. welches Problem X sollte ich wählen, um auf das Droid-Händlerproblem zu reduzieren, oder wie sollte ich dieses Problem ansehen (z. B. 3-Sat kann als Auswählen eines von $ 2 ^ N $ Wahlmöglichkeiten und dann prüfen, ob die Auswahl einige Praktikate erfüllt)

Answer 1

Sie können eine einfache Reduktion von Rucksack oder aus dem Partitionsproblem finden (das sich selbst auf Rucksack reduziert).

lass es von der Partitionsprobleme tun:

gegeben $ n $ ganzgeräte $ s= {a_1, a_2 \ ldots, a_n \} $ Mit gleichmäßiger Gesamtsumme gibt es eine Teilmenge, deren Summe genau die Hälfte der Summe aller Elemente ist?

Angenommen, Sie erhalten eine Instanz des Partitionsproblems. Wir erstellen eine Instanz des Droid-Händlerproblems wie folgt:

.
• Es gibt $ N $ Arten von Droiden, eines für jede Ganzzahl in $ s $ . Es gibt zwei Planeten $ s $ und $ T $ , mit einer gerichteten Kante von $ s $ bis $ T $ .
• auf dem Planeten $ s $ , kann der Player einen einzelnen Droid jedes Typs $ i $ kaufen Für einen Preis von $ A_I $ , und kann nichts verkaufen.
• auf dem Planeten $ t $ , kann der Player Droiden von jedem Typ $ i $ für a verkaufen Preis für $ 2 \ CDOT A_I $ , und kann nichts kaufen.
• Der Spieler beginnt mit $ Z $ gleich der Hälfte der Summe aller Elemente in $ s $ .

Dann ist es leicht zu sehen, dass der Spieler niemals mit mehr Geld enden kann als $ \ SUM S $ . Darüber hinaus kann er $ \ SUM S $ erreichen, wenn er und nur, wenn er $ \ frac {1} {2} kaufen kann Summe S $ Droiden im ersten Planeten, dh es gibt eine Teilmenge von $ S $ mit Summe $ \ frac {1} {2} \ sum s $ .

Die ursprüngliche Frage auf der Partitions-Probleminstanz ist daher gleichwertig, ob der Player mit $ \ Sum S $ in dem entsprechenden Droid-Händler-Problem enden kann.

Da dies eine Polynom-Zeit-Reduktion ist, erweist sich dies den Anspruch.

Answer 2

Das Problem ist NP-komplett, auch wenn der Spieler eine Fraktionierzahl eines Droidens kaufen / verkaufen kann. Wir reduzieren nicht ganz gleich 3sat (nae3sat) zu dieses Problem.

Angesichts einer Instanz von nae3sat mit $ n $ variablen $ x_1, \ ldots, x_n $ und $ M $ Clauses, wir erstellen ein Diagramm wie folgt.

generasacodicetagpre.

Das ist in jedem Schritt der Player, um zu genau einem der Planeten zu gehen $ X_I ^ 0 $ und $ x_i ^ 1 $ .

Wir erstellen zwei Arten von Droiden $ d_j $ und $ d_j '$ für jede Klausel < Klasse="Math-Container"> $ J $ . Wenn Klausel $ J $ ist, z. B. $ X_1 \ Vee \ neg x_3 \ Vee X_4 $ , Dann gibt es 1 Droid vom Typ $ d_j $ in Planet $ x_1 ^ 0, x_3 ^ 1 $ für Verkauf und 1 Droid des Typs $ d_j '$ in Planet $ x_1 ^ 1, x_3 ^ 0 $ für Verkauf, und es gibt 1 Nachfrage nach Droiden des Typs $ d_j $ in Planet $ x_4 ^ 0 $ und 1 Nachfrage nach Droiden des Typs $ d_j '$ in Planet $ x_4 ^ 1 $ . Für jeden Typ ist der Preis für den Spieler zum Kauf eines Droidens immer 1, und der Preis für den Player zum Verkauf eines Droidens ist immer 2. Der Spieler hat $ M $ Geld anfangs, wo $ M $ eine sehr große Anzahl ist.

Jetzt können wir sehen, dass die Fomula eine gültige Instanz von nae3sat ist, wenn und nur, wenn der Spieler $ M + M $ Geld aufnehmen kann, wenn sie bei $ t $ .

Übrigens zeigt diese Reduktion, dass Ihr Problem, egal ob der Spieler eine Fraktionierzahl eines Droidens kaufen / verkaufen kann, ist stark np-komplett .