Hallo Leute,

Wir schreiben eine Projektarbeit über das Rucksackproblem. Wir suchen aber neben den evolutiönären und den dynamischen Algorithmus noch weitere Optimierungen. Kann mir jemand evtl einen link schicken oder das ganze gleich posten?
Bin für jede hilfe dankbar


Moderiert von Narses: Topic aus Sonstiges (Delphi) verschoben am Do 20.05.2010 um 15:56

wie oben beschrieben, haben wir das dynamische schon ... -.-

Hallo und in der Entwickler-Ecke,

Mir stellt sich dann erstmal die Frage: Gibt es überhaupt noch andere "Optimierungen" dafür? Muss das unbedingt optimal gelöst werden, oder könnt ihr auch Näherungsverfahren (Greedy) besprechen und zeigen, dass ein Greedy-Ansatz (nicht?) beliebig schlecht sein kann?

Ich weiß nicht, ob es noch Optimierungen gibt. Greedyverfahren sind auch ok, das Evolutionsverfahren gibt ja auch nicht immer die exakte Lösung aus.
Am Ende wollen wir ein Paar Verfahren vergleichen und dann gucken, welches am schnellsten und besten ist.

hi

Sehr ergiebig, ist auch oftmals die Betrachtung der Englischen und Deutschen Wikipedia: Während die Deutsche sehr genau und kurz ist, ist die Englische oftmals etwas umfangreicher.

lg,

"George Dantzig proposed (1957) a greedy approximation algorithm to solve the unbounded knapsack problem. His version sorts the items in decreasing order of value per unit of weight, vi / wi. It then proceeds to insert them into the sack, starting with as many copies as possible of the first kind of item until there is no longer space in the sack for more. Provided that there is an unlimited supply of each kind of item, if m is the maximum value of items that fit into the sack, then the greedy algorithm is guaranteed to achieve at least a value of m / 2. However, for the bounded problem, where the supply of each kind of item is limited, the algorithm may be far from optimal."

Bedeutet das jetzt, dass er für jedes Element das Verhältnis wert zu Masse berechnet hat und dann solange die mit dem besten Verhältnis in den Sack gestopft hat, bis er voll ist?

Exakt .

Ich hab es mal programmiert, es funktioniert tatsächlich ganz gut. Hat bei 1.000.000 ELementen mit einer Gewichtsbeschränkung von 2.000.000 1.998.999 rausbekommen.
Gibt es noch andere Methoden?

Hallo,

und was heißt das:

Zitat:

mit einer Gewichtsbeschränkung von 2.000.000 1.998.999 rausbekommen.

Waren die übrig geblienbenen Elemente jetzt alle schwerer als 2.000.000-1.998.999=1001 kg?
Sonst hätte mindestens eins noch Platz gehabt.

Gruß Horst
Ok, negativer Wert wäre noch eine Möglichkeit, stände aber bestimmt nicht auf der Liste

Hallo,

Zitat:

Wir suchen aber neben den evolutiönären und den dynamischen Algorithmus noch weitere Optimierungen.

Simulated Annealing könnte auch dafür verwendet werden. Und somit auch alle verwandten wie der Sintflutalgorithmus, etc.


mfG Gü

Oder negative Masse Da würde der Algo sogar einen kolossalen Fehler machen =D

Danke erstmal für eure Hilfe

Horst_H hat folgendes geschrieben :

Hallo, und was heißt das: Zitat: mit einer Gewichtsbeschränkung von 2.000.000 1.998.999 rausbekommen. Waren die übrig geblienbenen Elemente jetzt alle schwerer als 2.000.000-1.998.999=1001 kg?

Damir war gemeint, dass das Tragelimit bei 2.000.000 lag und der Algorithmus hat 1.998.999 rausbekommen. Ich habe die Liste in einer For-Schleife mit Array[Schleifenvariable].wert = Schleifenvariable. VOn da her war kein Element mit 1001 kg mehr frei. Daswegen finde ich, dass das für eine Nährungslösung eigentlich gar nicht schlecht ist.
Laut wikipedia ist der Sinnflutalgo genauer als das simulierte abkühlen.
Der ist so beschrieben:

"
Wähle einen anfänglichen Schwellwert T > 0
Wähle einen Schwellwertfaktor TF (0 < TF < 1)
Wähle eine Zahl von Probierschritten Zmax
Wähle eine anfängliche Konfiguration C
Referenzlösung C_ref := C
Wiederhole bis Abbruchbedingung erfüllt
Wiederhole Zmax mal
Wähle neue Konfiguration C' (ausgehend von C)
Falls Qualität(C´) > Qualität(C_ref)
C_ref := C´
dQ := Qualität(C') - Qualität(C)
Falls dQ > -T
C := C'
T := T * TF
Gib C_ref aus
"

Was ich noch nicht verstehe ist, wie man am Anfang Zmax festlegt.

Hallo,

Zitat:

Laut wikipedia ist der Sinnflutalgo genauer als das simulierte abkühlen.

Das kommt schon sehr auf die Wahl der Parameter an. Nur weil in Wiki steht:

Zitat:

Experimente der Erfinder deuten außerdem darauf hin, dass die Schwellenakzeptanz unter vergleichbaren Bedingungen häufig qualitativ bessere Lösungen liefert als die simulierte Abkühlung.

heißt das noch nichts. Die Erfinder werden ja auch nicht ihrer Erfinden den Nachzug geben

Zmax ist eben so ein Parameter der festgelegt werden muss. Die korrekte Wahl kann nur durch Probieren ermittelt werden.


mfG Gü

und wie probiert man das aus?

Pr0g3r hat folgendes geschrieben :

und wie probiert man das aus?

1. nimm eine Zahl
   
2. führe den Algorithmus aus
   
3. ist das Ergebnis zufriedenstellend? Falls ja Ende des Probierens, falls nein gehe zu Punkt 1
   

SCNR


mfG Gü

mmh
gibt es da nichts eleganteres, womit man am Anfang berechnen kann, wie viele Durchläufe man ca braucht?

Hallo,

das wäre super - aber das gibts bei keinem heuristischen Algorithmus. (Sonst wäre diese ja fast überflüssig wenn die Anzahl der Iterationen bekannt ist).

Du kannst aber in der Literatur für Empfehlungen o.ä. suchen.

mfG Gü

Ich hab mal geguckt, aber leider nichts gefunden
vielleicht 2^irgendwas? (ist es ja meistens )

Hi

Dabei lässt sich sicherlich - unter Annahme zufälliger Gegenstände - ein Erwartungswert angeben. Dieser kann aber durch die vermutlich relativ starke Streuung auch sehr nutzlos ausfallen.

Erfahrungsgemäß ist der Rechenaufwand für die nächsthöhere Anzahl von Iterationen dabei aber so viel höher, dass selbst die vorherige Berechnung aller kleinerer Iterationsstufen noch nicht zu inem merklichen Anstieg der Rechenzeit führt.
So auch beim Schach, wo die Anzahl der vorausberechneten Halbzüge zwar stufenweise erhöht wird, aber für jede weitere Stufe alle vorherigen Berechnungen komplett neu durchgeführt werden.
Ob das bei deinem Algo so ist, hängt vom Anstieg der Rechenzeit mit der Iterationsanzahl ab. Für Schach ist das proportional zum Verhältnis von Blättern zu Knoten, und es existieren in einem Baum sehr viel mehr Blätter als Knoten.

lg,