Rucksackproblem

Beispiel für ein eindimensionales (Einschränkung) Rucksackproblem: Welche Boxen sollten ausgewählt werden, um den Geldbetrag zu maximieren und gleichzeitig das Gesamtgewicht unter oder gleich 15 kg zu halten? EIN Mehrfach eingeschränktes Problem Könnte sowohl das Gewicht als auch das Volumen der Kisten berücksichtigen.
(Lösung: Wenn eine Anzahl jeder Box verfügbar ist, dann sind drei gelbe Kisten und drei graue Kästchen; wenn nur die angezeigten Kästchen verfügbar sind, dann alle mit Ausnahme der grünen Box.)

Das Rucksackproblem ist ein Problem in Kombinatorische Optimierung: Bestimmen Sie bei einem Satz von Elementen mit jeweils einem Gewicht und einem Wert die Anzahl jedes Elements, das in eine Sammlung einbezogen werden soll, damit das Gesamtgewicht geringer oder gleich einer bestimmten Grenze ist und der Gesamtwert so groß wie möglich ist. Es leitet seinen Namen aus dem Problem, mit dem jemand konfrontiert ist, der durch eine feste Größe eingeschränkt wird Tornister und muss es mit den wertvollsten Gegenständen füllen. Das Problem tritt oft auf Ressourcenzuweisung wo die Entscheidungsträger aus einer Reihe von nicht-aufmerksamen Projekten oder Aufgaben unter einem festen Budget oder einer zeitlichen Einschränkung wählen müssen.

Das Rucksack -Problem wird seit mehr als einem Jahrhundert mit frühen Arbeiten aus dem Jahr 1897 untersucht.[1] Der Name "Rucksack Problem" stammt aus den frühen Werken des Mathematikers Tobias Dantzig (1884–1956),[2] und bezieht sich auf das alltägliche Problem des Verpackens der wertvollsten oder nützlichsten Gegenstände, ohne das Gepäck zu überladen.

Anwendungen

Rucksackprobleme treten in realen Entscheidungsprozessen in einer Vielzahl von Feldern auf, z.[3] Auswahl von Investitionen und Portfolios,[4] Auswahl an Vermögenswerten für Verbriefung von Asset-Backed,[5] und Schlüssel für die Erzeugung für die Merkle -Hellman[6] und andere Knapsack Cryptosystems.

Eine frühe Anwendung von Rucksack-Algorithmen war in der Konstruktion und Bewertung von Tests, bei denen die Testteilnehmer die Wahl haben, welche Fragen sie beantworten. Für kleine Beispiele ist es ein ziemlich einfacher Prozess, den Testteilnehmern eine solche Wahl zu bieten. Wenn beispielsweise eine Prüfung jeweils 12 Fragen im Wert von 10 Punkten enthält, muss der Testteilnehmer nur 10 Fragen beantworten, um eine maximal mögliche Punktzahl von 100 Punkten zu erzielen. Bei Tests mit einer heterogenen Verteilung der Punktwerte ist es jedoch schwieriger, Entscheidungen zu treffen. Feuerman und Weiss schlugen ein System vor, in dem die Schüler einen heterogenen Test mit insgesamt 125 möglichen Punkten erhalten. Die Schüler werden gebeten, alle Fragen nach besten Kräften zu beantworten. Von den möglichen Untergruppen von Problemen, deren Gesamtpunktwerte bis zu 100 addieren, würde ein Rucksackalgorithmus bestimmen, welcher Untergruppe jedem Schüler die höchstmögliche Punktzahl verleiht.[7]

Eine 1999er Studie des Algorithmus -Repositorys der Stony Brook University zeigte, dass das Rucksackproblem von 75 algorithmischen Problemen das 19. am beliebteste und der drittreichste benötigte danach war Suffixbäume und die Packungsproblem.[8]

Definition

Das häufigste Problem, das gelöst wird, ist das 0-1 Rucksack Problem, was die Anzahl einschränkt von Kopien jeder Art von Gegenstand auf Null oder eins. Bei einem Satz von einem Satz von Artikel von 1 bis zu , jeweils mit einem Gewicht und ein Wert zusammen mit einer maximalen Gewichtskapazität Anwesend

maximieren
vorbehaltlich und .

Hier repräsentiert die Anzahl der Elementinstanzen in den Rucksack einbeziehen. Informell besteht das Problem darin, die Summe der Werte der Elemente im Rucksack so zu maximieren, dass die Summe der Gewichte kleiner oder gleich der Kapazität des Rucksacks ist.

Das Begrenzter Rucksackproblem (BKP) Entfernt die Einschränkung, dass es nur eines von jedem Element gibt, aber die Nummer einschränkt von Kopien jeder Art von Gegenstand zu einem maximalen nicht negativen Ganzzahlwert :

maximieren
vorbehaltlich und

