Suche Home Einstellungen Anmelden Hilfe  

Standardalgorithmen
 
  
Anfang
vor
  

3.2 Das Königsberger Brückenproblem

In der Innenstadt von Königsberg vereinen sich der Alte und der Neue Pregel zum Pregelfluß. Im 18. Jahrhundert führten 
sieben Brücken über die Flußläufe, die die verschiedenen Stadtteile miteinander verbanden. 
 
 

Gibt es einen Weg, der genau einmal über jede Brücke und dann zurück zum Standort führt? 
 

  
Anfang
vor
zurück
  

3.2.1 Lösungsidee

Beantworten läßt sich die Frage, indem systematisch alle Varianten ausprobiert werden. Laut Problemstellung darf jede Brücke 
nur einmal überquert werden. Ausgehend von einem beliebigen Standort werden nacheinander alle noch zur Verfügung 
stehenden Brücken getestet. Vom neu erreichten Stadtteil aus werden wiederum alle noch begehbaren Brücken überquert. 
Kommt man zu einem Stadtgebiet, von wo aus nicht mehr weiter gegangen werden kann und die Brücken wurden noch nicht 
alle überquert sind, so muß ein Schritt zurückgegangen werden und eine andere Brücke gewählt werden. Steht keine andere 
Brücke mehr zur Verfügung, muß noch ein Schritt zurückgegangen werden, usw. 

Es deutet sich eine rekursive Lösung des Problems an, was Überlegungen zur Terminationen aufwirft. Da sieben Brücken 
vorhanden sind und jede Brücke nur einmal überquert werden darf, ist die Rekursionstiefe nie größer als sieben. Mit jeder 
Brückenüberquerung verringert sich die noch zu testende Menge von Varianten um Eins. Der Algorithmus terminiert, wenn 
entweder eine Lösung gefunden wurde oder alle denkbaren Lösungswege nicht zum Erfolg geführt haben. Dementsprechend 
gibt es eine oder keine Lösung für das Problem. 
 

  
Anfang
vor
zurück
  

3.2.2 Phasen der Modellierung

3.2.2.1 Darstellungsformen

In erster Überlegung werden die Varianten in Form eines Baumes dargestellt. Dazu werden die Brücken durchnumeriert. 
 
 

Anschließend muß ein Stadtteil als Startpunkt ausgewählt werden. Der Lösungsbaum beschreibt die Möglichkeiten des 
Überquerens der Brücken nach Problemstellung. Hier wird ein kleiner Auszug des Lösungsbaumes dargestellt. 
 

Die Darstellung des Graphen zeigt alle Varianten der Übergänge von einem Stadtteil in einen anderen. 
 

Die Modellbildung wird noch weiter verfolgt. Es ist nicht notwendig zu wissen, welche Brücke bereits passiert wurde.Wurde 
eine der Brücken überschritten, so steht sie nicht mehr zur Verfügung. Wird dieser Gedanke auf die Stadtteile übertragen, so 
muß lediglich protokolliert werden, wie oft von Stadtteil zu Stadtteil gewechselt wurde. Wurde beispielweise vom Nordteil zur 
Insel gegangen, dann steht anschließend nur noch einmal der Weg zwischen Insel und Nordteil zur Verfügung. Diese Abstaktion 
ermöglicht das Aufstellen folgender Übersicht. 
 
 

nach 

von

Nord
Süd
Ost
Insel
Nord
0
0
1
2
Süd
0
0
1
2
Ost
1
1
0
1
Insel
2
2
1
0
Diese Tabelle legt die zu verwendene Datenstruktur nahe. 
 
  
Anfang
vor
zurück
  

3.2.2.2 Datenstruktur

Die dargestellte Form impliziert ein zweidimensionales Feld. Die enthaltenen Informationen genügen für die Ermittlung der 
Lösung. Aufgeführt sind die noch zur Verfügung stehenden Brückenüberquerungen zwischen den Stadtteilen. Wurde eine 
Brücke überquert, muß die entsprechende Anzahl um Eins reduziert werden. 

Im Deklarationsteil werden folgende Vereinbarungen getroffen: 

     CONST ANZAHL = 7; 

     TYPE 

          tStadtteile = (Pregel, Nord, Sued, Ost, Insel); 
          tBrueckenplan = ARRAY [Nord..Insel,Nord..Insel] OF shortint; 
          tStrecke = RECORD 

               Weg : ARRAY[1..ANZAHL] OF tStadtteile; {zurückgelegter Weg} 
               wievielte : integer; {Wievielte Brücke ?}  

          END; 

Neben den bekannten Stadtteilen wird ein weiterer Stadtteil für die Initialisierung (hier Pregel) benannt. Der Typ tStrecke 
repräsentiert die zurückgelegte Wegstrecke (Weg) und die Anzahl der überquerten Brücken (wievielte). 
 

  
Anfang
vor
zurück
  

3.2.2.3 Das Struktogramm

 
 
  
Anfang
vor
zurück
  

3.2.3 Das Programm

     PROGRAM KoenigsbergerBrueckenproblem; USES crt; 
     CONST 

          ANZAHL = 7; 

     TYPE 

          tStadtteile = (Pregel, Nord, Sued, Ost, Insel); 
          tBrueckenplan = ARRAY [Nord..Insel,Nord..Insel] OF shortint; 
          tStrecke = RECORD 
          Weg : ARRAY[1..ANZAHL] OF tStadtteile;{zurückgelegter Weg} 
          wievielte : integer; {Wievielte Brücke ?} 
          END; 

     VAR 

          Brueckenplan : tBrueckenplan; 
          Strecke : tStrecke; 
          Startpunkt : tStadtteile; 
          Loesung : boolean; {stellt mögliche Lösung fest}  

In der Prozedur InitialisiereBrueckenplan wird die Brückenverteilung festgeschrieben. Die globale Feldvariable Brückenplan 
übergibt das Feld an die Prozedur, welches hier neu beschrieben wird. 

     PROCEDURE InitialisiereBrueckenplan (VAR Bruecken : tBrueckenplan); 
     BEGIN 

          Bruecken[Nord, Nord] := 0; 
          Bruecken[Nord, Sued] := 0; 
          Bruecken[Nord, Ost] := 1; 
          Bruecken[Nord, Insel] := 2; 
          Bruecken[Sued, Nord] := 0; 
          Bruecken[Sued, Sued] := 0; 
          Bruecken[Sued, Ost] := 1; 
          Bruecken[Sued, Insel] := 2; 
          Bruecken[Ost, Nord] := 1; 
          Bruecken[Ost, Sued] := 1; 
          Bruecken[Ost, Ost] := 0; 
          Bruecken[Ost, Insel] := 1; 
          Bruecken[Insel, Nord] := 2; 
          Bruecken[Insel, Sued] := 2; 
          Bruecken[Insel, Ost] := 1; 
          Bruecken[Insel, Insel] := 0; 

     END 

Die Prozeduren SchreibeStadtteil und die Prozedur SchreibeStrecke dienen der Anzeige der Brückenüberquerungen. 
SchreibeStadtteil wird aufgerufen, um den Startpunkt auszugeben. Außerdem wird die Anzeige von gültigen 
Brückenüberquerungen von der Prozedur SchreibeStrecke aufgerufen. 

     PROCEDURE SchreibeStadtteil (Stadtteil : tStadtteile); 
     BEGIN 

          CASE Stadtteil OF 
          Nord : write('Nord'); 
          Sued : write('Süd'); 
          Ost : write('Ost'); 
          Insel : write('Insel'); 

     END; 
     END; 

     PROCEDURE SchreibeStrecke (Strecke : tStrecke); 
     VAR i : integer; 
     BEGIN 

          FOR i := 1 TO Strecke.wievielte DO BEGIN 
          write(' = '); 
          SchreibeStadtteil(Strecke.Weg[i]); 
          END; 
          writeln; 

     END 

In der Prozedur NaechsterSchritt sind noch zwei Funktionen und zwei Prozeduren enthalten. 

     PROCEDURE NaechsterSchritt (von : tStadtteile); 
     VAR nach : tStadtteile;  

Die Funktion Naechster ermittelt den nächsten Stadtteil. Im Anweisungsteil der Prozedur NaechsterSchritt findet zunächst die 
Initialisierung der Stadtteile statt, indem die Variable nach auf Pregel gesetzt wird. Das erscheint sinnvoll, weil in der Schleife 
jeweils mit der ersten Anweisung nach := Naechster(nach) ein gültiger Stadtteil ausgewählt wird. 

     FUNCTION Naechster (Stadtteil : tStadtteile) : tStadtteile; 
     BEGIN 

          Naechster := Succ(Stadtteil); 

     END 

Die Funktion Moeglich prüft, ob zwischen den Stadtteilen, die durch von und Stadtteil repräsentiert werden, noch eine 
Brückenüberquerung möglich ist. 

     FUNCTION Moeglich (von, Stadtteil : tStadtteile) : boolean; 
     BEGIN 

          Moeglich := Brueckenplan[von, Stadtteil] > 0; 

     END 

In der Prozedur NotiereSchritt wird eine Brückenüberquerung protokolliert. Dazu werden die Werte in der Tabelle um Eins 
verringert, die Anzahl der Brückenüberquerung um Eins erhöht und der letzte Schritt aufgezeichnet: Strecke.Weg 
[Strecke.wievielte] := nach. Die möglicherweise aufgetretene Lösung wird abgefragt, indem geprüft wird, ob am Startpunkt 
angekommen wurde und die ANZAHL der Brücken überquert wurde. 

     PROCEDURE NotiereSchritt ( VAR Bruecke : tBrueckenplan; VAR Strecke : tStrecke); 
     BEGIN 

          Bruecke[von,nach] := Bruecke[von,nach] - 1; 
          Bruecke[nach,von] := Bruecke[nach,von] - 1; 
          Strecke.wievielte := Strecke.wievielte + 1; 
          Strecke.Weg[Strecke.wievielte] := nach; 
          Loesung := (nach = Startpunkt) AND (Strecke.wievielte = ANZAHL); 

     END 

Wenn ein Schritt zurückgeommen werden muß, dann wird die Prozedur LoescheSchritt aufgerufen. 

     PROCEDURE LoescheSchritt (VAR Bruecke : tBrueckenplan; VAR Strecke : tStrecke); 
     BEGIN 

          Bruecke[von,nach] := Bruecke[von,nach] + 1; 
          Bruecke[nach,von] := Bruecke[nach,von] + 1; 
          Strecke.wievielte := Strecke.wievielte - 1; 

     END 

An die Prozedur NaechsterSchritt wird als Parameter der jeweilige Standort übergeben (von). Im Weiteren wird systematisch 
nach noch zur Verfügung stehenden Brücken gesucht. Zunächst wird ein neuer Stadtteil ausgewählt. Wenn die Wahl des 
Zielstadtteiles eine Brückenüberquerung zuläßt, dann wird der Schritt notiert und geprüft, ob eine Lösung realisiert wurde. Ist 
die Lösung noch nicht erreicht, wird die Prozedur NaechsterSchritt von diesem Standpunkt aus (rekursiv) aufgerufen. Erweist 
sich eineBrückenüberquerung als Sackgasse, wird der letzte Schritt gelöscht. Der Vorgang terminiert, wenn eine Lösung 
erreicht ist oder alle Varianten getestet wurden (Loesung OR (nach = Insel)). 

     BEGIN 
     nach := Pregel; 
     REPEAT 

          nach := Naechster(nach); 
          IF Moeglich(von, nach) THEN BEGIN 

               NotiereSchritt(Brueckenplan, Strecke); 
               IF NOT Loesung THEN BEGIN 

                    NaechsterSchritt(nach); 
                    IF NOT Loesung THEN LoescheSchritt(Brueckenplan, Strecke); 

               END; 

          END; 

     UNTIL Loesung OR (nach = Insel); 
     END 

Im Hauptprogramm werden die Startpunkte vorbereitet. Nach dem Finden einer Lösung wird die Strecke ausgegeben. 

     BEGIN 
     clrscr; 
     Startpunkt := Pregel; 
     REPEAT 

          InitialisiereBrueckenplan(Brueckenplan); 
          Startpunkt := Succ(Startpunkt); 
          Strecke.wievielte := 0; 
          Loesung := false; 
          NaechsterSchritt(Startpunkt); 
          SchreibeStadtteil(Startpunkt); 
          IF Loesung 
          THEN SchreibeStrecke(Strecke) 
          ELSE writeln(' Es gibt keine gültige Strecke.'); 
          writeln; 

     UNTIL Startpunkt = Insel; 
     readln; 
     END. 
 

  
Anfang
vor
zurück
  

3.2.4 Variation des Themas

Dadurch, daß in der oben aufgeführten Variante mit sieben Brücken keine Lösung existiert, mag der Eindruck entstehen, daß 
das Programm möglicherweise fehlerhaft ist und deshalb keine Lösung gefunden wird. Um nachzuweisen, daß das Programm 
sehr wohl in der Lage ist, Lösungen zu finden, werden zwei Brücken ergänzt. Es entsteht folgender Plan. 
 
 

Die in der Tabelle veränderten Werte sind gekennzeichnet. 
 
 

nach 

von

Nord
Süd
Ost
Insel
Nord
0
1
1
2
Süd
1
0
1
2
Ost
1
1
0
2
West
2
2
2
0
Im Deklarationsteil muß die Anzahl auf 9 verändert werden. 

     CONST ANZAHL = 9; 

Die Prozedur InitialisiereBrueckenplan hat dann folgenden Inhalt: 

     Bruecken[Nord, Nord] := 0; 
     Bruecken[Nord, Sued] := 1; 
     Bruecken[Nord, Ost] := 1; 
     Bruecken[Nord, Insel] := 2; 
     Bruecken[Sued, Nord] := 1; 
     Bruecken[Sued, Sued] := 0; 
     Bruecken[Sued, Ost] := 1; 
     Bruecken[Sued, Insel] := 2; 
     Bruecken[Ost, Nord] := 1; 
     Bruecken[Ost, Sued] := 1;  
     Bruecken[Ost, Ost] := 0; 
     Bruecken[Ost, Insel] := 2; 
     Bruecken[Insel, Nord] := 2; 
     Bruecken[Insel, Sued] := 2; 
     Bruecken[Insel, Ost] := 2; 
     Bruecken[Insel, Insel] := 0;} 

Nach Ausführung des Programmes werden vier mögliche Lösungen für das Brückenproblem angezeigt. 
 

  
Anfang
vor
zurück
  

3.2.5 Verallgemeinerung

Das Backtracking Verfahren verallgemeinert: 

Es werden Schritte in Richtung Lösung systematisch geprüft und protokolliert. Führten sie in eine Sackgasse, so macht man sie 
schrittweise rückgängig und löscht die zugehörigen Aufzeichnungen. 
 

 

In Anlehnung an [Algorithmen und Datenstrukturen, N. Wirth, Teubner Verlag, Stuttgart, 1983, S. 167] wird eine allgemeine 
Backtracking - Prozedur dargestellt. 

     PROCEDURE try; 
     BEGIN 
     REPEAT 

          Wähle den nächsten Kandidaten 
          IF annehmbare Wahl THEN BEGIN  

               Zeichne den Schritt auf 
               IF unvollständige Lösung THEN BEGIN 

                    Versuche den nächsten Schritt 
                    IF NOT erfolgreich THEN Lösche die Aufzeichnung 

               END 

          END 

     UNTIL erfolgreich OR keine weiteren Kandidaten 
     END 
 

  
Anfang
zurück
  

3.2.6 Literatur

[Algorithmen und Datenstrukturen, Ottmann/Widmayer, Spektrum Verlag, 1996] 
[Algorithmen und Datenstrukturen, N. Wirth, Teubner Verlag, Stuttgart, 1983] 
[Duden Informatik, Engesser/Claus/Schwill, Dudenverlag, Mannheim, 1993] 
[Prinzipien des Agorithmenentwurfs, T. Ottmann, Spektrum Verlag, 1998] 
 
  
Anfang
  
 

Benutzer: Gast • Besitzer: seminar • Zuletzt gešndert am: