Algorithmen für zwei- und dreidimensionalen Rucksack

8

Ich weiß, dass die 2D- und 3D-Knapsack-Probleme NPC sind, aber gibt es eine Möglichkeit, sie in angemessener Zeit zu lösen, wenn die Instanzen nicht sehr kompliziert sind? Würde dynamische Programmierung funktionieren?

Mit 2D (3D) Rucksack meine ich, ich habe ein Quadrat (Würfel) und eine Liste von Objekten, alle Daten sind in Zentimetern und höchstens 20 m.

algorithms complexity-theory np-complete computational-geometry knapsack-problems Anonym
quelle
1
Welche Formen haben Ihre Objekte? Wie groß ist die Umgebung? Hat es die Größe begrenzt?
Raphael
Suchen Sie einen genauen Löser oder reichen Heuristiken aus?
Stefan
1
Könnten Sie genauer sein? Was sind "Größen" und was istm ? Wasgenauist Ihr Input, wasgenausind Ihre Einschränkungen und wasgenauversuchen Sie zu optimieren?
JeffE
1
Und was hast du schon versucht?
JeffE
4
Das Problem, über das Sie sprechen, wird im Allgemeinen nicht als Rucksackproblem bezeichnet. Normalerweise handelt es sich um das Problem des Packens von Namen , und Sie sollten in der Lage sein, unter diesem Namen viel mehr Informationen darüber zu finden.
Steven Stadnicki

Antworten:

1

Knapsack kann durch dynamische Programmierung gelöst in pseudo-Polynom Zeit mit n der Anzahl der Objekte und W der Größe des Rucksacks. Solange Ihr Container klein ist (numerisch), können Sie das Problem effizient lösen. Beachten Sie, dass Sie W anpassen können, indem Sie die Auflösung ändern. Es ist nicht erforderlich, einen Versandbehälter auf µm zu messen, aber die Messgeräte sind wahrscheinlich zu grob (abhängig von Ihren Objekten).O(nW)nWW

Der Rucksack kann auch in der Polynomzeit beliebig gut approximiert werden (siehe Polynomzeit-Approximationsschemata ).

Knapsack berücksichtigt jedoch nur das Anpassen von Zahlen an eine andere Zahl. Geometrie ist ihm egal. Wenn Sie "rätseln" müssen, brauchen Sie ein anderes Problem; In Anbetracht von Tetris ist dies wahrscheinlich viel schwieriger als Knapsack .

Raphael
quelle
0

GREEDY wird immer eine vernünftige Lösung finden, aber nicht unbedingt die optimale. Legen Sie einfach das größte Objekt, das jedes Mal in den Rucksack passt. Stoppen Sie, wenn keine Objekte mehr passen.

Salsaman
quelle
Nein, das stimmt nicht. Beachten Sie, dass im Knapsack-Problem auch Objekte Werte haben. Das gierige Befüllen nach Größe kann zu einer willkürlich schlechten Lösung führen.
Raphael
@ Raphael: Nun, nicht willkürlich schlecht, aber ich würde die gierige Lösung nicht als vernünftige Lösung betrachten. Der gierige Ansatz wird für die höherdimensionalen Analoga schlechter.
A.Schulz
@ A.Schulz Eigentlich ja willkürlich schlecht! Es kann leicht gezeigt werden, dass die gierige Heuristik für Rucksäcke, die entweder Größe oder Preis-Leistungs-Verhältnis verwendet, keine endliche Annäherungsgarantie an OPT hat.
Aaron
Leute ... bitte hör auf zu sagen "Nun, das weiß ich nicht! Aber ..." bevor du deine % # $ machst ( Hausaufgaben drauf!
MickLH