AuK/Verzweigen und beschränken WS13-14
Aus ProgrammingWiki
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 aber 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==
===Finden einer Schrankenfunktion===
Die Bestimmung eines Bounds (einer Schranke) für das vorgestellte Travelling Salesman Problem ist nicht einfach. Eine solche Schranke $s_k$ soll für einen Knoten $k$ versprechen, dass von $k$ aus kein Weg entstehen kann, der kürzer ist als der Bound $s_k$. Hat ein Knoten eines anderen Teilbaumes eine kleinere untere Schranke, ist dieser Knoten zu bevorzugen.<br>
Eine einfach zu berechnende Schrankenfunktion, ergibt sich aus der Summe der zurückgelegten Teilwege vom Start aus und der Entfernung zum nächstgelegenen noch unbesuchten Knoten. Leider ist die Funktion alles andere als präzise, auch wenn der Weg zum nächsten Knoten sehr kurz ist, kann der weitere Weg sehr lang sein und somit die Gesamtlänge weit größer ist als die ideale Lösung.<br>
Man muss den weiteren Weg nach dem Verlassen des Knotens $k$ auch in die Betrachtung mit einbeziehen. Als Beispiel könnte man die Summe aller zu $k$ hinführenden Kanten und von $k$ wegführenden Kanten berechnen, um so eine verlässlichere Schranke zu bekommen. Um Doppelzählung zu vermeiden dividiert man die Summe noch durch zwei. In diesem Fall hofft man aber auch nur auf eine Näherungslösung. Mit begrenztem Wissen und wenig Zeit eine gute Lösung zu erhalten nennt man Heuristik.
===Lösung mit reduzierten Entfernungsmatrizen===
Wie oben schon angesprochen, eignen sich Matrizen gut zur Angabe der Entfernungen zwischen den einzelnen Städten. Auch zur Berechnung des kürzesten Weges können sie helfen.<br>
Durch Reduktion jedes Zeileneintrags um das Zeilenminimum erhält man eine zeilenreduzierte Matrix. Danach bildet man in der zeilenreduzierten Matrix alle Spaltenminima und zieht diese von den Werten in den Spalten ab. Wichtig ist, dass man die Zeilen- und Spaltenminima jeweils neben bzw. unter die Matrix schreibt. Diese sind später für die Bound-Bildung wichtig.<br>
Beispiel:<br>
originale Entfernungsmatrix $\longrightarrow$ zeilenreduzierte Matrix $\longrightarrow$ vollständig reduzierte Matrix
<div>$
\begin{matrix}
x & 7 & 4 & 1 & | & \\
3 & x & 2 & 2 & | & \\
1 & 2 & x & 5 & | & \\
2 & 4 & 3 & x & | & \\
\hline
& & & & | &
\end{matrix}
\longrightarrow
\begin{matrix}
x & 6 & 3 & 0 & | & 1 \\
1 & x & 0 & 0 & | & 2 \\
0 & 1 & x & 4 & | & 1 \\
0 & 2 & 1 & x & | & 2 \\
\hline
& & & & | & 6
\end{matrix}
\longrightarrow
\begin{matrix}
x & 5 & 3 & 0 & | & 1 \\
1 & x & 0 & 0 & | & 2 \\
0 & 0 & x & 4 & | & 1 \\
0 & 1 & 1 & x & | & 4 \\
\hline
0 & 1 & 0 & 0 & | & 7
\end{matrix}
$
</div><br>
Wenn man nun von einem Knoten zum nächsten geht, muss man die Entfernungsmatrix entsprechend modifizieren. Wenn man vom Knoten $i$ aus die Kante $(i,j)$ hinzunimmt sind diese Modifizierungen erforderlich:
<ul>
<li>Setze $E[z,j] = \infty$ für alle $z \neq i$, denn $j$ wird nur von $i$ aus besucht.</li>
<li>Setze $E[i,s] = \infty$ für alle $s \neq j$, denn ein anderer Weg von $i$ aus ist verboten.</li>
<li>Setze $E[j,i] = \infty$, denn der Weg von $j$ nach $i$ ist nicht mehr verfügbar. Er wurde bereits in anderer Richtung durchlaufen.</li>
</ul>
Schranken können auch kürzer sein, als der später ermittelte kürzeste Rundweg.
'''Ablauf:'''
<ol>
<li>Startknoten festlegen und durch Erstellen der reduzierten Matrix die untere Schranke bestimmen</li>
<li>in der Hierarchie eine Ebene nach unten gehen und für die Knoten der einzelnen Teilbäume die untere Schranke bestimmen</li>
<li>an dem Knoten mit der kleinsten Schranke weiter nach unten gehen und jeweils wieder die minimale Schranke bestimmen</li>
<li>gibt es mehrere Teilstücke mit der gleichen minimalen Schranke müssen alle besucht werden</li>
<li>ist man in der untersten Ebene angekommen, gibt es nur noch einen Pfad und der letzte Knoten ist dann die Lösung</li>
</ol>
===Prioritätswarteschlangen===
Wie schon weiter oben erklärt ist es unbedingt notwendig, alle Blätter des Baumes in einer Warteschlange aufzubewahren. Auch wenn sie zum Zeitpunkt ihrer Analyse nicht die kleinste Schranke hatten.<br>
Für solche Probleme eignet sich eine Prioritätswarteschlange (engl. priority queue, auch Vorrangwarteschlange) besonders gut. Diese ist eine Datenstruktur zur Speicherung einer Menge von Elementen, für die eine Prioritätsordnung definiert ist. Jeder Wert hat einen Schlüssel mit seiner Priorität.
Folgende Operationen sind ausführbar:
<ul>
<li>'''initialize:''' Initialisieren einer (leeren) Struktur</li>
<li>'''insert:''' Einfügen eines Elements (an der richtigen Stelle)</li>
<li>'''access min:''' Minimum lesen</li>
<li>'''delete min:''' Minimum entfernen</li>
</ul>
Die Implementation erfolgt am besten mittels Heap (Halde). Ein Heap mit $n$ Elementen erlaubt das Einfügen eines neuen Elementes und das Entfernen des Minimums in $\mathcal{O}(\log n)$ Schritten. Das Minimum steht immer am Anfang des Heaps, deshalb kann '''accesss min''' in konstanter Zeit ausgeführt werden.<br>
Für das TSP und andere Minimierungsprobleme nutzt man die Min-Prioritätswarteschlange, für Maximierungsprobleme dreht man einfach die Prioritätsordnung um, so dass das Maximum immer an erster Stelle steht und erhält so eine Max-Prioritätswarteschlange. Priority Queues können einfach und effizient implementiert werden.
Schwierig ist nur zwei Heaps schnell zu einem zusammenzusetzen. Die beste Möglichkeit ist die vorhandenen Heaps aufzulösen und einen neuen Heap mit allen Elementen aus beiden Heaps zu erstellen. Wenn $n$ die Anzahl der Elemente des einen Heaps und $k$ die des anderen ist, ist diese Operation in $\mathcal{O}(n+k)$ Schritten durchführbar.