Vertiefungsaufgabe

Aus ProgrammingWiki
< AuK < Durchläufe durch Graphen SS12
Archivierte Version vom 2012-06-24T10:45:33+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

Ermittelte Rundreise

Intuitiver Algorithmus

Lösungsverfahren Branch & Bound

Näherungslösung MST-Heuristik

Fazit