Software Denk Sport 3
 
StartSeite | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern

/Lösung


Zu Ehren von EdsgerDijkstra, der unter anderem den Algorithmus zum Finden des kürzesten Pfades in einem Graphen entwickelt hat und auf die Gefahren des GOTO so eindrucksvoll hingewiesen hat, möchte ich folgende Aufgabe in die SoftwareDenkSport Liste eintragen:

Beschreibung

Stellen wir uns mal vor, dass wir nicht den kürzesten Pfad zwischen zwei Knoten des Grafen suchen, sondern die "schnellste" Verbindung. Und dass wir statt einfach den Kanten zwischen den Knoten zu folgen, nur die "Bahn", die zwischen den Knoten fährt, benutzen dürfen. Beim Umsteigen müssen wir in einem Knoten so lange warten, bis der nächste Zug kommt.

Als Eingabe haben wir einen Fahrplan aller "Züge", die zwischen den Knoten regelmäßig fahren. (Um die Aufgabe einfacher zu machen, gehen wir davon aus, dass der Fahrplan für jeden "Tag" der gleiche ist.)

Beispiel:

Zug 1:

KnotenZeit
A0.1
B0.3
C0.8
D0.9
E1.2

Die Zeit ist in Tagen eingegeben. Die 1.2 beim Knoten E bedeutet, dass der Zug, der heute um 0.1 startet, E morgen um 0.2 erreicht. Inzwischen startet in A (morgen um 0.1) der nächste Zug.

Aufgaben

  1. Entwickle einen Algorithmus, mit dem man für einen definierten Startknoten und Startuhrzeit die schnellste Zugverbindung zum definierten Zielknoten gefunden wird. (Also eine, mit der man den Zielknoten am schnellsten erreicht.)
  2. Zeit ist Geld. Jede Stunde, die wir unterwegs sind, kostet uns Ph, jeder gefahrene Kilometer kostet uns Pkm. Für bestimmte schnelle Züge muss man einen Zuschlag zahlen (der Zuschlag kostet einen festen Betrag für die komplette Reise). Entwickle einen Algorithmus, mit dem man für einen definierten Startknoten und Startuhrzeit die billigste Zugverbindung zum definierten Zielknoten gefunden wird.
Beispiel:

Zug 1, Preis/km: 0.1 $, Zuschlag: D-Zug (10 $)

KnotenZeitkm
A0.10
B0.3200
C0.8700
D0.9750
E1.21000

Fragen

Zur ersten Aufgabe eine Beispielfrage: Wenn zwei Züge gemäß der Pläne ...

Zug 1:
KnotenZeit
A0.1
B0.3
C2.8

Zug 2:
KnotenZeit
B0.2
C1.3

... fahren, und meine Aufgabe ist, vom Startzeitpunkt 0 (Null) von A nach C zu gelangen, dann ist die gesuchte Lösung also "(Knoten=A/Zeit=0), Warte 0.1 auf Zug 1 (Knoten=A/Zeit=0.1), Zug 1 bis B (B/0.3), Warte 0.9 auf Zug 2 (B/1.2), Zug 2 bis C (C/2.3)", d. h. schnellste Zugverbindung = 2.3?

JA, das ist die schnellste Verbindung. In der ersten Aufgabe geht es darum, die Verbindung zu finden, mit der man am frühesten den Zielknoten erreicht. (Dies hängt auch von der Anfangszeit an, denn die Wartezeit im Anfangsknoten zählt, wie alle Wartezeiten, auch mit) -- GregorRayman

Für "meine Ressourcen" schätze ich (wobei ich mich täuschen kann) die Schwere der Aufgabe auf viele Stunden (wenn nicht Tage) Nachgrübeln/Herumprobieren/Recherchieren ein (natürlich ohne Ergebnisgarantie). Bin momentan anderweitig ausgelastet. Anders gesagt: Dezeit zu schwer für mich. Tut mir leid. -- VolkerGlave


F: Welche Form soll eine Lösung haben?
A: Eine klare Beschreibung des Algorithmus am bestem mit einem einfachen Beispiel. Pluspunkte gibt es für einen Beweis.

F: Was ist das Kriterium für die Qualität der Lösung?
A: Dijkstras Algoritmus ist O(n2) (wo n die Anzahl der Knoten ist) für einen Startknoten und alle Zielknoten. Ich glaube, geeignetes Kriterium wäre auch die Effizienz. Sekundäres Kriterium ist die Einfachkeit der Erklärung (je einfacher, desto besser). Falls andere Kriterien erwünscht sind, meldet Euch schnell.

F: Wann startet und endet diese Denksportrunde?
A: Start: Jetzt. Ende: Mal sehen, wie schnell die Lösungen kommen. Wie wäre es mit 15.09.2004?

