#1 8. Oktober 2010 Uni Stundenplan optimieren Hi! Für diesen Thread gibt es vielleicht kein passendes Forum, aber ich denke, dass mir hier am ehesten geholfen werden kann, da es eigentlich eher um ein mathematisches Problem geht, welches ich mithilfe von einer Programmiersprache angehen will. Die Sprache ist hierbei eher irrelevant, deshalb das Code Präfix. Das Problem ist folgendes: Ich will ein Programm/Script schreibe, in dem ich alle meine Vorlesungszeiten und die zugehörigen Seminare/Übungen/Tutorien eintragen will (mit Raum, Dozent, etc.). Nun sind die Vorlesungszeit fest vorgegeben, die Übungen hingegen haben oft mehrere Termine. Das Programm/Skript soll anschließend den besten Stundenplan ausgeben. Dabei will ich diesen nach bestimmten Kriterien auswählen. Diese sind z.B. wenige Freistunden früh Schluss spät anfangen einen Tag frei ... Nun weiß ich nicht genau, wie ich das realisieren kann. Ich hatte mir vorgestellt, dass ich zuerst die Vorlesungszeiten eintrage und dann alle Kombinationen der Übungen ausprobiere und jeweils schaue, welches Kriterium ich erfüllen kann. Dies ist aber die Bruteforce Methode, die ggf. sehr lang dauern kann. Also würde ich den Studenplan am liebsten so optimieren, dass meine gewünschten Kriterien bestmöglich abgedeckt werden, wobei evtl nicht alle Kriterien erfüllt werden können. Habt ihr so etwas schon einmal probiert oder standet vor einem ähnlichen Problem? Also mir fällt nur Bruteforce oder eine Art Backtracking ein. Bei Backtracking kann man aber eigentlich nur nach einem Kriterium gehen und schauen ob es möglich ist dies umzusetzen. greez + Multi-Zitat Zitieren
#2 8. Oktober 2010 AW: Uni Stundenplan optimieren Spontan würd ich sagen, dass das ganze irgendwie mittels matching lösbar ist, also insgesamt mit Graphen etc - aber gibt bestimmt auch bessere Wege. http://en.wikipedia.org/wiki/Matching_(graph_theory) Aber ich frag mich eher - es ist ja nur nen Stundenplan. Dort nen Bruteforce zu machen geht schneller, als sich "in was neues" rein zu denken. Ist halt die Frage, ob es dir um die Technik, oder um das Resultat geht. Edit: Du kannst das ganze auch z.B. mittels Dijkstra machen (kürzester Weg im Graph) - du musst deine Gewichte den Kanten dann halt setzen, oder mehrere Gewichtungen wählen - danach könntest du Auswählen, nach welchem Gewicht (z.b. Gewichtet nach freien Tagen) es sortieren soll. Und dann musst du halt individuell für dich persönlich die beste der besten Gewichtungen auswählen + Multi-Zitat Zitieren
#3 8. Oktober 2010 AW: Uni Stundenplan optimieren joa... da gibt es noch weitere ansätze (z.b. greedy, genetische algorithmen), aaaber IMHO geht das optimieren im kopf wesentlich besser (und auch schneller) alle termine in nen stundenplan eintragen, die termine markieren, die fest sind und dann ein bisschen herumprobieren. dauer: 10min (mit eintragen) bis du das ganze per algo nachgebildet hast, bist du schon 100 mal auf dem papier fertig... wenn es dir aber um die übung geht, dann nimm nen bruteforce algo. die möglichkeiten sind ja relativ beschränkt. wenn du 30 mögliche "slots" für vorlesungen hast, dann musst du max. 155 millionen kombinationen durchgehen, wenn du nun die "festen" termine hinzunimmst, dann hast du vll. 20 mögliche slots, was dazu führt, dass du nur noch max. 184k möglichkeiten hast. (ich hoffe, ich habe mich net verrechnet) von daher ist bruteforce kein problem... + Multi-Zitat Zitieren
#4 8. Oktober 2010 AW: Uni Stundenplan optimieren Ja also das was du als Bruteforce bezeichnest, sprich alle Möglichkeiten ausprobieren wäre bei diesem rel. einfachen Problem denke ich die sinnvollste Lösung, weil es nicht soviele Möglichkeiten geben wird, dass ein moderner Rechner sonderlich lange dafür brauch. Wenn du den ganzen Kram komplett mathematisch aufbauen willst, brauchst du denke ich rel. lange um erstmal das Grundgerüst zu coden oder du benutzt z.B. Matlab, wo du schon viele mathematischen Funktionen effizient implementiert hast, dich allerdings erst einarbeiten musst. Einfallen würde mir da z.b. ein lineares Problem, dass du dann mit dem Simplex Algorithmus löst. Wobei ich grade nicht 100 prozentig sicher bin, ob man diese Problemstellung in ein lineares Modell überführen kann. Hier evtl. ein paar Denkanstöße: -Deine Nebenbedingungen wären die Rahmenbedingungen, also wann welche Übungen sind und wann die Vorlesungen sind (wie du sie dann tatsächlich mathematisch formulierst musst du selber schauen). -Die Maximierung- bzw. Minimierungsfunktion passt du dann nurnoch, je nach gewünschter Optimierung an(min. Freistunden, möglichst Spät anfangen, etc) Allerdings glaube ich nicht das du das so ohne weiteres in einfaches lineares Problem mit reellen Variablen überführen kannst. Und Eines mit natürlichen Variablen ist schon deutlich schwieriger zu lösen. Wenn du dich dafür sowieso interessierst, dann kannst du es ja versuchen, wenn es dir allerdings nur um eine funktionale einfache Implementierung für diese eine Problemstellung geht, wo du dich nicht noch in diverse Sachen einarbeiten möchtest, würde ich mich für die "Bruteforce" Methode entscheiden. Das sollte man denke ich sogar in Excel mit dem Solver hinkriegen können. + Multi-Zitat Zitieren
#5 8. Oktober 2010 AW: Uni Stundenplan optimieren Ich kenne Dijkstra und auch mit Graphen bin ich sehr gut vertraut. Jedoch denke ich, dass die Lösung mit Graphen doch sehr umständlich ist. Dennoch danke, für die Idee Dass Bruteforce bei diesem Problem kein großes Problem darstellt, ist mir durchaus bewusst. Dennoch wollte ich es ein wenig eleganter lösen und deshalb hatte ich hier nachgefragt. Es ist mir auch klar, dass es mit Papier und Stift viel schneller geht. So habe ich es schließlich bisher gemacht. Ich habe aber eine große Beigeisterung für technische Lösungen entwickelt und wollte daher dieses Problem eher automatisch lösen lassen. Die Idee kam mir, als ich mir ein Tool schreiben wollte, mit dem ich einfach einen Stundenplan erzeugen lassen kann, ich dem ich nur die Stunden eintrage und gut ist. @BuBi88D: Danke auch für den Hinweis des Simplex Alogs. Auch diesen kannte ich bereits, jedoch schien auch der mir zu aufwendig für die Aufgabe. Es gibt sicher noch ein paar Möglichkeiten, mit denen ich die Anzahl der Permutationen einschränken kann. Auf jeden Fall kann man Übungen ausschließen, die zeitgleich mit einer Vorlesung sind usw. Falls jemand noch recht einfache Lösungsvorschläge hat, die dennoch elegant sind, dann kann er sich ja hier melden. Ansonsten werde ich bald versuchen die ganze Sache mit der Methode aller Permutationen abzubilden. greez + Multi-Zitat Zitieren
#6 8. Oktober 2010 AW: Uni Stundenplan optimieren Ich find die Sache auch recht interessant.. Falls du was zu stande gebracht hast, wäre es super, wenn du mir mal ne PM schickst Danke.. + Multi-Zitat Zitieren
#7 8. Oktober 2010 AW: Uni Stundenplan optimieren Kann den Gedanken mal bitte jemand zuende denken, ich bin geistig nicht mehr fit: Ich denke (bzw. hab im Urin) dass sich Dein Problem auf das Rucksackproblem zurückführen lässt. Du kannst ja dir alle Übungen mit Gewichten vorstellen, die angeben, wie gut dieser Termin ist und Du hast eine feste Anzahl an Plätzen zu vergeben und willst die Gewichte maximieren. Passt jetzt nicht vollends, aber daher meine Überlegung. Nun ist es so, dass das Rucksackproblem NP-vollständig ist. Daher wirst Du nicht in der Lage sein, die Laufzeit signifikant gegenüber Brute-Force zu senken. Halt frickeln mit Heuristiken etc., aber weniger elegant. + Multi-Zitat Zitieren
#8 9. Oktober 2010 AW: Uni Stundenplan optimieren Sollte (leider) so hinhauen, wie Du gesagt hast. Hab erst an Sequenzing with Intervals gedacht, aber man braucht ja nicht alle Übungen drin haben, somit ist Dein Ansatz besser ;-) Ist aber auch noch zu früh oder schon zu spät, um mir da richtig Gedanken drum zu machen...hab schon viel davon verdrängt Aber die Idee zu so einem Programm finde ich auch reizvoll...muss ja in der Schule früher auch was dafür gegeben haben ;-) *mal darüber meditieren ich werde* MfG Basti1086 + Multi-Zitat Zitieren
#9 9. Oktober 2010 AW: Uni Stundenplan optimieren Ist das vom prinzip nicht genauso, wie das Stundenplan-in-der-Schule-Problem? Soweit ich mich ans letzte Semester erinnert soll man da am besten "Finite Domain Constraint Logic Programming" - also Logische Programmierung mit Constraints und endlichen Wertebereichen- für solche Probeme nutzen. Das ist z.B. mit Prolog möglich. Frag mich jetzt aber nicht nach Beispielcode, ich glaube so genau sind wir in die Stundenplanerstellung auch nicht gegangen. Aber nen Problem aus dem Bereich ist das 8(n)-Damen-Problem, da kannste dir schonmal grob anschauen, wie das mit dem FD-CLP in etwa läuft + Multi-Zitat Zitieren