Warum ist Dantzigs Lösung des Rucksackproblems nur ungefähr

Für eine Reihe von Artikeln mit Werten v ich und Gewichte w ich , und mit einem Gesamtgewicht W die unsere Tasche tragen kann, wie erreichen wir den maximalen Gesamtwert, ohne die Tasche zu beschädigen? Dantzig schlug vor, dass wir das Verhältnis betrachten v ich / w J , und fügen Sie Artikel hinzu, für die dieses Verhältnis am größten ist, bis der Beutel voll ist. Dies wird jedoch als Näherungslösung angesehen.

Über dieses Problem habe ich auch schon nachgedacht. Ich bin auf die gleiche Lösung wie Dantzig gekommen und habe sie sogar für die bewiesen 0 − 1 Problem. Natürlich war ich meinem Beweis gegenüber misstrauisch, noch bevor ich wusste, dass die Methode schon einmal vorgeschlagen worden war (da dies implizieren würde P = N P ). Ich bin jetzt noch misstrauischer.

Also erlöse mich von meinem Elend. Warum funktioniert es nicht?

Nun, wie würden Sie beweisen, dass diese Methode in einer allgemeinen Umgebung die beste ist?
Diese Methode hilft nicht, wenn v ich = w ich für alle ich − es heißt im Wesentlichen, Gegenstände nach dem Zufallsprinzip auswählen. Dieser Widerspruch gilt für die 0 − 1 Problem ebenso. Kann also nicht stimmen!

Antworten (2)

Es geht nicht, weil es nicht geht.

Sagen Sie, Sie haben W = 10 und es gibt drei Arten von Objekten:

  1. Typ A hat das Gewicht 9 und den Wert 90.
  2. Typ B hat Gewicht 2 und Wert 19.
  3. Typ C hat Gewicht 1 und Wert 1.

Wenn Sie sich ansehen v / w , Typ A gewinnt, also nehmen Sie einen Typ A Objekt und füllen Sie den verbleibenden Platz mit einem Typ auf C , für den Gesamtwert 91 .

Aber die optimale Lösung braucht fünf Typen B Objekte für den Gesamtwert 95 .

Wir könnten die allgemeine Schwierigkeit wie folgt charakterisieren: Eine Wahl, die anfangs gut schien, geriet später in Schwierigkeiten, weil unsere frühe Wahl von A , kurzfristig optimal, zwingt uns, das sehr Schlechte zu nehmen C nachher. Die optimale Lösung erfordert viele Entscheidungen, die auf kurze Sicht suboptimal erscheinen, aber gut zusammenarbeiten.

Dies ist ziemlich typisch für NP-vollständige Probleme. Sie haben viele Teile, die auf komplizierte Weise interagieren, sodass die Auswirkungen einer bestimmten Entscheidung in einem Teil des Problems nicht lokalisiert werden können, aber weitreichende Auswirkungen auf Entscheidungen haben, die an anderer Stelle getroffen werden. Vergleichen Sie dies mit dem prototypischen NP-vollständigen Problem CNF-SAT, bei dem die Teile logische Klauseln sind, die jeweils mehrere Komponenten enthalten, aber jede Komponente in mehreren Klauseln vorkommen kann. Jede Entscheidung über den Wert einer Komponente einer Klausel kann weitreichende Auswirkungen auf die anderen Klauseln haben.

Oder ziehen Sie in ähnlicher Weise das Packen in die Tonne in Betracht. Artikel, die optimal in den ersten Behälter passen, können sich als genau das herausstellen, was benötigt wird, um den Platz in späteren Behältern auszufüllen, so dass eine optimale Verpackung des ersten Behälters einen kurzfristigen Gewinn auf Kosten der Gesamtverpackung erzielen kann; Eine insgesamt optimale Lösung kann den ersten Behälter suboptimal packen, um bestimmte Sonderposten für später aufzubewahren.

Für die 0 − 1 Problem scheint es mir, dass die Wahl A ist optimal. Ich denke, ich sollte versuchen, ein Gegenbeispiel zu finden, das in der funktioniert 0 − 1 Fall aber.
@Matthew Ist das 0 − 1 Fall der Fall, in dem Sie höchstens einen von jedem Gegenstand nehmen können? Wenn ja, Split-Typ B in Typen B 1 … B 5 jeweils mit Gewicht 2 und Wert 19, oder wenn Sie möchten, dass sie unterschiedlich sind, geben Sie B ich Gewicht 2 − ϵ ich und Wert 19 + ϵ ich .
Das ist großartig. Danke. Ich glaube, ich habe meinen fehlerhaften Schritt identifiziert. Ich denke, es gibt die optimale Lösung, wenn es genau das gebundene Gewicht erhält, und nicht anders.
@MatthewMatic: Wenn Sie daran interessiert sind, einen Rucksacklöser zu implementieren, lesen Sie diesen Beitrag: codereview.stackexchange.com/questions/44421/…
@Matthew Ich glaube nicht. Es ist leicht, mich zu stören A , B ich , C Beispiel zu einem, bei dem die optimale Lösung genau das gebundene Gewicht erhält. Stellen Sie das einfach sicher ∑ ϵ ich = 0 .
@MJD Ich meine, wenn die Methode das gebundene Gewicht erhält, ist sie optimal. Nicht, dass, wenn die optimale Lösung das gebundene Gewicht erhält, dieses Verfahren es finden wird.
Ich glaube auch nicht, dass das stimmt. Im 0-1-Fall mit W = 10 betrachte A mit (Gewicht 6, Wert 60), B und C beide mit (Gewicht 5, Wert 49) und D, E, F, G alle mit (Gewicht 1, Wert 1) Ihre Methode wählt zuerst A (mit v / w = 10), dann passen B und C nicht, und dann wählt sie D, E, F und G, um die Gewichtsgrenze genau zu erfüllen, mit einem Gesamtwert von 64; während die optimale Lösung B+C mit dem Gesamtwert 98 ist.