Lösungen bitte nicht hier veröffentlichen. Schickt sie mir einfach per Mail MAIL rayman(a)grayman.de?subject=Denksport. Ich werde sie dann nach Schluß veröffentlichen.

F: Sollen wir die Aufgabe außerhalb des DseWiki (etwa in den einschlägigen Programmier-newsgroups) ankündigen?
A: Ich habe nichts dagegen. Im Gegenteil.

F: Wird es Testdaten bzw. einen Syntaxvorschlag für Testdaten, Lösungsdaten, Zugbenennung und Knotenbenennungen jenseits von Z geben?
A: Eigentlich geht es um eine Beschreibung eines Algoritmus. Eine Implementierung ist nicht erfordelich, wenn die Beschreibung klar ist. Ein Beweis wird hoch geschätzt. Aber natürlich, wenn mehrer Leute gleich gute Algorithmen präsentieren, kann eine Implementierung beim Zielfoto :-) entscheiden. Deswegen ist die Idee mit einem Testdatenformat gut.

Hier mein Vorschlag: Die Testdaten sollten in der SpracheYaml in folgender Form verwendet werden:

Züge: 
  - Zug 1
    fahrplan:
      - {knoten: A, zeit: 0.1, entfernung: 0}
      - {knoten: B, zeit: 0.4, entfernung: 15}
    preis: 0.2 // preis pro km
    zuschläge: [D-Zug, Sonderzuschlag_1]  // alle Zuschläge müssen bezahlt werden
Zuschlagspreise: {D-Zug: 10, Sonderzuschlag_1: 30, Sonderzuschlag_2: 20}

F: Wie weit geht die Zeitskala (für reale Implementierungen, *.23 oder *.9 ?) ?

A: Damit es einfacher wird, sagen wir, dass 1 ein Tag ist. Da es für den Algoritmus nicht relevant ist, wie genau wir die Zeit messen, reicht es, wenn der Tag in 256 Einheiten geteilt wird.

Autsch, das scheint mir alles sehr kompliziert. IMHO sollte das Knotennetz mit den Entfernungen getrennt von den Zügen definiert sein (kann natürlich im gleichen File sein), z. B.

   # Knoten:
   A(, optionale Knoteneigenschaften) # optionale Kommentare
   B
   C
   # Strecken:
   A-B, entfernung: 15, (,weitere optionale Streckeneigenschaften)
   A-C,
   ....

# Züge: 1, fahrplan: A0.1-B0.5-C0.8-D1.4, zuschläge: ...(,weitere optionale Zugeigenschaften) 2, fahrplan: A0.3-C0.6-E0.9, zuschläge

# Aufgaben: A0.0E? # wann kann ich frühestens in E sein A?D0.5 # wann muss ich in A starten um rechtzeitig in D zu sein ?0.0D1.0 # von wo aus kann ich D innerhalb von 1 Tag erreichen A0.0?2.0 # wohin kann ich innerhalb von 2 Tagen fahren.

# Fahrstrecken: 1:A0.1-C0.8/2:C1.6-E1.9 (, preis: ..., fahrdauer: ..., streckenlänge: ...)

Und die Zeit sollte einfach ein dezimaler Wert [Tage] sein.

-- HelmutLeitner

Meinetwegen. SpracheYaml habe ich nur deswegen vorgeschlagen, damit man nicht selber einen Parser schreiben muss, weil es für viele Sprachen bereits einen gibt. Was die Trennung der Strecken von Zügen angeht: Prinzipiell richtig, denn wenn man die Entfernungen bei den Zügen speichert, werden viele redundanten Daten gespeichert. Allerdings muss bei der getrennten Speicherung dann die Strecke bei den Zügen auch für die Knoten gespeichert werden, in denen der Zug nicht hält. Wenn es also die Strecken A-B, A-C, B-D und C-D gibt, muss bei einem Zug, der von A nach D ohne zu halten fährt, spezifiziert werden, dass er z.B. durch B fährt. (Eigentlich geht es hier überhaupt nicht um die Entfernungen, nur um die Preise)

Die erweiterten Aufgaben finde ich schön. -- GregorRayman


Von mir abschließend der Hinweis, dass die Aufgabe nicht akademisch ist. Ich habe mit ein paar Kollegen tatsächlich mal soetwas für die Bahn AG programmiert. War natürlich ein bisschen komplizierter, wir mussten das nicht auf Basis von Strecken sondern gleisgenau betrachten. -- SDö


StartSeite | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern
Text dieser Seite ändern (zuletzt geändert: 18. November 2004 13:54 (diff))
Suchbegriff: gesucht wird
im Titel
im Text