nicht angemeldet
+(Perl) Skript zur Erstellung eines Wochenplanes
Moin,
Folgendes technische Problem stellt sich mir:
Ich möchte ein CGI-Perl-Skript schreiben, dass einen Wochenplan erstellt.
______
Hintergrund:
Unser Abijahrgang organisiert einen Losverkauf, um unsere Jahrgangskasse aufzubessern. Wir sagen, jeder muss ca. 21 h Lose verkaufen. 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.). Nun habe ich mir überlegt das man dies doch auch mit HTML / CGI erledigen könnte.
______
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.
______
Problem:
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. 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.
Ich als relativer Perl-Neuling frage mich jetzt:
1. Ist dies die beste Loesung? (Laesst sich so etwas "eleganter" loesen als mit einer Zufallszahl etc.)
2. Braucht dieses Programm nicht viel Rechenzeit, da es so viele Schleifen durchlaufen muesste, bis es eine richtige Loesung findet?
Ich mache dies aus Spass an der Freude, es interessiert mich einfach. Die Plaene habe ich alle schon per Hand erledigt :*-(
Waere nett, wenn irgendjemand mir dies erklaeren koennte...
Danke im Vorraus!
Gruss,
Einbecker
p.s. fuer regional Interessierte: Es handelt sich um das Eulenfest, das naechstes Wochenende stattfindet. Kommt einfach mal vorbei, und kauft auch ein paar Lose! ;-)
pp.s. Danke, falls ihr bis hier hin gelesen habt!
-
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
-
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
-
Hi,
dass ich auch noch schauen kann, wer zu wem "passt".
dies wäre exakt zu definieren und wird dann Bestandteil der erwähnten Bewertungsfunktion.
Dies koennte ich ja auch mittels einer Uebergabe eines Sympathie-Wertes loesen, so dass im Enteffekt etwas aehnliches rauskommen sollte.
An dieser Stelle gibt es verschiedene Ansätze:
a) eine Sympathie-Funktion liefert Dir eine optimierbare Bewertungszahl.
b) eine Boolean-Matrix würde weniger genaue Werte liefern, aber viel schneller zum Abbruch der Tiefensuche führen.Dachte ich mir schon fast: Meine Schule setzt ein aehnliches Programm zur Stundenplan-Erstellung ein. Der Lehrer wuerde mir bloss die Quelle geben...
Stundenplanberechnung ist zwar auch NP-vollständig, würde ich denken, aber das korrespondierende Problem ist eher das Knapsack-Problem. (Hm, vielleicht auch für Deinen Fall ...)
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!
Wir haben damals (1981) Nikolaus Wirth, "Algorithmen und Datenstrukturen" verwendet. (Das ist der Erfinder von PASCAL und MODULA, überhaupt der Papst für gut erlernbare Programmiersprachen und einer meiner persönlichen Gurus. (Yes, I'm a quiche eater.)
Für die Beispiele wird im Zweifelsfalle PASCAL verwendet, es wird m. E. aber nichts vorausgesetzt, was in Perl nicht auch ginge.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.Für die Online-Verfügbarkeit brauchst Du doch keine dynamische Berechnung Deiner Ergebnisse, oder? Es reicht doch, wenn Dein Programm statische HTML-Seiten erstellt ...
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?)
Erstes Skript generiert direkt HTML als Datei und fertig ...
mfG - Michael
-
Moin,
Dachte ich mir schon fast: Meine Schule setzt ein aehnliches Programm zur Stundenplan-Erstellung ein. Der Lehrer wuerde mir bloss die Quelle geben...
Stundenplanberechnung ist zwar auch NP-vollständig, würde ich denken, aber das korrespondierende Problem ist eher das Knapsack-Problem. (Hm, vielleicht auch für Deinen Fall ...)
Vielleicht habe ich mich unklar ausgedrueckt: Es geht um einen Einsatzplan (Vgl: Stundenplan), jedoch mit der Hinzunahme von Sympathiefunktion und gewisser Regeln. Daher sehe ich keinen grossen Unterschied zwischen Stundenplan-Erstellung und unserem Problem. Ich werde mich auf alle Faelle mal einlesen...
Wir haben damals (1981) Nikolaus Wirth, "Algorithmen und Datenstrukturen" verwendet. (Das ist der Erfinder von PASCAL und MODULA, überhaupt der Papst für gut erlernbare Programmiersprachen und einer meiner persönlichen Gurus. (Yes, I'm a quiche eater.)
Gut, werde ich mir mal anschauen. Vielleicht gibt es ja auch was vergleichbares, das Perl verwendet, ist aber ja im Endeffekt auch egal.
Für die Beispiele wird im Zweifelsfalle PASCAL verwendet, es wird m. E. aber nichts vorausgesetzt, was in Perl nicht auch ginge.
Gut, Argument!
Für die Online-Verfügbarkeit brauchst Du doch keine dynamische Berechnung Deiner Ergebnisse, oder? Es reicht doch, wenn Dein Programm statische HTML-Seiten erstellt ...
Der naechste Jahrgang wird wieder einen Stundenplan erstellen muessen, ich dachte einfach, dass es moeglich waere, es auf einen Server zu stellen, um es Leuten, die aehnliche Probleme haben, anzubieten. Es bleibt natuerlich, wie gesagt, die Moeglichkeit des Downloads!
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?)
Erstes Skript generiert direkt HTML als Datei und fertig ...
Da ist dann aber kein CGI drin (heul) obwohl ich das doch so gern wollte...
*G* Ja, ich bin ein komplexer Denker ;-) Warum auch einfach, wenn...
Danke, ich werd mir bei Zeiten mal da etwas reinhaengen!
Gruss,
Einbecker
-