nicht angemeldet
Hi,
Ich möchte ein CGI-Perl-Skript schreiben, dass einen Wochenplan erstellt.
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".
Ich habe die Schicht-Pläne immer per Hand ausgearbeitet, was ein Haufen Arbeit war (sehen, dass jeder gleich viel Stunden hat, Leute zusammensusetzen, die miteinander "gut koennen", insgesamt 63 Leute mit unterschiedlichen möglichen Zeiten verwalten etc.).
Kannst Du Dein manuelles Verfahren in Form von Einzelschritten formulieren?
Kannst Du garantieren, daß es sowohl terminiert als auch eine korrekte Lösung der Aufgabe liefert?
Wenn ja, dann hast Du Teil a) gelöst.
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 ...
Ich habe ein Formular erstellt, das mehrere Sachen abfragt: Name der Orte, Zeit der einzelnen Schichten, Anzahl der Schichten pro Tag etc. Ferner wird nach einer Text-Datei gefragt, die als CSV eine Tabelle enthaelt, wann die Leute koennen, mit wem Sie nicht verkaufen, die Namen etc, und die dann ja auch ins Skript eingelesen werden kann.
Ich denke, ich habe die Datenstruktur halbwegs verstanden.
Das verwandte Standardproblem hierzu ist meiner Meinung nach "Travelling Salesman" - darüber gibt es Literatur, die Du Dir mal ansehen solltest (Rekursion, Backtracking etc.).
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). Es ist aber sehr lehrreich, weil es viele verwandte (NP-vollständige) Probleme gibt, für welche dieselbe Lösungstechnik anwendbar ist.
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.
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.)
Meine (theoretische) Ueberlegung war: Durch eine Zufallszahl wird bei einiger beliebigen Person angefangen, bis alle Schichten vergeben sind. Falls dies "aufgeht", also kein Fehler auftritt, wird das Ergebnis zurueckgegeben, andernfalls mit einer anderen Zahl fortgesetzt.
- 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.)?
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.
- 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).
Aber ein Perl-Skript, welches auf Deinem PC ggf. eine Nacht hindurch rechnet, sollte kein Problem darstellen - richtig?
mfG - Michael