/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:

Knoten Zeit A 0.1 B 0.3 C 0.8 D 0.9 E 1.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 $)

Knoten Zeit km A 0.1 0 B 0.3 200 C 0.8 700 D 0.9 750 E 1.2 1000

Fragen

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

Zug 1:

Knoten Zeit A 0.1 B 0.3 C 2.8

Zug 2:

Knoten Zeit B 0.2 C 1.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

A: Eine klare Beschreibung des Algorithmus am bestem mit einem einfachen Beispiel. Pluspunkte gibt es für einen Beweis.

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.

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.

A: Ich habe nichts dagegen. Im Gegenteil.

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.

   # 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: ...)

-- 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