Interessante Aufgabe
-
Hallo Leute,
ich hatte vorige Woche ein Seminar zu Zeitmanagement, wir hatten eine Interessante Aufgabe zum Thema Prioritäten setzen.Wir sollten die Aufgabe mit Zettel und Papier lösen, nicht das Problem. Aber ich habe mich und den Schulungsleiter gefragt, ob man das Problem auch Programmtechnisch(mit Computer)lösen könnte, er verneinte es.
Aber wenn ich mir das so anschaue, ist das doch so ähnlich wie ein Navigationssystem - Algorithmus , bloss nicht auf Entfernungen bezogen,sondern auf Zeiten?http://viewmorepics.myspace.com/index.cfm?fuseaction=viewImage&friendID=139334914&imageID=1579105712
http://viewmorepics.myspace.com/index.cfm?fuseaction=viewImage&friendID=139334914&imageID=1579106185
Wenn man die Zeichnung sieht, die Zahlen an den Strichen sind Wegzeiten und in den Orten das sind Aufenthaltszeiten.
Um das Ergebnis nicht nur von dem erreichen der 2h abhängig zu machen, gibt es noch ein Punktsystem:
für alle erreichten "muss-ziele" gibt es 20Pkt
"kann-ziele" gibt es 10Pktfür jede Minute, die man im Krankenhaus sich aufhält (z.B. wenn man Zeit herrausgeholt hat) bekommt man Minuten*3Pkt und für den Park Minuten*2Pkt. der Bahnhof ist nur abgeben.
So, ehe jetzt einer wieder "Wolf" schreit, ich bin weder Schüler noch Student, ich bin Angestellter Programmierer und habe die Aufgabe interessant gefunden um sie eventl. mal softwaretechnisch zu lösen.
Zuerst wollte ich mit VB ran gehen, aber ich finde, das Problem schreit geradezu nach Zeigern,oder?
Nagut, jetzt lass ich es aus dem Sack, hat jemand eine Idee wie ich an die Sache rangehen kann ... bitte nicht zu kompliziert, ist wie gesagt nur, eine interssante Idee und sollt nicht mehr werden *lach*
Danke für Eure Hilfe.
Mfg Alex :xmas1:
-
Sicher ist sowas auch maschinell lösbar - im Zweifelsfall mit einer angepassten Breitensuche oder Tiefensuche. (den Entfernungsplan baust du als Graph auf, dann suchst du stückweise alle Wege durch diesen Graphen und bewertest, wie "gut" sie sind (und ob sie alle Randbedingungen erfüllen))
-
-
Hallo CStoll,
CStoll schrieb:
den Entfernungsplan baust du als Graph auf, dann suchst du stückweise alle Wege durch diesen Graphen und bewertest, wie "gut" sie sind (und ob sie alle Randbedingungen erfüllen))
ich komme mit dem Graphen nicht klar, wie meinst du das? Ich habe überlegt ob ich die Wege in eine Tabelle ablege, z.B. nummeriert:
1;Wohnung;5;5;Bank;5 (ID;Ort;Aufenthaltszeit;Wegzeit;Ort;Aufenthaltszeit) und dann
in der Zeile vermerken, welche Orte noch möglich sind:
ich baue es mal auf:
1;Wohnung;5;5;Bank;5;[2,3] <-- Wege die noch möglich sind von der Bank aus
2;Bank;5;2;Friseur;5 [...] <-- Wege die nooch möglich sind von dem Friseur aus
3;Bank;5;6;Passamt;3
.
.
.Und dann lass ich ALLES durchspielen und Bewerte dann die Zeiten, in C ist das ja von der Rechenzeit her unerheblich?
Wie ist die Idee?
Klar, ich habe die Randbedingungen nicht drin ... mhmmm
Gruss ALex
-
- Der Graph hat endlich viele Knoten und Kanten => es gibt nur endlich viele Möglichkeiten, wie du alle Knoten besuchen kannst => 'einfach' alle durchprobieren, und du findest die optimale Lösung
- Auch wenn es 'nur' endlich viele Lösungen sind, sind es doch extrem (!) viele.
Vielleicht klappts hier noch, weil der Graph ja nicht allzu groß ist, da bin ich mir aber unsicher. - Das Problem erinnert mich an eine Variation des Traveling Salseman Problem (TSP). Das ist NP-hart (d.h. man braucht mit dem Rechner nach aktuellem wissensstand unglaublich viel Zeit, um es exakt zu Lösen)
- Um solche Probleme näherungsweise zu Lösen, benutzt man meist irgendwelche Heuristiken auf dem Rechner (= schlaues Raten)
- Wenn man effiziente Lösungen für so ein Problem schaffen will, braucht man viel Graphentheorie und lineares Programmieren.