AuK/Verzweigen und beschränken WS13-14

Wiki-Quelltext dieser Seite.

;Autoren
:[mailto://s3hakret@stud.hszg.de Hannes Kretschmer]<br/>
:[mailto://s3juhils@stud.hszg.de Julian Hilsberg]

=Bewerten, auswählen und expandieren=

=Anwendung auf das Rucksackproblem=

=Das Rundreiseproblem=

==Problemstellung==
Ein Geschäftsmann (auch Handlungsreisender) muss bei einer Rundreise $n$ vorgegebene Städte besuchen. Er startet in einer dieser Städte, besucht nacheinander alle anderen Städte und kehrt am Ende in seine Ausgangsstadt zurück.<br>
Das Optimierungsproblem besteht jetzt darin, die Rundreise so zu planen, dass ihre Gesamtlänge minimal wird.
Die Entfernung zwischen den einzelnen Paaren von Städten sind angegeben, z.B. in einer Tabelle.
Das Problem ist auch bekannt unter dem Namen Travelling Salesman Problem (TSP).

==Einteilung==
Das Rundreiseproblem gehört in die Kategorie der NP-vollständigen Problemen. Für solche Probleme ist kein effizienter Algorithmus bekannt. Es wird aber angenommen, dass jeder deterministische Algorithmus zur exakten Lösung mindestens exponentiell viele Rechenschritte braucht. Ein mathematischer Beweis für diese Vermutung existiert aber bis heute nicht. Für spezielle Formen des TSP und zur Berechnung von Näherungslösungen sind aber viele effiziente Algorithmen bekannt.

==Praxis==
Einsätze in der Praxis:
<ul>
  <li>Verkehrsplanung</li>
  <li>Logistik (z.B. bei UPS)</li>
  <li>Entwurf Integrierter Schaltungen</li>
</ul>

==Naiver Algorithmus==

==Lösung mit Verzweigen und beschränken==