CD optimal füllen: Wie sollte Algorithmus aussehen?
-
Alle möglichen Kombinationen ist ganz einfach. Entweder ist eine Datei in der Kombination drin oder nicht. D. h. es gibt bei n Dateien 2^n verschiedene Möglichkeiten. Die kannst du einfach durch eine Zählvariable darstellen.
Beispiel für n = 8:
Zählvariable Kombination 0000 0001 achte Datei 0000 0010 siebte Datei 0000 0011 siebte und achte Datei 0000 0100 sechste Datei ...
-
Danke für den Tip. Das ist natürlich ein neuer Denkansatz das alles als binären Zahlenstrahl abzulegen. Dann müßte ich mir nur noch einen Weg überlegen, wie ich den am besten manipuliere, damit auch wirklich alle Möglichkeiten abgegriffen werden.
Das Auswerten ist ja mit dieser Technik kein Problem mehr
-
Tsunami schrieb:
Dann müßte ich mir nur noch einen Weg überlegen, wie ich den am besten manipuliere, damit auch wirklich alle Möglichkeiten abgegriffen werden.
Es werden doch alle durchgegangen
-
Michael E. schrieb:
Es werden doch alle durchgegangen
Damit meinte ich eigentlich auch den Algorithmus, der den String verändert. Es könnte ja passieren, wenn man nicht genau aufpaßt und testet, daß man durch einen Fehler unbeabsichtigt Lücken reißt.
Aber die Idee mit dem Zahlenstrahl gefällt mir wirklich gut, danke nochmal für den Tip!
-
deine aufgabe kannst du mit dem simplex-algorithmus lösen.
grüße mm
-
Den Simplex-Algorithmus kenne ich auch, müßte man wirklich mal ausprobieren ob man damit auf Anhieb die optimale Lösung finden würde.
Wobei bei vielen Daten das Tableau sehr groß werden würde, muß ich einfach mal testen. Mache ich morgen.
-
da würd ich aber aufpassen, die Optimierungssoftware von Heute greift auf modifizierte Simplex- oder gänzlich andere schlaue Algorithmen zurück. Du könntest unter Umständen doch recht lange warten wenn du das selbst baust, wobei dein Problem ja eher winzig ist.
Aber der erste Schritt ist dann wohl das Aufstellen eines Linearen Optimierungsproblems, wenn ich mich nicht verschaut habe kann man das sogar als 0-1 LOP formulieren.
tt
-
Wie kann man denn hier das Simplex-Verfahren anwenden?
-
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