Vertiefungsaufgabe

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

    Intuitiver Algorithmus

    Lösungsverfahren Branch & Bound

    Näherungslösung MST-Heuristik

    Fazit