15.2.1 Pfadfinder



next up previous
Weiter: 15.2.2 Hoch: 15. BWINF 2. Runde Zurück: Allgemeine Hinweise 2. Runde

15.2.1 Pfadfinder

Ein häufiges Alltagsproblem ist es, in einem Verkehrsnetz die schnellste Verbindung zwischen zwei Punkten zu finden. Bei mittlerer Komplexität des Netzes und einer graphischen Übersicht lösen die meisten Menschen diese Aufgabe ohne Schwierigkeiten; für den Computer ist die Sache schon deutlich komplizierter.

In dieser Aufgabe betrachten wir einen vereinfachten Ausschnitt des Londoner U-Bahn-Netzes mit 50 Bahnhöfen und sieben Linien:

Oder der gleiche Ausschnitt in Farbe.

Die Linien und ihre Bahnhöfe sind in der nachfolgenden Liste enthalten, wobei Umsteigebahnhöfe durch einen Stern hinter dem Namen gekennzeichnet sind. Wer die Liste nicht abtippen möchte, aber Zugang zum Netz hat, kann sie sich hier herunterladen.

Zur Bestimmung der schnellsten Verbindung legen wir die folgenden vereinfachenden Annahmen zugrunde:

  1. der Weg von einem Bahnhof zum nächsten dauert immer genau eine Minute; der Aufenthalt im Bahnhof dreißig Sekunden,

  2. ein Umsteigevorgang dauert immer eine genau festgelegte Zeit, die von Wochentag, Tageszeit, sportlicher Fitneß etc. abhängt.

Schreiben Sie ein Programm, welches nach Eingabe der festen Umsteigezeit und zweier Bahnhöfe aus der Liste eine genaue Beschreibung der schnellsten Verbindung (Namen der Linien und passierte Bahnhöfe) ausgibt. Wenn es mehrere gleich schnelle Verbindungen gibt, sollen diese alle ausgegeben werden. Senden Sie mehrere Beispielausgaben ein, darunter auch je eine für die drei Verbindungen Gloucester Road nach King's Cross, Leicester Square nach Baker Street und Paddington nach Bond Street; legen Sie dabei eine Umsteigezeit von drei Minuten zugrunde.

BAKERLOO:
        Embankment*
        Charing Cross*
        Piccadilly Circus*
        Oxford Circus*
        Regent's Park
        Baker Street*
        Marylebone
        Paddington*

CENTRAL:
        Notting Hill Gate*
        Queensway
        Lancaster Gate
        Marble Arch
        Bond Street*
        Oxford Circus*
        Tottenham Court Road*
        Holborn*
        Chancery Lane
        St. Paul's
        Bank/Monument*
        Liverpool Street*

CIRCLE:
        Notting Hill Gate*
        Bayswater
        Paddington*
        Edgeware Road
        Baker Street*
        Great Portland Street
        Euston Square
        King's Cross/St. Pancras*
        Farringdon
        Barbican
        Moorgate
        Liverpool Street*
        Aldgate
        Tower Hill
        Bank/Monument*
        Cannon Street
        Mansion House
        Blackfriars
        Temple
        Embankment*
        Westminster
        St. James's Park
        Victoria*
        Sloane Square
        South Kensington*
        Gloucester Road*
        High Street Kensington
        Notting Hill Gate*

JUBILEE:
        Charing Cross*
        Green Park*
        Bond Street*
        Baker Street*

NORTHERN:
        Embankment*
        Charing Cross*
        Leicester Square*
        Tottenham Court Road*
        Goodge Street
        Warren Street*
        Euston*

PICCADILLY:
        Earl's Court
        Gloucester Road*
        South Kensington*
        Knightsbridge
        Hyde Park Corner
        Green Park*
        Piccadilly Circus*
        Leicester Square*
        Covent Garden
        Holborn*
        Russel Square
        King's Cross/St. Pancras*

VICTORIA:
        Victoria*
        Green Park*
        Oxford Circus*
        Warren Street*
        Euston*
        King's Cross/St. Pancras*




Mon Dec 16 11:47:49 MET 1996