Vertiefungsaufgabe

Aus ProgrammingWiki
< AuK < Durchläufe durch Graphen SS12
Archivierte Version vom 2012-06-24T10:54:39+00:00. Aktuelle Version

Robert Riedel: s3roried@stud.hszg.de
Bettina Sprenger: s3bespre@stud.hszg.de


Lösung des Rundreiseproblems (TSP)

Aufgabenstellung

Eine PKW-Rundreise soll durch die folgenden Städte führen und dabei jeden dieser 16 Orte genau einmal besuchen:

  • Dresden
  • Berlin
  • Spröda
  • Lüneburg
  • Löbau
  • Limbach-Oberfrohna
  • Blankenheim (06528)
  • Dohna
  • Eisenach (99817)
  • Dürrhennersdorf
  • Callenberg (09337)
  • Eisenhüttenstadt
  • Pirna
  • Riesa
  • Coswig (01640)
  • Seerhausen

Ausnahme: Die Stadt, in der die Rundreise beginnt und endet, ist die einzige zweimal besuchte Stadt.

Gesucht ist die kürzeste Rundreise.

Entfernungsmatrix

Unser TSP umfasst also 16 Städte und 120 Entfernungen. Der daraus konstruierte Graph besitzt demnach Knotenanzahl |V| = 16 und Kantenanzahl |E| = 120. Daraus resultiert folgende symmetrische Entfernungsmatrix.

Croxeldyffic_Adjmatrix.jpg

Ermittelte Rundreise

Intuitiver Algorithmus

Lösungsverfahren Branch & Bound

Näherungslösung MST-Heuristik

Fazit