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 oder Matrix.
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</li>
  <li>Entwurf Integrierter Schaltungen</li>
</ul>

<language>Scheme</language>
==Naiver Algorithmus==
[[Bild:S3juhils_Tsp4.PNG|200px|thumb|right]]
Die wahrscheinlich offensichtlichste Lösung liegt darin sich alle Rundreisen generieren zu lassen und dann die mit dem kürzesten Weg auszuwählen.
Für $n$ Städte gibt es insgesamt $n!$ Rundreisen. Da man aber jeden Rundweg in zwei Richtungen gehen kann, sind nur die Hälfte der Rundreisen verschieden. Somit sind nur $\frac{n!}{2}$ Rundreisen wirklich relevant. Ist der Start- und Zielort festgelegt sind es nur $\frac{(n-1)!}{2}$ mögliche Rundreisen. 
Der Aufwand allein für die Erstellung aller Rundreisen ist exponentiell, wie sich mit der ''Stirling''schen Formel zeigen lässt:

<math>n! \approx \sqrt{2 \cdot \pi \cdotn} \cdot \left( \frac{n}{e} \right)^n = \mathcal{O}(n^n)</math><br>

<center>[[Bild:S3juhils_Tsp6.png|400px]]</center><br>

Bereits für 10 Städte gibt es 181.440 mögliche Rundreisen, für 13 sind es dann 239.500.800 mögliche Rundreisen. Wenn die Berechnung pro Rundreise 1 Millisekunde bräuchte, benötigt man zur Berechnung aller Rundreisen bei 13 Städten rund 3 Tage. <br>
Nun muss man noch die kürzeste Rundreise finden, was durch Entfernungsmatrizen möglich ist. Möchte man nun das TSP mit vielen Städten (großem $n$) lösen, bedarf es einer anderen Lösungsstrategie.<br>

<popup name="Vollständigen Code">
<code id="526e34208512e" rows="38" cols="80">
(define permut
  (lambda (ls)
    (cond
      ((null? ls) '())
      ((null? (cdr ls)) (list (list (car ls))))
      (else
       (apply
        append
        (map
         (lambda (zeichen)
           (map
            (lambda (x) (cons zeichen x))
            (permut (delete zeichen ls))))
         ls))))))

(define delete
  (lambda (item ls)
    (cond
      ((null? ls) '())
      ((eqv? (car ls) item) (cdr ls))
      (else
       (cons (car ls) (delete item (cdr ls)))))))

(define staedte-permut
  (lambda (n)
    (letrec
        ((helfer
          (lambda (i)
            (if (= i 1)
                '()
                (cons i (helfer (- i 1)))))))
      (let ((ls (helfer n)))
        (map
         (lambda (x)
           (cons 1 (append x (list 1))))
         (permut ls))))))
</code></popup>

<run id="526e3420851b9">
(/ (length (staedte-permut 10)) 2)</run>

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