Algorithmus zur Lösung des Rucksackproblems (Version 2, korrigiert)

Das Folgende ist ein Algorithmus zum genauen Lösen des Ganzzahl-Rucksack-Problems. Der vorgeschlagene Algorithmus erfordert weniger Rechenressourcen und ist möglicherweise etwas einfacher als der dynamische Programmieralgorithmus (DP).

Der Grund veranlasste den Autor zur Veröffentlichung


Die erste Version der Beschreibung des Algorithmus wurde von mir an das Institut für Mathematik geschickt. S. L. Sobolev, Sibirischer Zweig der Russischen Akademie der Wissenschaften, von wo aus die Antwort gesendet wurde, dass der angegebene Algorithmus seit langem bekannt ist. Ich zitiere:
Eine seiner ersten Referenzen in Kerellers Buch ist Nemhauser, Ullman, Diskrete dynamische Programmierung und Kapitalallokation, Management Science, 15 S. 494-505, 1969.
Trotzdem habe ich mich entschlossen, die Community mit dem Algorithmus vertraut zu machen Ich habe es nicht in diskreten Mathematiklehrbüchern gefunden, die mir bekannt waren (vielleicht habe ich schlecht gesucht). In der ersten Version des Algorithmus ist ein Fehler aufgetreten, auf den der Benutzer wataru hingewiesen hat . Vielen Dank dafür. Ich habe versucht, diesen Fehler zu beheben. Ich habe den Algorithmus selbst erreicht und hoffe, dass ich die Rechte von niemandem verletze. Vielleicht findet jemand die Beschreibung interessant und nützlich.

Einleitung


Das eindimensionale Rucksackproblem (0-1-Rucksack) ist ein klassisches diskretes Optimierungsproblem [1], [2]. Diese Aufgabe und ihre Varianten sind weit verbreitet, um eine Vielzahl von praktischen Problemen zu modellieren. Allgemein lässt sich das Problem wie folgt formulieren: Aus einer gegebenen Menge von Objekten mit den Eigenschaften "Kosten" und "Gewicht" muss eine bestimmte Anzahl von Objekten so ausgewählt werden, dass die maximalen Gesamtkosten unter Einhaltung des Grenzwerts für das Gesamtgewicht erzielt werden.
Genauer gesagt seien P (i) > 0 und W (i) > 0 die Kosten und das Gewicht des i- ten Gegenstands, wobei i = 1,2,3, ..., N und N die Anzahl der Gegenstände ist.
Es ist erforderlich, einen solchen Booleschen Vektor X der Dimension zu findenN , wobei
X (i) = 1 ist, wenn der Gegenstand mit der Nummer i in den Rucksack gelegt wird;
X (i) = 0, wenn der Gegenstand mit der Nummer i nicht im Rucksack ist;
so dass die Summe Σ P (i) X (i) maximal ist
und die Ungleichung Σ W (i) X (i) ≤ C gilt , wobei C > 0 die Kapazität des Rucksacks ist.
Es gibt verschiedene genaue und ungefähre Algorithmen zur Lösung des Rucksackproblems.
Genaue Algorithmen umfassen:
  • erschöpfende Suche
  • Verzweigungs- und gebundene Methode
  • Dynamische Programmierung (DP)
.
Ungefähre Algorithmen sind gierig (JA) und genetisch (GA). Der Vergleich verschiedener Methoden zur Lösung des Rucksackproblems ist in der Literatur und im Internet weit verbreitet, sodass wir nicht weiter darauf eingehen und sofort zur Sache gehen.
Betrachten Sie eine Variante des Algorithmus zum Lösen des Rucksackproblems, vorausgesetzt, die Artikelgewichte sind natürliche Zahlen und die Artikelwerte sind reelle Zahlen.

Beschreibung des Algorithmus zur Lösung des Rucksackproblems mit Pseudocode-Elementen


