Vertiefungsaufgabe

Aus ProgrammingWiki
< AuK < Durchläufe durch Graphen SS12
Archivierte Version vom 2012-06-24T10:34:53+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 (\emph{06528})
    		•
  • Dohna
    		•
  • Eisenach (\emph{99817})
    		•
  • Dürrhennersdorf
    		•
  • Callenberg (\emph{09337})
    		•
  • Eisenhüttenstadt
    		•
  • Pirna
    		•
  • Riesa
    		•
  • Coswig (\emph{01640})
    		•
  • Seerhausen
    		•

    Intuitiver Algorithmus

    Lösungsverfahren Branch & Bound

    Näherungslösung MST-Heuristik

    Fazit