Das Unbegrenztes Rucksackproblem (UKP) platziert keine Obergrenze auf die Anzahl der Kopien jeder Art von Gegenstand und kann wie oben formuliert werden, außer dass die einzige Einschränkung auf ist, dass es eine nicht negative Ganzzahl ist.

maximieren
vorbehaltlich und

Ein Beispiel für das unbegrenzte Rucksack -Problem wird unter Verwendung der am Anfang dieses Artikels gezeigten Abbildung und des Textes "Wenn eine beliebige Anzahl jedes Feldes verfügbar ist" in der Bildunterschrift dieser Abbildung angegeben.

Rechenkomplexität

Das Rucksack -Problem ist aus vielen Gründen aus der Perspektive der Informatik interessant:

  • Das Entscheidungsproblem Form des Rucksackproblems (Kann zumindest einen Wert von V erreicht werden, ohne das Gewicht zu überschreiten W?) ist NP-CompleteDaher ist in allen Fällen kein korrekter und schneller (Polynomzeit) bekannt.
  • Während das Entscheidungsproblem NP-Complete ist, ist das Optimierungsproblem nicht, seine Lösung ist mindestens so schwierig wie das Entscheidungsproblem, und es gibt keinen bekannten Polynomalgorithmus, der angesichts einer Lösung feststellen kann, ob es optimal ist (was bedeuten würde (was bedeuten würde (was bedeuten würde dass es keine Lösung mit einer größeren gibt Vdamit das NP-Vervollständigenentscheidungsproblem).
  • Da ist ein Pseudopolynomzeit Algorithmus verwendet Dynamische Programmierung.
  • Da ist ein Vollständige polynomiale Zeitnäherungsschema, der den pseudopolynomialen Zeitalgorithmus als Unterroutine verwendet, die unten beschrieben wird.
  • In vielen Fällen, die in der Praxis entstehen, und "zufällige Instanzen" aus einigen Verteilungen können dennoch genau gelöst werden.

Es gibt einen Zusammenhang zwischen den Problemen "Entscheidung" und "Optimierung", bei denen ein Polynomalgorithmus, der das Problem "Entscheidung" löst Erhöhen Sie den Wert von k. Wenn ein Algorithmus dagegen den optimalen Wert des Optimierungsproblems in der Polynomzeit findet, kann das Entscheidungsproblem in der Polynomzeit gelöst werden, indem der Wert der Lösungsausgabe durch diesen Algorithmus mit dem Wert von k verglichen werden. Somit sind beide Versionen des Problems von ähnlicher Schwierigkeit.

Ein Thema in der Forschungsliteratur ist es zu identifizieren, wie die "harten" Instanzen des Rucksackproblems aussehen.[9][10] oder einen anderen Weg betrachten, um zu ermitteln, welche Eigenschaften von Instanzen in der Praxis sie möglicherweise besser machen können, als ihr schlechtes Verhalten von NP-Case-Case-Case-Verhaltensweisen vorschlägt.[11] Das Ziel, diese "harten" Instanzen zu finden, ist für ihre Verwendung in öffentliche Schlüsselkryptographie Systeme wie die Merkle-Hellman Knapsack Cryptosystem.

Bemerkenswert ist die Tatsache, dass die Härte des Rucksackproblems von der Form der Eingabe abhängt. Wenn die Gewichte und Gewinne als Ganzzahlen vergeben werden, ist es Schwach NP-Complete, während es ist stark NP-Complete Wenn die Gewichte und Gewinne als rationale Zahlen angegeben werden.[12] Im Fall von rationalen Gewichten und Gewinnen gibt es jedoch immer noch a Vollständige polynomiale Zeitnäherungsschema.

Lösung

Es stehen mehrere Algorithmen zur Verfügung, um Rucksackprobleme zu lösen, basierend auf dem dynamischen Programmieransatz.[13] das Zweig und gebunden sich nähern[14] oder Hybridisierungen von beiden Ansätzen.[11][15][16][17]

Dynamischer Programmieralgorithmus

Das Unbegrenztes Rucksackproblem (UKP) Legt keine Einschränkung auf die Anzahl der Kopien jeder Art von Gegenstand ein. Außerdem nehmen wir hier an

vorbehaltlich und

Beobachten Sie das hat die folgenden Eigenschaften:

1. (Die Summe von Nullpunkten, d. H. Die Summierung des leeren Satzes).

2. Anwesend , wo ist der Wert der -Die Art von Gegenstand.

Die zweite Eigenschaft muss ausführlich erläutert werden. Wie erhalten wir während des Verfahrens dieser Methode das Gewicht? ? Es sind nur Wege und die vorherigen Gewichte sind wo es total gibt Arten unterschiedlicher Gegenstände (unter anderem meinen wir, dass das Gewicht und der Wert nicht vollständig gleich sind). Wenn wir jeden Wert davon kennen Elemente und der damit verbundene Maximalwert zuvor vergleichen wir sie nur miteinander und erhalten letztendlich den Maximalwert und sind fertig.

Hier wird das Maximum des leeren Satzes als Null angesehen. Tabulierung der Ergebnisse von nach oben durch gibt die Lösung. Seit der Berechnung von jedem beinhaltet höchstens untersucht Artikel, und es gibt höchstens Werte von Zur Berechnung ist die Laufzeit der dynamischen Programmierlösung . Dividieren durch ihre größter gemeinsamer Teiler ist eine Möglichkeit, die Laufzeit zu verbessern.

Selbst wenn P ≠ np, das Komplexität widerspricht nicht der Tatsache, dass das Problem der Rucksack lautet NP-Complete, seit , nicht wie , ist nicht polynomisch in der Länge des Eingangs zum Problem. Die Länge der Länge der Die Eingabe des Problems ist proportional zur Anzahl der Bits in , , nicht zu selbst. Da diese Laufzeit jedoch ist PseudopolynomDies macht die (Entscheidungsversion des) Rucksackproblems a schwach NP-Complete-Problem.

0-1 Rucksack Problem

A demonstration of the dynamic programming approach.
Eine Demonstration des dynamischen Programmieransatzes.

Eine ähnliche dynamische Programmierlösung für das 0-1-Rucksack-Problem läuft auch in der pseudopolynomialen Zeit. Davon ausgehen sind streng positive Ganzzahlen. Definieren Um der Höchstwert zu sein, der mit Gewicht weniger als oder gleich erreicht werden kann Verwenden von Elementen bis zu (Erste Artikel).

Wir können definieren rekursiv wie folgt: (Definition a)

  • wenn (Der neue Artikel ist mehr als die aktuelle Gewichtsgrenze)
  • wenn .

Die Lösung kann dann durch Berechnung gefunden werden . Um dies effizient zu tun, können wir eine Tabelle verwenden, um frühere Berechnungen zu speichern.

Das Folgende ist Pseudocode für das dynamische Programm:

// Eingabe: // Werte (in Array V gespeichert) // Gewichte (in Array w) gespeichert) // Anzahl verschiedener Elemente (n) // Rucksack -Kapazität (W) // Hinweis: Das Array "V" und das Array "W" wird angenommen, um alle relevanten Werte ab Index 1 zu speichern.  Array m[0..n, 0..W]; zum j aus 0 zu W tun:   m[0, j] : = 0 zum i aus 1 zu n tun:   m[i, 0] : = 0  zum i aus 1 zu n tun:   zum j aus 0 zu W tun:   wenn w[i] > j dann:   m[i, j] : = m[i-1, j]   anders:   m[i, j] : = Max(m[i-1, j], m[i-1, j-w[i]] + v[i])) 

Diese Lösung läuft daher ein Zeit und Platz. (Wenn wir nur den Wert m [n, w] benötigen, können wir den Code so ändern, dass die erforderliche Menge an Speicher o (w) ist, der die jüngsten zwei Zeilen des Arrays "m" speichert.)

Wenn wir jedoch noch ein oder zwei Schritte weiter gehen, sollten wir wissen, dass die Methode in der Zeit zwischen den Zeiten laufen wird und . Aus Definition aWir wissen, dass nicht alle Gewichte berechnet werden müssen, wenn die Anzahl der Elemente und die von uns ausgewählten Elemente festgelegt sind. Das heißt, das obige Programm berechnet mehr als notwendig, da sich das Gewicht von 0 zu W häufig ändert. Aus dieser Perspektive können wir diese Methode so programmieren, dass sie rekursiv ausgeführt wird.

// Eingabe: // Werte (in Array V gespeichert) // Gewichte (in Array w) gespeichert) // Anzahl verschiedener Elemente (n) // Rucksack -Kapazität (W) // Hinweis: Das Array "V" und das Array "W" wird angenommen, um alle relevanten Werte ab Index 1 zu speichern.  Definieren Wert[n, W]  Initialisieren alle Wert[i, j] = -1  Definieren m:=(i,j)  // Funktion m definieren, damit sie den Maximalwert darstellt, den wir unter der Bedingung erhalten können: Verwenden Sie zuerst i Elemente, die Gesamtgewichtsbegrenzung ist J. {   wenn i == 0 oder j <= 0 dann:   Wert[i, j] = 0   Rückkehr    wenn (Wert[i-1, j] == -1) dann:  // m [i-1, j] wurde nicht berechnet, wir müssen die Funktion m aufrufen   Wert[i-1, j] = m(i-1, j)    wenn w[i] > j dann:  // Artikel kann nicht in die Tasche passen   Wert[i, j] = Wert[i-1, j]   anders:    wenn (Wert[i-1, j-w[i]] == -1) dann:  // m [i-1, j-w [i]] wurde nicht berechnet, wir müssen die Funktion m aufrufen   Wert[i-1, j-w[i]] = m(i-1, j-w[i]))   Wert[i, j] = Max(Wert[i-1,j], Wert[i-1, j-w[i]] + v[i])) }  Laufen m(n, W) 

Zum Beispiel gibt es 10 verschiedene Elemente und die Gewichtsgrenze beträgt 67. Also,

Wenn Sie die obige Methode verwenden, um für zu berechnen Sie werden dies bekommen, ohne Anrufe auszuschließen, die Produkte produzieren :

Außerdem können wir die Rekursion brechen und sie in einen Baum umwandeln. Dann können wir einige Blätter schneiden und parallele Computing verwenden, um das Ausführen dieser Methode zu beschleunigen.

Um die tatsächliche Teilmenge der Elemente und nicht nur ihren Gesamtwert zu finden, können wir diese nach Ausführen der obigen Funktion ausführen:

/**  * Gibt die Indizes der Elemente des optimalen Rucksacks zurück.  * I: Wir können Artikel 1 bis I in den Rucksack einfügen  * J: Maximales Gewicht des Rucksacks  */ Funktion Tornister(i: int, j: int): Satz<int> {   wenn i == 0 dann:   Rückkehr {}   wenn m[i, j] > m[i-1, j] dann:   Rückkehr {i}  Tornister(i-1, j-w[i]))   anders:   Rückkehr Tornister(i-1, j) }  Tornister(n, W) 

In der Mitte treffen

Ein weiterer Algorithmus für 0-1 Rucksack, der 1974 entdeckt wurde[18] und manchmal als "Meet-in-the-Middle" bezeichnet Ein ähnlich benannter Algorithmus in der Kryptographie, ist exponentiell in der Anzahl verschiedener Elemente, kann dem DP -Algorithmus jedoch vorzuziehen sein, wenn ist groß im Vergleich zu n. Insbesondere wenn die sind nichtnegative, aber nicht von Ganzzahlen, wir könnten den dynamischen Programmieralgorithmus durch Skalierung und Rundung verwenden (d. H. Verwenden Fixpunktarithmetik), aber wenn das Problem erfordert Bruchteilige Ziffern der Präzision, um zur richtigen Antwort zu gelangen, muss skaliert werden von und der DP -Algorithmus erfordert Raum und Zeit.

Algorithmus In der Mitte treffen ist  Eingang: Eine Reihe von Elementen mit Gewichten und Werten. Ausgang: Der größte kombinierte Wert einer Untergruppe. Partition der Set {1 ...n} in zwei Sätze A und B von ungefähr gleicher Größe berechnen die Gewichte und Werte aller Teilmengen jedes Satzes für jeden Teilmenge von A tun         Finden Sie die Teilmenge von B vom größten Wert, so dass das kombinierte Gewicht geringer ist als W     Behalten Sie den bisher gesehenen kombinierten Wert im Auge

Der Algorithmus nimmt Raum- und effiziente Implementierungen von Schritt 3 (z. B. Sortieren der Untergruppen von B nach Gewicht, Abwerfen von Teilmengen von B, die mehr als andere Teilmengen von B mit größerem oder gleichem Wert wiegen Eine Laufzeit von . Wie mit dem sich im mittleren Angriff treffen In der Kryptographie verbessert sich dies der Laufzeit eines naiven Brute Force -Ansatzes (untersucht alle Teilmengen von ), auf Kosten der Verwendung exponentieller als konstanter Raum (siehe auch Baby-Schritt-Riesenschritt).

Näherungsalgorithmen

Bei den meisten Problemen mit NP-Vervollständigung kann es ausreichen, praktikable Lösungen zu finden, auch wenn sie nicht optimal sind. Vorzugsweise ist die Näherung jedoch mit einer Garantie für den Differenz zwischen dem Wert der gefundenen Lösung und dem Wert der optimalen Lösung geliefert.

Wie bei vielen nützlichen, aber rechenintensiv komplexen Algorithmen wurden erhebliche Untersuchungen zur Erstellung und Analyse von Algorithmen durchgeführt, die eine Lösung annähern. Das Rucksackproblem ist zwar NP-Hard, aber eine Sammlung von Algorithmen, die immer noch auf jeden bestimmten Grad angenähert werden können. Dies bedeutet, dass das Problem ein Polynomzeitnäherungsschema aufweist. Um genau zu sein, hat das Rucksackproblem a Vollständige polynomiale Zeitnäherungsschema (FPTAs).[19]

Gieriger Näherungsalgorithmus

George Dantzig vorgeschlagen a gierig Näherungsalgorithmus um das unbegrenzte Rucksackproblem zu lösen.[20] Seine Version sortiert die Elemente in abnehmender Wertreihenfolge pro Gewichtseinheit, . Anschließend wird sie in den Sack eingefügt, beginnend mit möglichst vielen Kopien der ersten Art von Gegenstand, bis mehr Platz mehr im Sack für mehr enthalten ist. Vorausgesetzt, es gibt eine unbegrenzte Versorgung jeder Art von Artikel, wenn ist der maximale Wert der Artikel, die in den Sack passen, und dann wird der gierige Algorithmus garantiert mindestens einen Wert von erreichen .

Für das begrenzte Problem, bei dem die Versorgung jeder Art von Gegenstand begrenzt ist, kann der obige Algorithmus alles andere als optimal sein. Eine einfache Änderung ermöglicht es uns jedoch, diesen Fall zu lösen: Angenommen, alle Elemente passen individuell in den Sack ( für alle ). Eine Lösung konstruieren Durch das packen so lange wie möglich gierige Gegenstände, d.h. wo . Konstruieren Sie außerdem eine zweite Lösung mit dem ersten Element, der nicht passte, enthielt. Seit Bietet eine Obergrenze für die LP -Entspannung Von dem Problem muss einer der Sätze zumindest einen Wert haben ; Wir geben also zurück, was auch immer von und hat einen besseren Wert, um a zu erhalten -Annäherung.

Es kann gezeigt werden, dass die durchschnittliche Leistung mit der Fehlerrate auf die optimale Lösung in der Verteilung konvergiert [21]

Vollständige polynomiale Zeitnäherungsschema

Das Vollständige polynomiale Zeitnäherungsschema (FPTAs) Für das Rucksack -Problem nutzt das Problem die Tatsache, dass der Grund, warum das Problem keine Polynomzeitlösungen hat, darin besteht, dass die mit den Elementen verbundenen Gewinne nicht eingeschränkt sind. Wenn man einige der am wenigsten signifikanten Ziffern der Gewinnwerte abrundet, werden sie durch ein Polynom und 1/ε begrenzt, wobei ε eine gebundene Richtigkeit der Lösung ist. Diese Einschränkung bedeutet dann, dass ein Algorithmus in Polynomzeit eine Lösung finden kann, die innerhalb eines Faktors (1-ε) der optimalen Lösung korrekt ist.[19]

Algorithmus Fptas ist   Eingang: ε ∈ (0,1] A List a von n Elementen, angegeben durch ihre Werte, und Gewichte Ausgang: S 'Die FPTAS -Lösung P: = max   // der höchste Artikelwert k: = ε   zum i aus 1 zu n tun  : =   Ende für  Rückkehr die Lösung, s ', verwendet die  Werte im oben beschriebenen dynamischen Programm

Satz: Der Satz Berechnet durch den oben genannten Algorithmus , wo ist eine optimale Lösung.

Dominanzbeziehungen

Das Lösen des unbegrenzten Rucksackproblems kann erleichtert werden, indem Gegenstände wegwerfen, die niemals benötigt werden. Für einen bestimmten Artikel Angenommen, wir könnten eine Reihe von Gegenständen finden so dass ihr Gesamtgewicht geringer ist als das Gewicht von und ihr Gesamtwert ist größer als der Wert von . Dann kann nicht in der optimalen Lösung erscheinen, da wir immer eine potenzielle Lösung verbessern können Durch Ersetzen mit dem Set . Daher können wir die außer Acht lassen -D -Elements insgesamt. In solchen Fällen, wird gesagt zu dominieren . (Beachten Sie, dass dies nicht für Problemen mit begrenzten Rucksack gilt, da wir die Elemente in möglicherweise bereits verbraucht haben .))

Das Finden von Dominanzbeziehungen ermöglicht es uns, die Größe des Suchraums erheblich zu reduzieren. Es gibt verschiedene Arten von Dominanzbeziehungen,[11] die alle eine Ungleichheit der Form befriedigen:

, und für einige

wo und . Der Vektor bezeichnet die Anzahl der Kopien jedes Mitglieds von .

Kollektive Dominanz
Das -D -Element ist gemeinsam dominiert durch , geschrieben als , wenn das Gesamtgewicht einer Kombination von Gegenständen in ist weniger als wi und ihr Gesamtwert ist größer als vi. Formal, und für einige , d.h. . Die Überprüfung dieser Dominanz ist rechnerisch schwer, damit sie nur mit einem dynamischen Programmieransatz verwendet werden kann. Tatsächlich entspricht dies der Lösung eines kleineren Rucksack -Entscheidungsproblems, wo , , und die Gegenstände sind beschränkt auf .
Schwellenwertdominanz
Das -D -Element ist Schwellenwert dominiert durch , geschrieben als , wenn eine Reihe von Kopien von werden dominiert von . Formal, , und für einige und . Dies ist eine Verallgemeinerung der kollektiven Dominanz, die erstmals eingeführt wurde[13] und im EDUK -Algorithmus verwendet. Das kleinste definiert die Schwelle des Gegenstandes , geschrieben . In diesem Fall könnte die optimale Lösung höchstens enthalten Kopien von .
Mehrfachdominanz
Das -D -Element ist multiplizieren dominiert durch einen einzelnen Artikel , geschrieben als , wenn wird von einigen Kopien von dominiert . Formal, , und für einige d.h. . Diese Dominanz könnte während der Vorverarbeitung effizient eingesetzt werden, da sie relativ leicht erkannt werden kann.
Modulare Dominanz
Lassen sei der Bester Artikel, d.h. für alle . Dies ist der Gegenstand mit der größten Wertdichte. Das -D -Element ist modular dominiert durch einen einzelnen Artikel , geschrieben als , wenn wird dominiert von plus mehrere Kopien von . Formal, , und d.h. .

Variationen

Es gibt viele Variationen des Rucksackproblems, die sich aus der großen Anzahl von Anwendungen des Grundproblems entstanden. Die Hauptschwankungen treten auf, indem die Anzahl eines Problemparameters wie die Anzahl der Elemente, die Anzahl der Ziele oder sogar die Anzahl der Rucksäcke geändert wird.

Multi-Objektiv-Rucksackproblem

Diese Variation verändert das Ziel der Person, die den Rucksack füllt. Anstelle eines Ziels, wie z. B. die Maximierung des Geldgewinns, könnte das Ziel mehrere Dimensionen haben. Zum Beispiel kann es sowohl umweltbezogene oder soziale Bedenken sowie wirtschaftliche Ziele geben. Zu den häufig behandelten Problemen gehören Portfolio- und Transportlogistikoptimierungen.[22][23]

Angenommen, Sie haben ein Kreuzfahrtschiff geführt. Sie müssen entscheiden, wie viele berühmte Comedians eingestellt werden sollen. Dieses Boot kann nicht mehr als eine Tonne Passagiere bewältigen und die Entertainer müssen weniger als 1000 Pfund wiegen. Jeder Komiker hat ein Gewicht, bringt basierend auf seiner Popularität ein Geschäft und fragt nach einem bestimmten Gehalt. In diesem Beispiel haben Sie mehrere Ziele. Sie möchten natürlich die Popularität Ihrer Entertainer maximieren und gleichzeitig ihre Gehälter minimieren. Außerdem möchten Sie so viele Entertainer wie möglich haben.

Mehrdimensionales Rucksackproblem

In dieser Variation das Gewicht des Rucksack -Elements wird durch einen d-dimensionalen Vektor gegeben und der Rucksack hat einen dimensionalen Kapazitätsvektor . Das Ziel besteht darin, die Summe der Werte der Elemente im Rucksack so zu maximieren, dass die Summe der Gewichte in jeder Dimension überschreitet nicht .

Mehrdimensionaler Rucksack ist rechnerisch härter als Rucksack. sogar für Das Problem hat nicht EPTAs es sei denn pNp.[24] Der Algorithmus in[25] wird gezeigt, um spärliche Instanzen effizient zu lösen. Eine Instanz mehrdimensionaler Rucksack ist spärlich, wenn es einen Satz gibt zum so dass für jeden Rucksackartikel , so dass und . Solche Fälle treten beispielsweise bei der Planung von Paketen in einem drahtlosen Netzwerk mit Relaisknoten auf.[25] Der Algorithmus von[25] Löst auch spärliche Instanzen der Multi-Choice-Variante, mehrfache mehrdimensionaler Rucksack.

Der IHS-Algorithmus (Zunahme der Höhenschelf) ist für 2D-Rucksack optimal (Verpackungsquadrate in ein zweidimensionales Quadrat der Einheit): Wenn es höchstens fünf Quadrate in einer optimalen Packung gibt.[26]

Multiple Rucksack Problem

Diese Variation ähnelt der Packungsproblem. Es unterscheidet sich von dem Stellverpackungsproblem darin, dass eine Teilmenge von Elementen ausgewählt werden kann, während im Stellverpackungsproblem alle Elemente in bestimmte Behälter gepackt werden müssen. Das Konzept ist, dass es mehrere Rucksäcke gibt. Dies mag wie eine triviale Veränderung erscheinen, aber es ist nicht gleichwertig der Kapazität des Anfangsracks. Diese Variation wird in vielen Lade- und Planungsproblemen in der Operationsforschung verwendet und hat a Polynom-Zeit-Approximationsschema.[27]

Quadratische Rucksackproblem

Das quadratische Rucksackproblem maximiert eine quadratische Objektivfunktion, die binäre und lineare Kapazitätsbeschränkungen unterliegt.[28] Das Problem wurde 1980 von Gallo, Hammer und Simeone eingeführt.[29] Die erste Behandlung des Problems stammt jedoch 1975 auf Witzgall.[30]

Subset-Sum-Problem

Das Summenproblem ist ein Sonderfall der Entscheidung und 0-1 Probleme, bei denen jede Art von Gegenstand dem Wert entspricht: . Auf dem Gebiet der Kryptographie, der Begriff Rucksackproblem wird oft verwendet, um sich speziell auf das Summenproblem der Untergruppe zu beziehen und allgemein als einer von bekannt Karps 21 NP-Complete-Probleme.[31]

Die Verallgemeinerung des Summenproblems der Untergruppe wird als mehrfaches Subset-Sum-Problem bezeichnet, bei dem mehrere Behälter mit derselben Kapazität vorhanden sind. Es wurde gezeigt, dass die Verallgemeinerung keine hat Fptas.[32]

Geometrisches Rucksackproblem

In dem Geometrisches RucksackproblemEs gibt eine Reihe von Rechtecken mit unterschiedlichen Werten und einen rechteckigen Rucksack. Ziel ist es, den größtmöglichen Wert in den Rucksack zu packen.[33]

Siehe auch

Anmerkungen

  1. ^ Mathews, G. B. (25. Juni 1897). "Auf der Partition der Zahlen" (PDF). Verfahren der London Mathematical Society. 28: 486–490. doi:10.1112/PLMS/S1-28.1.486.
  2. ^ Dantzig, Tobias (2007). Nummer: Die Sprache der Wissenschaft (The Masterpiece Science Ed.). New York: Plume -Buch. ISBN 9780452288119.
  3. ^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Rucksackprobleme. Berlin: Springer. p. 449. ISBN 978-3-540-40286-2. Abgerufen 5. Mai 2022.
  4. ^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Rucksackprobleme. Berlin: Springer. p. 461. ISBN 978-3-540-40286-2. Abgerufen 5. Mai 2022.
  5. ^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Rucksackprobleme. Berlin: Springer. p. 465. ISBN 978-3-540-40286-2. Abgerufen 5. Mai 2022.
  6. ^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Rucksackprobleme. Berlin: Springer. p. 472. ISBN 978-3-540-40286-2. Abgerufen 5. Mai 2022.
  7. ^ Feuermann, Martin; Weiss, Harvey (April 1973). "Ein mathematisches Programmiermodell für die Testkonstruktion und -bewertung". Managementwissenschaft. 19 (8): 961–966. doi:10.1287/mnsc.19.8.961. JStor 2629127.
  8. ^ Skiena, S. S. (September 1999). "Wer interessiert sich für Algorithmen und warum? Lehren aus dem Stony Brook Algorithmus Repository". ACM Sigact News. 30 (3): 65–74. Citeseerx 10.1.1.41.8357. doi:10.1145/333623.333627. ISSN 0163-5700. S2CID 15619060.
  9. ^ Pisinger, D. 2003. Wo sind die harten Rucksackprobleme? Technischer Bericht 2003/08, Abteilung für Informatik, Universität Kopenhagen, Kopenhagen, Dänemark.
  10. ^ Caccetta, L.; Kulanoot, A. (2001). "Rechenaspekte von Hardacksack -Problemen". Nichtlineare Analyse. 47 (8): 5547–5558. doi:10.1016/s0362-546x (01) 00658-7.
  11. ^ a b c Poirriez, Vincent; Yanev, Nicola; Andonov, Pansen (2009). "Ein Hybridalgorithmus für das unbegrenzte Rucksackproblem". Diskrete Optimierung. 6 (1): 110–124. doi:10.1016/j.disopt.2008.09.004. ISSN 1572-5286.
  12. ^ Wojtczak, Dominik (2018). "Über starke NP-Vervollständigung rationaler Probleme". Internationales Informatik -Symposium in Russland. Vorlesungsnotizen in Informatik. 10846: 308–320. Arxiv:1802.09465. doi:10.1007/978-3-319-90530-3_26. ISBN 978-3-319-90529-7. S2CID 3637366.
  13. ^ a b Andonov, Pansen; Poirriez, Vincent; Rajopadhye, Sanjay (2000). "Unbegrenztes Rucksack Problem: Dynamisches Programmieren überarbeitet". Europäisches Journal of Operational Research. 123 (2): 168–181. Citeseerx 10.1.1.41.2135. doi:10.1016/s0377-2217 (99) 00265-9.
  14. ^ S. Martello, P. Toth, Rucksack -Probleme: Algorithmen und Computerimplementierungen, John Wiley und Sons, 1990
  15. ^ S. Martello, D. Pisinger, P. Toth, Dynamische Programmierung und starke Grenzen für das 0-1 Rucksack-Problem, Verwalten. Sci.45: 414–424, 1999.
  16. ^ Plateau, G.; Elkihel, M. (1985). "Ein Hybridalgorithmus für das 0: 1-Rucksackproblem". Methoden der Oper. Res. 49: 277–293.
  17. ^ Martello, S.; Toth, P. (1984). "Eine Mischung aus dynamischer Programmierung und Ast-und-gebunden für das Problem der Untergruppe". " Verwalten. Sci. 30 (6): 765–771. doi:10.1287/mnsc.30.6.765.
  18. ^ Horowitz, Ellis; Sahni, Sartaj (1974), "Berechnung von Partitionen mit Anwendungen zum Rucksack -Problem", Journal of the Association for Computing Machinery, 21 (2): 277–292, doi:10.1145/321812.321823, HDL:1813/5989, HERR 0354006, S2CID 16866858
  19. ^ a b Vazirani, Vijay. Näherungsalgorithmen. Springer-Verlag Berlin Heidelberg, 2003.
  20. ^ Dantzig, George B. (1957). "Diskret-variable Extremumsprobleme". Unternehmensforschung. 5 (2): 266–288. doi:10.1287/Opre.5.2.266.
  21. ^ Calvin, James M.; Leung, Joseph Y. -t. (1. Mai 2003). "Durchschnittliche Case-Analyse eines gierigen Algorithmus für das Problem mit 0/1 Rucksack". Operations Forschungsbriefe. 31 (3): 202–210. doi:10.1016/s0167-6377 (02) 00222-5.
  22. ^ Chang, T. J., et al. Heuristik für die Optimierung von Kardinalität eingeschränkten Portfolio. Technischer Bericht, London SW7 2AZ, England: Die Management School, Imperial College, Mai 1998
  23. ^ Chang, C. S., et al. "Genetische Algorithmusbasis -Bikriterionoptimierung für Traktionsumspannungen im DC -Eisenbahnsystem. "In Fogel [102], 11-16.
  24. ^ Kulik, A.; Shachnai, H. (2010). "Es gibt keine EPTAs für zweidimensionale Rucksack" (PDF). Inf. Verfahren. Lette. 110 (16): 707–712. Citeseerx 10.1.1.161.5838. doi:10.1016/j.ipl.2010.05.031.
  25. ^ a b c Cohen, R. und Grebla, G. 2014. "Mehrdimensionale OFDMA-Planung in einem drahtlosen Netzwerk mit Relaisknoten". in Proc. IEEE INFOCOM'14, 2427–2435.
  26. ^ Yan Lan, György Dósa, Xin Han, Chenyang Zhou, Attila Benkő [1]: 2D -Rucksack: Packen von Quadräten, Theoretische Informatik Vol. 508, S. 35–40.
  27. ^ Chandra Chekuri und Sanjeev Khanna (2005). "A PTAs für das Problem mit mehreren Rucksack". Siam Journal über Computing. 35 (3): 713–728. Citeseerx 10.1.1.226.3387. doi:10.1137/s0097539700382820.
  28. ^ Wu, Z. Y.; Yang, Y. J.; Bai, F. S.; Mammadov, M. (2011). "Globale Optimalitätsbedingungen und Optimierungsmethoden für quadratische Rucksackprobleme". J Optim Theory Appl. 151 (2): 241–259. doi:10.1007/s10957-011-9885-4. S2CID 31208118.
  29. ^ Gallo, G.; Hammer, P. L.; Simeone, B. (1980). Quadratische Rucksackprobleme. Mathematische Programmierstudien. Vol. 12. S. 132–149. doi:10.1007/bfb0120892. ISBN 978-3-642-00801-6.
  30. ^ Witzgall, C. (1975). "Mathematische Methoden der Standortauswahl für elektronische Nachrichtensysteme (EMS)". NASA STI/RECKRECTION TECHNISCHER ANGEBEITEN N. NBS Interner Bericht. 76: 18321. Bibcode:1975stin ... 7618321w.
  31. ^ Richard M. Karp (1972). "Reduzierbarkeit zwischen kombinatorischen Problemen". In R. E. Miller und J. W. Thatcher (Herausgeber). Komplexität von Computerberechnungen. New York: Plenum. S. 85–103
  32. ^ Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000). "Das Problem mit mehreren Untergruppen der Untergruppe". Siam J. Optim. 11 (2): 308–319. Citeseerx 10.1.1.21.9826. doi:10.1137/s1052623498348481.
  33. ^ Abed, Fidaa; Chalermsook, Parinya; Correa, José; Karrenbauer, Andreas; Pérez-Lantero, Pablo; Soto, José A.; Wiese, Andreas (2015). Auf Guillotine -Schneidsequenzen. S. 1–19. doi:10.4230/lipics.approx-random.2015.1. ISBN 978-3-939897-89-7.

Verweise

Externe Links