EINGABE : // Eingabe
Die Quellendatenfelder (ID) enthalten ganzzahlige Gewichte W und reelle Werte P von Objekten W (1 ... N) > 0 und P (1 ... N) > 0,
wobei N die Anzahl der Objekte und C > 0 ist - Rucksackkapazität.
OUTPUT: //
Boolesches Array X (1 ... N) ausgeben , wobei X (i) = 1 ist, wenn sich das Element mit der Nummer i in der Lösung befindet, und X (i) = 0 ist, wenn sich das Element mit der Nummer i nicht in befindet die entscheidung.

START // Start des Algorithmus

Stufe 1 // ID sortieren
Сортируем ИД в порядке уменьшения удельной стоимости предметов:
P(1) / W(1) >= P(2) / W(2) >= ...>= P(i) / W(i)>=… >= P( N) / W(N)
где P(i) > 0 стоимость предмета i , W(i) >0 вес предмета i.
В массиве X(1...N) все элементы первоначально = 0.
Для снижения потребности в памяти для алгоритма определяем минимальный вес в наборе ИД W_min = min( W )

Этап 2 // инициализация рабочих массивов
Создаем массив вещественных чисел LP размерностью (W_min… С)
и массив целых чисел LCr размерностью (W_min… С) . In das Array LP und LCr geben wir die Daten des ersten Elements aus der sortierten Liste der IDs ein
  LP( W(1) )  = P(1)
  LCr( W(1) ) = 1 
Dabei ist P (1) der Preis und W (1) das Gewicht des ersten Elements in der sortierten Liste der IDs.

Stufe 3 // Füllen der Arbeitsfelder
 FOR i = 2 TO N  // цикл по оставшимся элементам ИД  

Sei W (i) und P (i) das Gewicht und die Kosten des aktuellen ID-Elements.
Wir erzeugen ein leeres Array von reellen Zahlen. Klon der Dimension (W_min ... C) .
Fügen Sie dem Clone- Array die Kosten des aktuellen ID-Elements hinzu
Clone( W(i) ) = P(i)
.
Kopieren des Arrays Clone von Null verschiedenen Daten aus dem Array LP Additionswert P (i) des aktuellen Elements und sein Index Erhöhung seines Gewichts W (i) , mit der Maßgabe , dass der Index Klon nicht die Kapazität des Rucksacks überschreiten C .
FOR j = W_min TO ( C - W(i) )  
  IF LP(j) >0 THEN
    Clone( j + W(i) ) = LP(j) + P(i) 
  END IF
NEXT // конец цикла копирования 

Wir modifizieren LP , LCr-Arrays basierend auf Daten aus dem Clone- Array . Wir aktualisieren in LP , LCr-Arrays nur die Elemente, deren Kosten in Clone höher sind als in LP .
  FOR j = W_min TO C  
    IF Clone( j ) >0 AND Clone( j ) > LP( j ) THEN
       LP( j ) = Clone( j ) 
       LCr( j ) = i
     END IF
   NEXT  // конец цикла модификации LP, LCr  
NEXT  // конец цикла по оставшимся элементам 

Stufe 4 // Generieren des Ergebnisses, umgekehrter Abstieg
Im LP- Array finden wir den Maximalwert der Kosten Pmax = MAX (LP) , dies sind die Kosten der gefundenen optimalen Lösung. Der Index des im Array gefundenen Elements ist gleich dem Gewicht der Lösung, wir bezeichnen es mit Wr , d.h. LP (Wr) = Pmax . Fügen Sie das erste in X gefundene Element hinzu:
 X( LCr( Wr ) ) = 1 
