Holz zerschneiden - NP schwer?

*Q* 1

Hallo,

ein freund von mir hatte heute seine Abschlussprüfung bei der IHK und da hatten die eine Aufgabe bei der es um die Zerschneidung von Holz geht.
Ich habe mich jetzt gefragt (rein aus Interesse), ob das problem NP schwer (evtl. kennt ihr das als NP-hart, aber bei uns meinte der Prof., dass das eine schlechte Übersetzung sei und wir besser NP-schwer sagen sollen) ist, oder ob es vielleicht einen effizienten algorithmus dafür gibt, bin mir aber noch nicht so sicher. Vielleicht habt ihr eine Idee.

Hier das Problem (gekürzt):
In einem Lager befinden sich beliebig viele Balken der Längen 2m, 3m, 4m und 5m.
Die Eingabe ist dann ein "Auftrag", also eine Menge von Längen von Holzbalken (2 Stellen hinterm Komma).
Nun müssen Balken aus dem Lager zersägt werden um den Auftrag zu erfüllen. Das Ziel ist es, so wenig Verschnitt wie möglich zu haben. Wenn es mehrere optimale Möglichkeiten gibt, dann ist die Lösung mit den wenigsten Schnitten zu bevorzugen.

Beispiel:
Auftrag: 2*2,48; 1*2,68; 2*3,12; 1*1,32; 2*1,33; 1*1,34
Verschnitt minimal: 1,80
Anzahl Schnitte: 7
4,00 -> 1,33; 1,33; 1,34 Verschnitt: 0,00
4,00 -> 2,68; 1,32; Verschnitt: 0,00
4,00 -> 3,12 Verschnitt: 0,88
4,00 -> 3,12 Verschnitt: 0,88
5,00 -> 2,48; 2,48; Verschnitt: 0,04

Anmerkung: Das mit den 2 Stellen hinterm komma stand da nirgendswo explizit, ist aber in allen Beispielen dort so und ich habe es jetzt einfach mal angenommen. Insbesondere interessiert mich auch, ob diese Einschränkung hier etwas an der Komplexitätsklasse ändert.

Erstmal sieht das sehr nach NP-schwer aus, denn das Problem hat eine starke ähnlichkeit zu Bin-Packing, Rucksack, Partition bzw makespan scheduling.
Aber evtl. geht die NP-schwere durch die beschränkung auf 2 Nachkommastellen und/oder durch die festen Längen der Bretter verloren? Evtl. kann man irgendwas mit dynamischer Programmierung machen, oder ausnutzen, dass die Längen der Bretter fest sind und das Problem dann auf eine endliche Menge an Grundproblemen zurückführen oder so...

Habt ihr eine Idee?

Edit: Für die NP-schwere müsste man natürlich eine Entscheidungsvariante betrachten, also dass man entscheiden muss, ob es mit Verschnitt höchstens k (teil der eingabe) möglich ist, die Bretter zu zersägen.

Q schrieb:

Habt ihr eine Idee?

Du bist doch Q, für dich sollte das doch kein Problem sein.
Da ist ja Chuck Norris schneller bei einer Lösung.

Q schrieb:

In einem Lager befinden sich beliebig viele Balken der Längen 2m, 3m, 4m und 5m.
Die Eingabe ist dann ein "Auftrag", also eine Menge von Längen von Holzbalken (2 Stellen hinterm Komma).

Also wenn es wirklich nur 2 Stellen hinterm Komma sind, ist das Problem doch trivial. Es gibt nur endlich viele Eingaben mit Summe<=2m+3m+4m+5m, weil jeder Auftrag zwischen 0.01 und 14.00 liegt und es maximal 14/0.01 Aufträge geben kann.

Endlich viele Eingaben => Alle können vorberechnet werden => Antwort in O(1).

*Q* 1

@Holzhammer:

Q schrieb:

In einem Lager befinden sich beliebig viele Balken der Längen 2m, 3m, 4m und 5m.
Die Eingabe ist dann ein "Auftrag", also eine Menge von Längen von Holzbalken (2 Stellen hinterm Komma).

Hast du das beachtet?

Q schrieb:

Hast du das beachtet?

Nein, sorry, da muss ich weiter überlegen.

*Q* 1

nochne idee:
Wenn man alles mal 100 rechnet, hat man ganze zahlen und keine 2 nachkommastellen mehr, vll bringt das irgendwas

volkard

Q schrieb:

nochne idee:
Wenn man alles mal 100 rechnet, hat man ganze zahlen und keine 2 nachkommastellen mehr, vll bringt das irgendwas

Das ist eh klar, daß man nur in Centimetern rechnet.

volkard

Möglichst wenig Schnitte sagt, daß man bei gleich wenig Verlust die Lösung bevorzugen soll, die kürzere Balken aus dem Lager nimmt.
Das würde heißen, wenn ich ein einen Balken mit Aufträgen so füllen kann, daß auf diesem Balken der Verlust minimal ist, und kurze Balken erst probiert habe, kann ich den Balken schon so ausdrucken, weil es kein Backtracking geben muss?

