CD optimal füllen: Wie sollte Algorithmus aussehen?
-
Uiuiui, der Datenträgerguru spricht
-
Marc++us: Hast du da irgendwelche Zahlen?
-
Tsunami schrieb:
Also erst einmal danke für die ganzen Rückmeldungen!
Das im diesjährigen Bundeswettbewerb auch so eine Aufgabe gestellt wurde, wußte ich nicht. Wann ist der denn vorbei, damit man eventuell noch nähere Tips bekommt?
Hintergrund ist der, daß ich Burn to the Brim kenne und auch benutze. Allerdings möchte ich auf Linux migrieren und es gibt keine Linuxversion davon. Ich würde das Programm in C++ dann entwickeln, BttP ist allerdings in Pascal geschrieben und daher nicht so wirklich geeignet um da Codefragmente raus zu übernehmen.
Pascal und C++ ähneln sich eigentlich ziemlich, bis das Pascal keine OOP kennt. Die Typen sind alle gleich, es gibt keine großen Unterschiede.
-
Michael E. schrieb:
Marc++us: Hast du da irgendwelche Zahlen?
Keine, die ich nicht selbst gefälscht habe.
Da muß ich Dich auf öffentliche Quellen verweisen, z.B. c't.
Kleiner Exkurs (sorry for OT):
Du kannst es Dir aber auch ganz anschaulich vorstellen, zwei Gründe verursachen dies:
a) Geometrie - das ist eine Scheibe, die hängt nach Außen durch, wird aber gleichzeitig vom Lack nach oben gezogen, daher ist sie am Außenrand auch welliger, jetzt dreht man das, folglich "wabbert" die Kante in der Höhe einfach mehr, und dadurch bekommt man stärkere Signalschwankungen. Daß sich dies sofort als höhere Fehlerrate auswirkt ist naheliegend, das muß so sein.
b) Herstellung - da man alle Schichten über Spinningverfahren aufbringt (man kippt etwas in die Mitte und schleudert es dann über die Seite ab), sind diese am Rand dünner und weniger homogen als in der Mitte. Auch das Metall nimmt in der Dicke am Rand ab, da es gemäß einer Gaußverteilung aufgebracht wird. Daher sind alle Schichten am Rand empfindlicher, näher an ihren Limits, gleichzeitig ist dort aber die Nähe zum eindringenden Sauerstoff am geringsten, wodurch die Schichten stärker strapaziert werden.
Das ganze ist bei DVDR (egal ob + oder -) natürlich noch dramatischer als bei CDR, da die Strukturen kleiner sind.
-
DEvent schrieb:
Pascal und C++ ähneln sich eigentlich ziemlich, bis das Pascal keine OOP kennt. Die Typen sind alle gleich, es gibt keine großen Unterschiede.
Dann werde ich mir den Source wohl genauer angucken müssen, obwohl mir eine Eigenentwicklung am liebsten wäre, da am besten zu warten.
Mein größtes Problem ist der Algorithmus mit dem man alle möglichen Kombinationen erstellen läßt. Da weiß ich noch nicht so richtig, wie ich das machen soll
Edit:
Burn to the Brim ist übrigens in Delphi geschrieben, hatte ich falsch in Erinnerung.
-
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.