nicht angemeldet
Moin,
ich formuliere Deine Frage mal um: Du möchtest
a) einen Algorithmus finden, welcher die oben genannte Aufgabe automatisch löst und
b) diesen in einer bestimmten Art via GUI bedienbar machen.Fällt Dir auf, welche Begriffe in dieser Beschreibung *nicht* vorkommen?
Richtig: Es sind die Begriffe "Perl" und "CGI".
Was Du aber weiter unten wieder aufgreiftst ;-) Ja, ich weiss was Du meinst. Ich dachte mir so etwas schon.
Kannst Du Dein manuelles Verfahren in Form von Einzelschritten formulieren?
Sollte moeglich sein... Vielleicht etwas Arbeit, aber wozu hat man denn Freizeit!
Kannst Du garantieren, daß es sowohl terminiert als auch eine korrekte Lösung der Aufgabe liefert?
Theoretisch: nein. Praktisch jedoch ja, denn in meinem Fall sind die moeglichen Zeitraeume sowie die verlangten Arbeitszeiten im Verhaeltnis so gut, dass ich auch noch schauen kann, wer zu wem "passt". Dies koennte ich ja auch mittels einer Uebergabe eines Sympathie-Wertes loesen, so dass im Enteffekt etwas aehnliches rauskommen sollte.
Wenn ja, dann hast Du Teil a) gelöst.
Gut, zumindest theoretisch! Ich werd mich bei Gelegenheit mal dransetzen.
Nun habe ich mir überlegt das man dies doch auch mit HTML / CGI erledigen könnte.
Bestenfalls Schritt b) des Problems. Diesen halte ich für den weniger interessanten ...
Wohl wahr, wohl wahr! Terminologie war noch nie meine Staerke (und das bei Mathe-LK). Eigentlich sollte ich natuerlich Sagen: fuer die GUI HTML / CGI, als Sprache Perl.
Das verwandte Standardproblem hierzu ist meiner Meinung nach "Travelling Salesman" - darüber gibt es Literatur, die Du Dir mal ansehen solltest (Rekursion, Backtracking etc.).
Dachte ich mir schon fast: Meine Schule setzt ein aehnliches Programm zur Stundenplan-Erstellung ein. Der Lehrer wuerde mir bloss die Quelle geben...
Das ist *kein* ganz triviales Problem (ich habe das damals im 3. Semester gehört und bin nicht sicher, ob das heute bereits Abiturstoff ist).
Abiturstoff?? *G* Schoen, wenn es wenigstens nen Informatik-Grundkurs gaebe... Aber da gibts ja wichtigere Sachen... (wie nen Musik-LK mit 5 Leutchens...) Und dass es nicht ganz trivial ist, hatte ich mir schon gedacht.. <span style="self-irony:true">Sonst waere ich doch selbst drauf gekommen</span>
Es ist aber sehr lehrreich, weil es viele verwandte (NP-vollständige) Probleme gibt, für welche dieselbe Lösungstechnik anwendbar ist.
Wunderbar. Dann mal ran ... ;-)
Jetzt ist mir folgendes Problem bewusst geworden: Wie erstelle ich den Wochenplan, so dass er gültig ist, also jedem die gleiche Anzahl Stunden zuordnet, nich eine Person 8 Stunden am Stueck verkauft etc.
Das Problem ist das "etc" - das mußt Du schon exakt formulieren.
Schon klar, es ging mir ja auch nicht um fertige Loesungen, sondern nur um Hinweise: Ich will ja schon noch was selfer machen ;-)
Der Rest ist nicht so schwer, wenn Du das Backtracking (und die zugehörigen Datenstrukturen) fertig hast: Du brauchst eine Bewertungsfunktion, welche die Information liefert, ob die vorliegende Belegung "valide" ist oder nicht. (Am besten schon für Teil-Belegungen - dann kannst Du während der Tiefensuche frühzeitig Teilbäume abschneiden.)
Werde mich wohl ein wenig reinlesen muessen... BTW: Gibt es was dazu im Netz? In meinen Buechern ist nix zu finden... Sonst vielleicht auch ein Buchtip!
- Ist dies die beste Loesung? (Laesst sich so etwas "eleganter" loesen als mit einer Zufallszahl etc.)
Wie groß ist Dein Datenuniversum (wie viele Personen sind beteiligt etc.)?
ca. 60 Personen, drei Wochen, pro Person ca 20 Stunden. Nicht zu gross also.
Ich denke, mit heutigen Rechnern und einer halbwegs tauglichen Implementierung solltest Du den vollständigen Baum durchrechnen können, also nach der optimalen Lösung suchen und Zufallszahlen nicht verwenden.
Schoen. Man lernt ja nie aus!
- Braucht dieses Programm nicht viel Rechenzeit, da es so viele Schleifen durchlaufen muesste, bis es eine richtige Loesung findet?
Siehe oben.
Ich sehe keine sinnvolle Verwendung für CGI (was Deine verfügbare Rechenzeit massiv limitieren würde).
Okay. War wohl nix. Ich dachte, ich koennte das fuer den naechsten Jahrgang ins netz Stellen oder so... Dann ja wohl nur als Download.
Aber ein Perl-Skript, welches auf Deinem PC ggf. eine Nacht hindurch rechnet, sollte kein Problem darstellen - richtig?
Jep. Die Frage: Wie bringe ich das dann jedoch auf den Bildschirm? (Idee: Skript schreibt in Datei -> Anderes Skript liest Datei -> CGI an Browser (Yep, ich wills einfach drin haben...) als HTML. Richtig?)
Danke fuer deine Analyse, hat mir sehr weitergeholfen!
Gruss,
Einbecker
mfG - Michael