CD optimal füllen: Wie sollte Algorithmus aussehen?
-
mezzo mix schrieb:
deine aufgabe kannst du mit dem simplex-algorithmus lösen.
eher nicht.
allenfalls infofern, daß man sogar mit einem klavier primzahlen berechnen kann, wenn man ein wenig frickelt.
-
volkard schrieb:
mezzo mix schrieb:
deine aufgabe kannst du mit dem simplex-algorithmus lösen.
eher nicht.
allenfalls infofern, daß man sogar mit einem klavier primzahlen berechnen kann, wenn man ein wenig frickelt.falls du darauf hinaus willst, daß ich "simplex-" anstatt "dualer simplex-algorithmus" geschrieben hab...
ansonsten erleuchte mich!
-
mezzo mix schrieb:
falls du darauf hinaus willst, daß ich "simplex-" anstatt "dualer simplex-algorithmus" geschrieben hab...
ansonsten erleuchte mich!Ich kenne den Dualen Simplex Algorithmus nicht, würde der sich denn relativ einfach als C++-Version erstellen lassen?
Ich habe jetzt eine erste Version fertig, die alle möglichen Kombinationen durchgeht und ab ca. 10 Dateien dauerts merklich länger.
-
mezzo mix schrieb:
deine aufgabe kannst du mit dem simplex-algorithmus lösen
Der Simplex-Algorithmus, den ich kenne, kann keine ganzzahligen Optimierungsprobleme lösen.
-
doch der Simplex-Algorithmus *kann* ganzzahlige Optimierungsprobleme lösen - man muss nur nach jedme Lauf gewisse zusätzliche Nebenbedinungen hinzunehmen - allerdings potenziert sich die Laufzeit dadurch ziemlich - bei Interesse hilft sogar Wikipedia weiter.
-
Ich persönlich denke auch, dass volkards Verfahren in der Praxis vielleicht gar nicht mal so schlecht ist. Es wird sicherlich nicht immer zur optimalen Lösung führen (und man kann natürlich auch leicht Beispiele konstruieren wo es zu sehr schlechten Lösungen führt). Aber wenn man dann noch das was Marcus gesagt hat mit betrachtet, dann scheint mir das sogar eine ganz gute Lösung zu sein, für die Praxis jedenfalls. Zudem sehr einfach zu implementieren. Ist ja im Prinzip nur ein Greedy-Verfahren wenn mich nicht alles täuscht.
-
Ja, es ist ein Greedy-Verfahren. Man kann zeigen, dass es sich dabei um eine 2-Approximation handelt. Das heißt man braucht höchstens doppelt so viele Datenträger wie im Optimalfall nötig. Soooo schlecht kann's also garnicht werden.
Der Beweis ist einfach: Man betrachte zwei aufeinanderfolgende Datenträger. Die sind beide mindestens halbvoll (sonst hätten wir ja nicht zwei Datenträger dafür gemacht). Also braucht auch die optimale Lösung mindestens einen Datenträger um die Daten abzulegen, die wir auf zwei Datenträger verteilt haben.
Tatsächlich kann man sogar auf die Sortierung nach Größe verzichten.
Besser als Faktor 3/2*optimale Anzahl Datenträger kann man in Polynomialzeit nicht werden.
-
ah, binpacking, sehr schön. da hab ich gerade ein proseminar drüber gehalten
http://homepages.uni-paderborn.de/olaf/perlen/ausarbeitung.pdf
da sind auch 2 algorithmen drin, falls es den threadersteller noch interessiert.
-
Also erst einmal vielen Dank für die nach wie vor eintrudelnen Antworten
Habt mir alle sehr geholfen und ich habe das Programm mittlerweile auch fertig auf die Beine bekommen, bin mit der Geschwindigkeit und den Ergebnissen auch sehr zufrieden.@borg
Dieser Lösungsansatz ist ganz anders, sieht sehr gut aus! Vor allem gefällt mir, daß er wesentlich leichter zu programmieren ist.
Ich habe das Programm wie gesagt fertig, werde deinen Algorithmus aber auf jeden Fall mal ausprobieren und gegebenenfalls dann bei mir einbauen, da ich damit das Programm wohl um einiges kürzer machen könnte.Vielen Dank an dieser Stelle noch mal für alle Rückmeldungen! Habe bloß leider im Moment keine Zeit aktiv zu programmieren, bin im Klausurstreß.
-
Tsunami schrieb:
@borg
Dieser Lösungsansatz ist ganz anders, sieht sehr gut aus! Vor allem gefällt mir, daß er wesentlich leichter zu programmieren ist.
Ich habe das Programm wie gesagt fertig, werde deinen Algorithmus aber auf jeden Fall mal ausprobieren und gegebenenfalls dann bei mir einbauen, da ich damit das Programm wohl um einiges kürzer machen könnte.pass aber auf, da sind 2 algorithmen im pdf. nextFit kann bis zu 2 mal so schlecht werden wie die optimale lösung und bestFit kann nur bis zu 1.7 mal so schlecht werden wie eine optimale lösung. wenn du bestFit mit einem balancierten baum implementierst ist auch die laufzeit ok: O(nlog(n)). aber das fällt eigentlich schon nicht mehr unter den bereich "trivial" dafür brauchst du immerhin rb-trees oder avl-trees.
-
borg schrieb:
wenn du bestFit mit einem balancierten baum implementierst ist auch die laufzeit ok: O(nlog(n)). aber das fällt eigentlich schon nicht mehr unter den bereich "trivial" dafür brauchst du immerhin rb-trees oder avl-trees.
Wenn die Implementierungssprache beispielsweise C++ ist, dann leistet set (bzw. multiset) das Gewünschte. Insofern isses dann doch wieder einfach zu implementieren.
-
jo
-
So, habe dieses WE wieder ein wenig mehr Zeit und wollte mal gucken wie ich den vorhandenen Algorithmus vielleicht verkleinern kann, bevor ich mir den Vorschlag von borg genauer angucken wollte.
Ich habe mir bei meiner Lösung einen abgebrochen. Um den alternierenden Zahlenstrahl zu erzeugen benutze ich zwei Strings und das geht doch sicher einfacher oder?
Hat jemand eine Idee wie man so einen Zahlenstrahl ohne großen Aufwand erstellen kann und auch alle möglichen Kombinationen abdeckt?