Holz zerschneiden - NP schwer?
-
Q schrieb:
Hast du das beachtet?
Nein, sorry, da muss ich weiter überlegen.
-
nochne idee:
Wenn man alles mal 100 rechnet, hat man ganze zahlen und keine 2 nachkommastellen mehr, vll bringt das irgendwas
-
Q schrieb:
nochne idee:
Wenn man alles mal 100 rechnet, hat man ganze zahlen und keine 2 nachkommastellen mehr, vll bringt das irgendwasDas ist eh klar, daß man nur in Centimetern rechnet.
-
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.
-
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
-
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.
-
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.