Nur zur Verdeutlichung: Wenn Sie Artikel nach ihrem Wert/Gewicht-Verhältnis auffüllen, bis kein Artikel mehr in dieser Reihenfolge passt, ist das Ergebnis optimal , wenn das bis dahin aufgelaufene Gewicht genau dem verfügbaren Platz entspricht. Mit anderen Worten, es ist IMMER optimal für das angesammelte Gesamtgewicht. Ich denke, das ist das Ergebnis, das Sie im Sinn hatten. Es ist nicht schwer zu beweisen und findet sich in jeder Einführung in Rucksackprobleme, zum Beispiel in "Martello, S. & Toth, P. Knapsack problems: algorithms and computer implements. John Wiley & Sons, 1990"

Wie in der ersten Antwort und den dortigen Kommentaren besprochen, ist Ihre Methode jedoch offensichtlich nicht immer optimal, wenn sie endet, ohne den Beutel vollständig zu füllen. Denk an W = 10 N für groß N , und Gegenstände A (Gewicht 1 , Wert 1 ) B (Gewicht 10 N , Wert 10 N − 1 ). Dann landet Ihr Algorithmus bei A und einen Wert von 1 , wenn es stattdessen hätte haben können B mit einem Wert von 10 N − 1 . Nichtsdestotrotz, A ist trivial optimal für das erreichte Gewicht, also optimal für einen Tornister mit Gesamtgewicht 1 .

Diese Antwort kann irreführend sein? Betrachten Sie den im @MJD-Post erwähnten Fall. Wenn Sie die Elemente gierig gemäß ihrem v / w für W = 12 füllen, erhalten Sie am Ende [A, B, C] für einen Wert von 110, während 6xB einen Wert von 114 ergibt.
@JeroenVuurens das widerspricht nicht dem, was ich in der Antwort sage. Beachten Sie, dass ich sage "bis kein Artikel mehr in diese Bestellung passt". Angenommen, es gibt mehrere Elemente des Typs B, da Sie über ein Szenario sprechen, in dem mehrere B-Elemente verwendet werden, deckt meine Antwort nicht die Situation ab, in der Sie mit dem Einfügen von C beginnen. Wenn Sie eine Idee haben, wie Sie die Aussage klarer ausdrücken können, l Ich werde meine Antwort gerne bearbeiten, aber der mathematische Inhalt ist korrekt, so wie er jetzt ist
@JeroenVuurens Wenn Sie mir zustimmen, können Sie meine Antwort positiv bewerten, um anderen Vertrauen in die Aussage dahinter zu geben. Ich fand es sehr beunruhigend, dass die vorhandene Antwort nur ein negatives Ergebnis liefert, obwohl die Realität ist, dass das gierige Packen in den meisten Fällen gut funktioniert (und meine Antwort zeigt, warum).
immer noch nicht einverstanden. Im angegebenen Beispiel für W=12 ergibt die Sortierung der Elementtypen nach v/w [ A, B, C ] (oder [A, B, B, B, B, B, B, C], wenn Sie auf 0 bestehen /1 Zuweisung). Wenn ich Sie also richtig verstehe, behaupten Sie, dass der Algorithmus optimal ist, wenn wir Artikel gierig auffüllen, wenn wir mit Artikel A beginnen, weil dieser das höchste v / w hat, bevor wir zum nächsten übergehen. In diesem Beispiel füllt das den Rucksack mit ABC, während BBBBBB besser ist.
@JeroenVuurens In meinem Beitrag heißt es: "Artikel entsprechend ihrem Wert / Gewichtsverhältnis auffüllen, bis Sie keinen weiteren Artikel mehr in diese Bestellung aufnehmen können". Daher würden Sie damit beginnen, A einzubeziehen, weil es das beste v/w hat und passt. Dann würden Sie B einschließen, weil es das beste v/w der verbleibenden Elemente hat und auch passt. Danach hat das nächste B das beste v/w, aber da es nicht passt, hörst du auf. Sie erhalten am Ende [A,B], das die Gewichtung 11 und den Wert 109 hat. Keine andere Kombination mit Gewichtung ≤ 11 hat einen besseren Wert
Warum ist Dantzigs Lösung des Rucksackproblems nur ungefähr
AntwortenHierDatenschutz-Bestimmungen1y, 0v