Ich hätte eine polynomielle Lösung, wenn garantiert wäre, dass es keinen Verschnitt gäbe.

Die Probleminstanz kann man als Vektor von 400 Zahlen ansehen, die angeben, wie viele Hölzer von Länge 0.01, 0.02, ..., 4.00 gewünscht sind.

Für 2*3*4*5m gibt es eine endliche Anzahl Vektoren optimaler Zerlegungen.

Jede Lösung lässt sich, bis auf einen endlichen Rest, in 2*3*4*5m-Blöcke zerlegen.
Wie viele solche Blöcke es mindestens gibt, kann man einfach berechnen.

Der Rest lässt sich ebenfalls als 400 Zahlen auffassen, die Möglichkeiten sind beschränkt, wir können alle durchgehen. Um von Probleminstanz minus Rest auf die Lösung zu kommen ist es nur nötig, den Vektor (Probleminstanz minus Rest) als Linearkombination der Lösungsvektoren darzustellen.

holzhammer schrieb:

Ich hätte eine polynomielle Lösung, wenn garantiert wäre, dass es keinen Verschnitt gäbe.

Der Ansatz lässt sich auf jeden endlichen Verschnitt erweitern.

*Q* 1

gute Idee allerdings sehr ich noch zwei Probleme:
1. wie berechnest du die koeffizienten? bedenke dass sie ganzzahlig und nicht negativ sein müssen.
2. der verschnitt einer optimalen Lösung ist auch bei der entscheidungsvariante unbekannt, da man da nur eine Obergrenze als Eingabe kriegt

Bitte ein Bit

Also wenn es wirklich nur 2 Stellen hinterm Komma sind, ist das Problem doch trivial. Es gibt nur endlich viele Eingaben mit Summe<=2m+3m+4m+5m, weil jeder Auftrag zwischen 0.01 und 14.00 liegt und es maximal 14/0.01 Aufträge geben kann.

Endlich viele Eingaben => Alle können vorberechnet werden => Antwort in O(1).

Ähh was ist das für ein dummer Spruch...

Alle NP-vollständigen Probleme haben endlichen Eingaben und können mit einer endlichen Anzahl von Regeln beschrieben werden. Das Problem ist nur dass man ab einer gewissen Größe rechnet bis zum Sankt Nimmerleinstag. Und dumm, erhöht die Eingabegröße nur um 1 Element, rechnet doppelt so lange. 2^100 Rechenschritte sind zwar endlich, aber nicht praktisch berechenbar. Löse doch mal ein 50x50 Sudoku. Oder löse mal die Ackermannfunktion mit (100/100). Da würde sogar der Quantenrechner der Borg zusammenbrechen.

Endlichkeit bringt dir hier nichts.

Bitte ein Bit schrieb:

Also wenn es wirklich nur 2 Stellen hinterm Komma sind, ist das Problem doch trivial. Es gibt nur endlich viele Eingaben mit Summe<=2m+3m+4m+5m, weil jeder Auftrag zwischen 0.01 und 14.00 liegt und es maximal 14/0.01 Aufträge geben kann.

Endlich viele Eingaben => Alle können vorberechnet werden => Antwort in O(1).

Ähh was ist das für ein dummer Spruch...

Alle NP-vollständigen Probleme haben endlichen Eingaben und können mit einer endlichen Anzahl von Regeln beschrieben werden. Das Problem ist nur dass man ab einer gewissen Größe rechnet bis zum Sankt Nimmerleinstag. Und dumm, erhöht die Eingabegröße nur um 1 Element, rechnet doppelt so lange. 2^100 Rechenschritte sind zwar endlich, aber nicht praktisch berechenbar. Löse doch mal ein 50x50 Sudoku. Oder löse mal die Ackermannfunktion mit (100/100). Da würde sogar der Quantenrechner der Borg zusammenbrechen.

Endlichkeit bringt dir hier nichts.

A(n, m) für 0<n,m<=100 zu berechnen liegt in O(1), da kannst du sagen, was du willst.

Bashar

Bitte ein Bit schrieb:

Also wenn es wirklich nur 2 Stellen hinterm Komma sind, ist das Problem doch trivial. Es gibt nur endlich viele Eingaben mit Summe<=2m+3m+4m+5m, weil jeder Auftrag zwischen 0.01 und 14.00 liegt und es maximal 14/0.01 Aufträge geben kann.

Endlich viele Eingaben => Alle können vorberechnet werden => Antwort in O(1).

Ähh was ist das für ein dummer Spruch...

Alle NP-vollständigen Probleme haben endlichen Eingaben und können mit einer endlichen Anzahl von Regeln beschrieben werden.

Endlich viele Eingaben, nicht endliche Eingaben.