weiter
// цикл формирование результата 
UNTIL Wr > 0 // если Wr = 0, результат сформирован  
 // уменьшаем вес решения на вес добавленного в результат предмета
  Wr = Wr - W( LCr( Wr ) )   
  // Проверяем, не внесен ли уже следующий элемент в  X 
  IF  X(LCr( Wr ) = 0 then  // не внесен
       X( LCr( Wr ) ) = 1   //  вносим
  ELSE  //   внесен  

Wir verlassen den UNTIL- Zyklus und wiederholen die Schritte 2 , 3 , 4 (nur in Stufe 2 erstellen wir keine LP- und LCr- Arrays , sondern füllen sie mit Nullen). Wiederholen Sie Schritt 1 (ID sortieren) ist nicht erforderlich. Dies ist im Wesentlichen eine Rekursion, die jedoch aufgrund der vorläufigen Sortierung der ID nicht tief ist. Bei einigen Sätzen ist möglicherweise überhaupt keine Rekursions-ID vorhanden. Bei der Wiederholung der Berechnungen berücksichtigen wir nur die IDs, deren Index kleiner als LCr (Wr) ist, und reduzieren die erforderliche Rucksackgröße auf das erreichte Gewicht Wr .
         N_NEW = LCr( Wr ) -1
         C_NEW = Wr
         GOTO этап 2
    END IF
NEXT // конец цикла формирование результата 

FINISH // Ende des Algorithmus
Kosten der gefundenen Lösung Σ P (i) X (i) , Gewicht Σ W (i) X (i) .
Die Richtigkeit der Berechnung der Gesamtkosten eines Rucksacks kann leicht durch Induktion nachgewiesen werden. Das Wiederherstellen des optimalen Satzes von Gegenständen ist ebenfalls nicht schwierig. Der vorgestellte Algorithmus ermöglicht es uns, eine genaue Lösung für das ganzzahlige Problem eines Rucksacks zu erhalten.

Zusammenfassende Bemerkungen


  1. Die Gesamtkomplexität des vorgestellten Algorithmus besteht aus der Komplexität des Sortierens der ID und der Komplexität des Ausführens der Stufe 3 des Algorithmus (unter Berücksichtigung der Anzahl der Iterationen). Die Laufzeit von Stufe 3 ist proportional zur Anzahl der Artikel pro Rucksackkapazität ( N * C ). Es ist ziemlich schwierig, die Anzahl der Iterationen im Voraus zu bestimmen. Die Anzahl der Iterationen kann von 0 bis zur Anzahl der Objekte in der Lösung Σ X (i) variieren . Bei jeder Iteration, die in Schritt 4 auftritt , verringert sich der Rechenaufwand in den Schritten 2, 3 . Die obere Schätzung der Zeitkomplexität des gesamten Algorithmus überschreitet nicht N * C * (Anzahl der Iterationen + 1).
  2. Der Bedarf des Algorithmus im Speicher ist proportional zur Kapazität des Rucksacks C und hängt nicht von der Anzahl der Objekte im Eingabedatensatz N ab , die ihn von der DP-Methode unterscheidet.
  3. Die internen Zyklen von Schritt 3 können problemlos parallel ausgeführt werden.
  4. Bei einer großen Streuung der Stückkosten von Elementen können Sie Schritt 3 unterbrechen und die verbleibenden Elemente mit niedrigen Stückkosten nicht mehr berücksichtigen , wenn die Änderungen in Stufe 3 des Algorithmus oben im LP- Array aufhören.
  5. Wenn die Kapazität des Rucksacks C groß genug ist, so dass aus technischen Gründen keine Arrays der Dimension C erstellt werden können oder die Gewichte der Objekte reelle Zahlen sind, kann der vorgeschlagene Algorithmus einfach geändert werden, indem Arrays durch verknüpfte Listen ersetzt werden.
  6. Ob dieser Algorithmus polynomisch ist oder nicht, vermute ich nicht zu beurteilen.


Literatur

  1. Papadimitriou H., Steiglitz K. Kombinatorische Optimierung: Algorithmen und Komplexität. M .: Mir, 1985.
  2. T. Cormen, C. Leiserson, R. Rivest, C. Stein. Algorithmen: Konstruktion und Analyse. M .: Verlag "Williams", 2005.

Jetzt auch beliebt: