Suche Home Einstellungen Anmelden Hilfe

"Versorgung der Bevölkerung"

Unser Problem bestand darin, einen optimalen Rundweg für einen Roboterboten zu entwerfen.
Die Route sollte so aussehen, daß man auf dem kürzesten Weg genau jedes Haus mit Grundnahrungsmitteln
versorgt. Die Entfernungen zwischen den einzelnen Häusern sind dem Boten bekannt. Der Bote hat nun das
Problem, für sich den kürzesten Weg zu finden, und dabei jedes Haus genau einmal anzulaufen.

Unsere Aufgabe besteht nun darin, verschiedene Lösungen für das Problem zu finden und die Effizient miteinander
zu vergleichen.

Der Entwurf des Lösungsplanes:

1. Schritt:
Als Erstes entwarfen wir mit den gegebenen Hausnummern (Knoten) einen geschlossenen Graphen, und
markierten die Kanten mit den Entfernungen zwischen den Häusern.

 
                      der erste Graph                                            die Verbesserung

2. Schritt:
Aus dem Graphen entwickelten wir, ausgehend von einem beliebigen Punkt, ein Baumdiagramm, das die möglichen
Wege des Boten widerspiegelt und dem man die Länge der Wege berechnen kann.
 
 
Wegsumme:   128   104       120    91           91    104         139   120        130    139     130    128

3. Schritt:
Als weiterer Ansatz zur Lösung entstand dann eine Adjazenzmatrix. Die Matrixwerte sind die einzelnen Entfernungen
zwischen zwei Häusern. ( z.B. a(1,2) = 20, a(1,3) = 23, a(1,7) = nil )
 
 

nil	20	23	1	nil	nil	nil
20	nil	nil	4	15	nil	nil
23	nil	nil	36	nil	28	nil
1	4	36	nil	9	25	16
nil	15	nil	9	nil	nil	3
nil	nil	28	25	nil	nil	17
nil	nil	nil	16	3	17	nil

 

Eine Möglichkeit ist der Greddy-Algorithmus.
Dieser Algorithmus wurde erstmals 1957 von R.C.Prim  entwickelt. Der Algorithmus schreitet voran, indem er einem
Spannbaum durch Hinzufügen jeweils einer Kante "wachsen" läßt. Da der Baum minimale Gesamtlänge besitzen soll,
wählt der Algorithmus immer die kürzeste Kante, um sie dem Baum hinzuzuführen.
Dieser Algorithmus, MINSPAN genannt, benutzt eine Liste L von Kanten, welche die Knoten in dem gerade im Aufbau
befindlichem Baum mit dem noch nicht aufgespannten Knoten verbinden. Der Baum selbst wird mit T bezeichnet.
Am Anfang besteht T aus einem einzelnen, beliebig gewählten Knoten u . Die Liste L enthält zu Beginn alle Kanten, die
mit u enden. Diese werden nach steigender Länge sortiert. Der Algorithmus geht so weiter vor, bis alle Knoten abgelaufen
sind. Die kürzeste Kante ist einfach zu berechnen, da sie immer das erste Element von L ist. Mit der neuen Kante wird die
neue Liste L erzeugt. Diese neue Liste L wird dann mit der nächsten Kante verwendet. Und dies geht solange weiter, bis
alle Knoten verarbeitet wurden.
Dieser Algorithmus hat aber bei unserem Beispiel nicht zum Erfolg geführt. Aus dem Grunde wird dieser Algorithmus
von uns nicht verwendet.
 

Formal kann man das Problem mit Hilfe eines ungerichteten Graphen ausdrücken. Die Knoten in dem Graphen entsprechen
den Städten und die markierten Kanten dazwischen den Verbindungen zwischen den Städten und ihren Entfernungen.
Allerdings ist das Problem des Handlungsreisenden nicht für jeden Graphen lösbar. Der Graph muß die Eigenschaft besitzen, mindestens einen Zyklus zu beinhalten, der alle Knoten enthält. Einen solchen Graphen nennt man Hamilton'schen Graphen. Somit reduziert sich das Problem des Handlungsreisenden auf die Suche nach dem kürzesten Zyklus in einem Hamilton'schen Graphen.

Das Problem des Handlungsreisenden läßt sich mit Hilfe des 'Branch-and-Bound-Verfahren's' lösen.

An einem Beispiel soll das Verfahren erläutert werden.
Gegeben seien vier Städte (A, B, C, D) und ihre Entfernungen. Daraus ergibt sich dieser ungerichtete Graph.
   
Das Branch-and-Bound-Verfahren teilt ein Optimierungsproblem in Teilprobleme auf, die dann schrittweise abgearbeitet
werden.
Der Handlungsreisende hat drei Möglichkeiten, vom Punkt A zu den anderen Städten (AB, AC, AD) zu kommen. Das heißt,
es existieren drei Teilprobleme. Diese drei Teilprobleme lassen sich mit Hilfe von Entfernungstabellen
(Matrix) besser verdeutlichen.

Welcher Weg für ihn der günstigste ist, wird mit Hilfe einer oberen und unteren Schranke abgeschätzt.

 
Da P2 die kleinste Schranke hat, wählt der Handlungsreisende den Weg vom Startpunkt A nach C. Am Punkt C angekommen muß er sich wieder entscheiden, ob er erst die Stadt B oder doch erst die Stadt D besuchen soll. Daraus ergeben sich wieder zwei Teilprobleme, die auch mit Hilfe des Branch-and-Bound-Verfahren's entschieden werden.
 
 

Am Ende entscheidet sich der Handlungsreisende auf Grund des Branch-and-Bound-Verfahren's  für die Strecke von
A über C,  D nach B und wieder zurück nach A. Diese Route hat auch tatsächlich die kürzeste Länge und ist daher die
optimale Lösung unseres Problems.
Die Lösung des Problems mit dem Branch-and-Bound-Verfahren zeigt, das man nur eines der sich ergebenden
Teilprobleme weiter verfolgen muß. Damit reduziert sich ein solches Problem erheblich.
 
 

Vorteil:

• es werden erheblich weniger  Knoten  zur Berechnung der optimalen Lösung  herangezogen

• keine Abschätzung der Güte
• Kompromiß finden zwischen Rechenaufwand und Qualität der Schranken (wenn man nur eine der beiden Schranken berechnet)

Literatur: Internet
                Duden Informatik
                Der Turing Omnibus, A.K.Dewdney
                Bundeswettbewerb Info Bd7/8 Aufgabe 11. Wettbewerb
                Datenstrukturen und Algorithmen, Ralf Hartmut Güting
 
 

  baum2.GIF

  bild4.GIF

  bild7.jpg

  bsp.GIF

  graphgif.GIF

  graphgif2.GIF

  Image10.gif

  Image14.gif

  Image15.gif

  Image17.gif

  Image18.gif

  Image19.gif

  Image20.gif

  Image9.gif

  Projekt3.sml

  versu1.sml

Benutzer: gast • Besitzer: mthomas • Zuletzt geändert am: