AuK/Branch and Bound
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Python</language>
Die Idee von ''Branch and Bound'' wurde 1960 von A. H. Land und A. G. Doig formuliert. 1965 gab R. J. Dakin einen einfach zu implementierenden Algorithmus dafür an.
[[AuK/Divide_and_Conquer|Teile und Herrsche]] sowie [[AuK/Dynamic_Programming|dynamisches Programmieren]] zerlegen das Gesamtproblem in einfachere Teilprobleme. Im Gegensatz dazu wird bei ''Branch and bound'' (Verzweige und Begrenze) die Lösungsmenge geeignet partitioniert. Das bedeutet, ''dass sich der Lösungsraum baumartig strukturieren lässt''. Abb. 1 zeigt das für einen ''Entscheidungsbaum''.
[[Datei:BnB_FullSearchTree.png|center|500px]]
<center>Abb. 1: Baumartige Repräsentation des Lösungsraums</center>
Für die resultierenden Bäume gilt jedoch, dass sie nur in Exponentialzeit erzeugt und nicht vollständig gespeichert werden können. Man stelle sich z.B. ein [[AuK/Graphen#Anwendungsbeispiel:_0.2F1_Rucksackproblem|0/1-Rucksackproblem]] mit 50 Gegenständen vor. Bei diesem gibt es über eine Billiarde potentielle Belegungen, die nicht alle geprüft werden können.
Eine vollständige Enumeration bzw. ein vollständiger Durchlauf (Traversierung) des Lösungsraumbaumes sollte also vermieden werden, wenn man einigermaßen praktikable Problemgrößen im Auge hat. Dies kann man erreichen, wenn man den Baum nur teilweise, nämlich nur für "aussichtsreiche" Knoten aufbaut.
Durch dieses ''Verzweigen'' (Branch-Schritt) entstehen Teilmengen, die jeweils unterschiedliche spezielle Eigenschaften besitzen: Die Gegenstandsmenge beim [[AuK/Graphen#Anwendungsbeispiel:_0.2F1_Rucksackproblem|0/1-Rucksackproblem]] kann z.B. in die Teilmenge $A$ (alle Rucksackbelegungen, bei denen Gegenstand 1 enthalten ist) und die Teilmenge $B$ (alle Rucksackbelegungen, bei denen Gegenstand 1 nicht enthalten ist) zerlegt werden. Diese Mengen können nun wieder verzweigt bzw. bezüglich des Enthaltens der anderen Gegenstände in noch kleinere Teilmengen unterteilt werden. So entsteht ein Entscheidungsbaum, wie in Abb. 1. Alternativ können Tiefensuche oder Breitensuche als ''Enumerationsverfahren'' eingesetzt werden, um einen entsprechenden Baum zu erhalten.
Für die Identifikation "hoffnungsloser Fälle", also Knoten, die (zunächst) nicht weiter expandiert werden, ist eine separate Knotenbewertung notwendig (Bound-Schritt). Eine (geeignete) ''obere'' Schranke bei einem ''Maximierungsproblem'' beziffert die Chancen auf den gesuchten Maximalwert. Der durch einen Knoten repräsentierte, bereits erzielte Maximalwert dient als (globale) ''untere'' Schranke, die im Prozess schrittweise nach oben verschoben wird. Ist die obere Schranke eines Knotens kleiner als dessen untere, wäre die Expansion des betreffenden Knotens sinnlos. (Für Minimierungsprobleme gilt dies analog.)
==0/1-Rucksackproblem==
Für ein 0/1-Rucksackproblem mit 4 Gegenständen könnte genau der in Abb. 1 dargestellte Suchbaum entstehen. Der Baum hat $2^4=16$ Blätter.
Auf jeder Ebene wird für einen bestimmten Gegenstand die Entscheidung getroffen, ob dieser im Rucksack enthalten sein soll (1) oder nicht (0). Wurden 4 Entscheidungen getroffen (Ergebnisvektor mit 4 Komponenten), steht eine mögliche Rucksackbelegung fest. Diese kann nun die Lösung (Optimum) sein oder auch nicht.
Im Unterschied zu dem weiter unten bearbeiteten Rundreiseproblem wird beim 0/1-Rucksackproblem eine ''Auswahl'' von (einzupackenden) Gegenständen vorgenommen, während beim Rundreiseproblem ''alle'' Städte in der Lösung vorkommen müssen.
Da die Kapazitätsbeschränkung $K$ des Rucksacks Teil der Aufgabenstellung ist, werden die Knoten, durch die das Gesamtgewicht des Rucksacks über $K$ liegen würde, nicht expandiert.
[[Datei:BnB_TreeBoundStatic.png|center|500px]]
<center>Abb. 2: Reduzierter Lösungsraumbaum</center>
Die ja/nein-Angaben an den Kanten/Pfeilen beziehen sich auf die Knoten, von denen sie ''ausgehen''. Für den Knoten für den Gegenstand mit dem Gewicht $5$ in der Wurzel bedeutet das: ja/links/einpacken bzw. nein/rechts/nicht einpacken.
Für vier Gegenstände mit den Gewichten $(5,4,3,2)$ und einer Maximalkapazität von $8$ können die Zweige ignoriert werden, bei denen die Kapazitätsgrenze überschritten wird (grau). Von $16$ möglichen Lösungskandidaten (Blätter) bleiben noch $10$ übrig und anstatt $15$ Expandierungen vorzunehmen, sind nur noch $9$ erforderlich.
Die Kapazitätsgrenze ist eine statische Schranke, denn sie ändert sich während der Suche nicht. Sie gehört hier zur Aufgabenstellung.
Für das Branch and Bound Verfahren sind ''dynamische Schranken'', die im Verlauf der Suche immer strenger werden, von Interesse. Wurde z.B. bereits irgendeine gültige Rucksackbelegung gefunden, können Knoten unter denen nur schlechtere Belegungen zu finden sind, ignoriert werden. Je besser der aktuell beste Rucksack im Verlauf der Suche wird, umso strenger wird die Schranke und umso stärker fällt die Begrenzung aus. Das Ziel ist also möglichst schnell zu einer guten (noch nicht optimalen) Lösung zu gelangen, um von einer möglichst starken Begrenzung zu profitieren.
'''Beispiel''': Gegeben sind 4 Gegenstände mit den Gewichten $g=(5,3,4,2)$ und den Werten $w=(9,5,6,3)$. $K=8$. Unter den gültigen Bepackungen des Rucksacks soll die mit dem größten Gesamtwert ermittelt werden.
{| class="wikitable" style="text-align:center; vertical-align:middle; margin:0 auto;"
|- style="font-weight:bold;"
! Gegenstand $i$
! Gewicht $g$
! Wert $w$
! spezifischer Wert $w/g$
|-
| 1
| 5
| 9
| 1,8
|-
| 2
| 3
| 5
| 1,7
|-
| 3
| 4
| 6
| 1,5
|-
| 4
| 2
| 3
| 1,5
|}
Gibt es z.B. bereits einen gültigen Rucksack mit einem gewissen Wert, so müsste für einen Knoten (quasi einen noch nicht fertig gefüllten Rucksack) bestimmt werden, ob überhaupt noch ein gültiger Rucksack zusammengestellt werden kann, der wertvoller ist. An jedem Knoten hat der untersuchte Teil-Rucksack einen momentanen Gesamtwert und eine Restkapazität. Um zu bestimmen, welcher zusätzliche Gegenstandswert unter Verbrauch der Restkapazität noch hinzugefügt werden kann, müsste allerdings ein weiteres (kleineres) Rucksackproblem gelöst werden. Das wäre sehr aufwendig. Wir brauchen eine ''effiziente'' Bewertungsfunktion.'' Diese Effizienz kann dadurch verbessert werden, dass eine ''Schranke geringerer Güte'' ermittelt wird (Relaxation). Dies kommt dann auch bei der näherungsweisen Lösung von Optimierungsproblemen zum Tragen. Für das 0/1 Rucksackproblem bietet sich z.B. folgende Möglichkeit:
<!--
| Gegenstand $i$ | Gewicht $g$ | Wert $w$ | spezifischer Wert $w/g$ |
|:--------------:|:------------:|:-----------:|:-----------------------:|
| 1 | 5 | 9 | 1,8 |
| 2 | 3 | 5 | 1,7 |
| 3 | 4 | 6 | 1,5 |
| 4 | 2 | 3 | 1,5 |
-->
Die $n$ Gegenstände mit den Werten $w_i$ und den Gewichten $g_i$ für $1 \leq i \leq n$ können nach ihrem ''spezifischen Wert'' $\frac{w_i}{g_i}$ sortiert entschieden werden. Dieser Quotient sagt aus, welcher Wert pro Gewichtseinheit beim Hinzufügen dieses Gegenstands hinzugewonnen wird. Entscheidungen für Gegenstände mit hohem Wert und geringem Gewicht werden so zuerst getroffen. Es ist sichergestellt, dass $\frac{w_i}{g_i} \geq \frac{w_{i+1}}{g_{i+1}}$. Für einen Knoten (einen Teil-Rucksack) bei dem bereits $k$ Gegenstände entschieden wurden, kann bei gegebener Maximalkapazität $K$ die Restkapazität $r$ und der damit einhergehende maximal erreichbare Rucksackwert $m$ bestimmt werden.
Ein (Teil-)Rucksack ist definiert durch den Vektor $\overrightarrow{x}=(x_1, x_2, \dots, x_k) \text{ für } 1 \leq k \leq n \text{ und } x_k \in \{0,1\}$. Der Rucksack $(1,0,1)$ enthält demnach Gegenstand 1 und 3 und nicht Gegenstand 2.
$$r = K - \sum_{i=1}^k x_i g_i$$
$$m = r \frac{w_{k+1}}{g_{k+1}} + \sum_{i=1}^k x_i w_i$$
Die Restkapazität $r$ eines Rucksacks ist die Differenz zwischen Maximalkapazität $K$ und aktuellem Rucksackgewicht. Der maximal erreichbare Rucksackwert $m$ (obere Schranke für das tatsächliche Maximum) ist die Summe aus dem aktuellen Rucksackwert und der Restkapazität multipliziert mit dem spezifischen Wert des '''nächsten''' noch nicht entschiedenen Gegenstands ($k+1$). Da die spezifischen Werte aller weiteren Gegenstände maximal genauso groß sind, bildet $m$ eine obere Schranke.
Liegen für alle aktuellen Blätter die Wert des jeweils besten Rucksacks (untere Schranke) nicht mehr unter dem höchstens erzielbaren Gesamtwert (oberen Schranke), so ist das globale Maximum gefunden. Weitere Knotenexpansionen wären Zeitverschwendung.
====Ablauf====
[[Bild:Branch-and-bound.png|center|800px]]
<!--
[[Datei:BnB_TreeBoundRest.png|center|600px]]
<center>Abb. 3: Expansionsprozess und Schrankenbestimmung</center>
Der mögliche Wertzugewinn kann so für jeden Knoten sehr einfach berechnet werden. Obiges Bild zeigt die entsprechenden Zugewinne an den Knoten für die rechts aufgelisteten Gegenstände. Wie effektiv die resultierende Begrenzung ist, hängt nun von der Reihenfolge ab in der die Knoten geprüft werden. In jedem Fall muss bei Knoten <font color='red'>A</font> begonnen werden. Bei <font color='red'>A</font> ist der aktuelle Rucksack leer (hat den Wert $0$) und es ist ein Zugewinn von maximal $8\cdot 1.8 = 14.4$ zu erwarten. Da $0+14.4$ größer ist als der momentan beste Rucksack (ist zu Beginn ebenfalls leer, d.h. Wert gleich Null) muss <font color='red'>A</font> expandiert werden. Durch die Expandierung wird ein Rucksack gefunden der Gegenstand 1 enthält und somit den Wert $9$ hat. Dieser wird nun zum momentan besten bekannten Rucksack und gibt mit seinem Wert eine erste Schranke vor. Als nächste Knoten kommen nun <font color='red'>B</font> und <font color='red'>C</font> in Frage. Bei <font color='red'>B</font> ist der aktuelle Rucksackwert $9$ und durch den Zugewinn von $5$ kann ein maximaler Rucksackwert von $14$ erreicht werden. Bei <font color='red'>C</font> ist der maximal zu erreichende Wert nur $13.3$. Aus diesem Grund sollte Knoten <font color='red'>B</font> bevorzugt behandelt werden. Knoten <font color='red'>C</font> wird für spätere eventuelle Expansionen "zur Seite gelegt". Folgende Tabelle zeigt die weitere Entwicklung:
-->
<!--
| Schritt | Knoten | Rucksackwert | Zugewinn | Max | Aktion | Best |
| --- | --- | --- | --- | --- | --- | --- |
| 1 | A | 0 | 14,4 | 14,4 | Expandiere zu B und C | 9 |
| 2 | B | 9 | 5 | 14 | Expandiere zu D und E | 14 |
| | C | 0 | 13,3 | 13,3 | Aufschieben | |
| 3 | C | 0 | 13,3 | 13,3 | Bound (Max $\leq$ Best) | |
| | D | 14 | 0 | 14 | Gehe zu H | 14 |
| | E | 9 | 4,5 | 13,5 | Bound (Max $\leq$ Best) | |
| 4 | H | 14 | 0 | 14 | Ende (keine Knoten mehr) | 14 |
-->
<!--
{| class="wikitable" style="text-align:right; vertical-align:middle;margin:0 auto;"
|- style="font-weight:bold;"
! style="text-align:center;" | Schritt
! style="text-align:center;" | Knoten
! Rucksackwert
! Zugewinn
! Max
! style="text-align:left;" | Aktion
! Best
|-
| style="text-align:center;" | 1
| style="text-align:center;" | A
| 0
| 14,4
| 14,4
| style="text-align:left;" | Expandiere zu B und C
| 9
|-
| style="text-align:center;" | 2
| style="text-align:center;" | B
| 9
| 5
| 14
| style="text-align:left;" | Expandiere zu D und E
| 14
|-
| style="text-align:center;" |
| style="text-align:center;" | C
| 0
| 13,3
| 13,3
| style="text-align:left;" | Aufschieben
|
|-
| style="text-align:center;" | 3
| style="text-align:center;" | C
| 0
| 13,3
| 13,3
| style="text-align:left;" | Bound (Max $\leq$ Best)
|
|-
| style="text-align:center;" |
| style="text-align:center;" | D
| 14
| 0
| 14
| style="text-align:left;" | Gehe zu H
| 14
|-
| style="text-align:center;" |
| style="text-align:center;" | E
| 9
| 4,5
| 13,5
| style="text-align:left;" | Bound (Max $\leq$ Best)
|
|-
| style="text-align:center;" | 4
| style="text-align:center;" | H
| 14
| 0
| 14
| style="text-align:left;" | Ende (keine Knoten mehr)
| 14
|}
Die Expandierung von <font color='red'>B</font> in Schritt 2 führt zu einem neuen besten Rucksack wodurch die untere Schranke auf 14 angehoben wird. In Schritt 3 kann für die verfügbaren Knoten <font color='red'>C</font> und <font color='red'>E</font> festgestellt werden, dass sich unterhalb keine bessere Lösung befinden kann.
Erst nachdem eine Rucksackbefüllung $(1,1)$ mit $14$ als Gesamtwert gefunden wurde, werden die Knoten <font color='red'>C</font> und <font color='red'>E</font> nicht mehr expandiert. Sie können nichts besseres als $13,3<14$ liefern. Damit ergibt sich folgender dynamisch reduzierter Suchbaum bei dem weitere 6 Expandierung eingespart wurden.
[[Datei:BnB_TreeBoundResult.png|center|600px]]
Ausführliche Bearbeitung mit Boundbestimmung:
[[Datei:Rucksack-BranchAndBound.jpg|center|600px]]
-->
===Implementation===
Nur selten werden Branch and Bound Algorithmen rekursiv implementiert. Eine ''sortierte Queue (priority queue)'' ist zumeist die beste Option, um eine Menge abzuarbeitender Elemente zu verwalten, so wie es hier für die Knoten erforderlich ist. Die meisten höheren Programmiersprachen bieten hierzu entsprechende Datenstrukturen an. Hier wird ''heapq'' verwendet, um die zur Expandierung zur Verfügung stehenden Knoten nach ihrem maximal erreichbaren Rucksackwert sortiert bereitzustellen. Die Auswahl des als nächstes zu expandierenden Knotens kann so durch ein einfaches ''heappop'' realisiert werden.
Die Expandierung, also das Erzeugen neuer Knoten mit und ohne dem nächsten Gegenstand, erfolgt schlicht durch Anhängen von 1 oder 0 an die Liste welche einen Rucksack repräsentiert. Die expandierten Knoten werden nur dann der Queue hinzugefügt, wenn die Kapazitätsgrenze nicht überschritten wird und der maximal erreichbare Wert den momentan besten Rucksackwert überschreitet.
Gibt es keine zu prüfenden Knoten mehr, also wurden alle Knoten entweder bereits verarbeitet oder ausgeschlossen, steht das Endergebnis fest.
<code id="5fe9a90e5190b">
import heapq # Priority Queue
def bnbKnapsack(items, K):
# Sortierung der Gegenstände nach Gewicht pro Werteinheit (kleiner ist besser)
sortedItems = sorted(items, key=lambda x: x[0] / x[1])
print(sortedItems)
bestKS = [] # [0,1,1,0] heißt das item1 und 2 enthalten sind und item0 und 3 nicht, anfangs leer
# Hilfsfunktion zur Bestimmung des Rucksackwerts
def ksValue(ks): return sum([sortedItems[i][1] if ks[i] == 1 else 0 for i in range(len(ks))])
# Hilfsfunktion zur Bestimmung des Rucksackgewichts
def ksWeight(ks): return sum([sortedItems[i][0] if ks[i] == 1 else 0 for i in range(len(ks))])
# Hilfsfunktion zur Bestimmung des maximal erreichbaren Rucksackwerts
def limit(ks): return ksValue(ks)+(K-ksWeight(ks))*sortedItems[len(ks)][1]/sortedItems[len(ks)][0]
knapsacks = [] # die aktuellen Knoten, sortiert nach maximal erreichbarem Rucksackwert
heapq.heappush(knapsacks, (1 / limit([]), [])) # Wurzel ist der leere Rucksack
while len(knapsacks): # solange es Knoten zu prüfen gibt
ks = heapq.heappop(knapsacks)[1] # Knoten mit dem höchsten erreichbaren Rucksackwert als nächstes
print("check:", ks)
for x in [0,1]: # Expandieren zu 2 neuen Knoten
expanded = ks + [x]
print("expanded:", expanded, end=" ")
if ksWeight(expanded) <= K: # Kapazitätsgrenze noch nicht überschritten
best = ksValue(bestKS) # momentan bester Rucksack
if len(expanded) < len(sortedItems): # noch kein vollständiger Rucksack
m = limit(expanded) # maximal zu erreichender Wert
if m > best: # könnte ein besserer Rucksack erzielt werden?
heapq.heappush(knapsacks, (1 / m, expanded))
print("queued with max:", m, end=" ")
else:
print("bound", end=" ")
if best < ksValue(expanded): # besser?
bestKS = expanded
print("better")
else:
print("")
else:
print("too heavy")
return [sortedItems[i] for i in range(len(bestKS)) if bestKS[i]]
</code>
<run id="5fe9a90e51b28">
print("Best:",bnbKnapsack([(5, 9), (3, 5), (4, 6), (2,3)], 8))
</run>
==Traveling Salesman Problem (TSP)==
Das oft zitierte ''Problem des Handlungsreisenden'' oder ''Rundreiseproblem'' besteht darin, eine vorgegebene Anzahl von Städten genau einmal zu besuchen und zum Ausgangspunkt zurückzukehren, wobei der zurückgelegte Gesamtweg minimal ist. Die Längen der Wegstrecken zwischen den Städten sind bekannt.
Dieses Problem haben aber nicht nur Handlungsreisende, sondern auch Logistikunternehmen (wie muss das Postauto fahren, sodass die Tour möglichst schnell geht), Platinen-Designer (wie müssen Kontakte verbunden werden, sodass möglichst wenig Edelmetall verbraucht wird) und viele mehr. In jedem Fall geht es darum, irgendwelche "Kosten" zu ''minimieren''. Es handelt sich also um ein ''Optimierungsproblem''.
[[Datei:BnB_TSPGraph.png|center|300px]]
<center>Abb. 2: gerichteter und gewichteter Graph</center>
Ein TSP lässt sich sehr einfach in Form von gewichteten Graphen darstellen, s. Abb. 2. Die die Städte repräsentierenden Knoten sind einfach durchnummeriert worden: $0,1,2,3$, $n=4$. Die Gewichte der Kanten entsprechen hier den Kosten für den Übergang von einem Knoten zum anderen (z.B. dem Preis für eine Flugreise von Ort A nach Ort B). Die Kosten zwischen zwei Knoten können dabei auch von der Richtung abhängig sein.
Eine Entfernungsmatrix $E$, wie in Abb. 3, liefert auch eine adäquate Modellierung des gegebenen Sachverhalts. Die $\infty$-Einträge kennzeichnen unmögliche oder verbotene Übergänge.
<!--
| $E$ | 0 | 1 | 2 | 3 | |
| --- | --- | --- | --- | --- | --- |
| '''0'''| $\infty$ | $20$ | $15$ | $10$ |
| '''1'''| $8$ | $\infty$ | $9$ | $8$ |
| '''2'''| $6$ | $12$ | $\infty$ | $13$ |
| '''3'''| $5$ | $10$ | $9$ | $\infty$ |
-->
{| class="wikitable" style="text-align:right; vertical-align:middle;margin:0 auto;"
|- style="font-weight:bold;"
! $E$
! 0
! 1
! 2
! 3
|-
| '''0'''
| $\infty$
| $20$
| $15$
| $10$
|-
| '''1'''
| $8$
| $\infty$
| $9$
| $8$
|-
| '''2'''
| $6$
| $12$
| $\infty$
| $13$
|-
| '''3'''
| $5$
| $10$
| $9$
| $\infty$
|}
<center>Abb. 3: Entfernungsmatrix $E$ für ein asymmetrisches TSP</center>
Die Suche nach einem Weg mit minimalen Kosten kann auch hier mittels Entscheidungsbaum visualisiert werden: Die im Baumdiagramm (Abb. 4) jeweils eingetragenen Pfeile geben an, welche Stadt als nächste besucht wird. Da es sich um eine Rundreise handelt, spielt es keine Rolle, welcher Knoten die Wurzel des Baumes (Start und Ende der Rundreise) bildet.
[[Datei:BnB_TSPTree.png|center|500px]]
<center>Abb. 4: Entscheidungsbaum für das TSP (mit markierter Lösung)</center>
Gibt es $n$ Knoten, so gibt es im ersten Schritt $n-1$ Möglichkeiten die Reise fortzusetzen, im nächsten Schritt nur noch $n-2$ usw. bis nach $n-2$ Schritten nur ein Knoten als mögliches Ziel verbleibt. Mit der Rückkehr zum Ausgangspunkt schließt sich der Kreis und die Länge des Weges steht fest.
Der in Abb. 4 angegebene Baum protokolliert alle möglichen Städtebesuchsfolgen. Für die Suche der kürzesten Rundreise spielt es im Allgmeinen durchaus eine Rolle, auf welchem Weg die betrachtete Stadt erreicht wurde. Von daher brauchen wir für jeden Stadtbesuch im Protokoll (Abb. 4) eine aktualisierte Gesamtschau auf die noch möglichen Fortsetzungen des Weges.
Dies erreichen wir durch ''Modifikation der jeweils aktuellen Entfernungsmatrix'' und führen das am Beispiel $0\rightarrow 3$ vor:
# $E[0,j]=\infty$ für $j\neq 3$: Besuche $3$ von $0$ aus, nicht von einer anderen Stadt her.
# $E[3,0]=\infty$: Der Rückweg von $3$ zu $0$ ist verboten, da $0$ bereits besucht wurde.
# $E[i,3]=\infty$ für $i\neq 0$: Nur von $0$ besucht man $3$, von keiner anderen Stadt aus.
Nach dem Übergang von $0$ (Start/Ziel) zu $3$ ergibt sich die in Abb. 5 angegebene modifizierte Entfernungsmatrix.
<!--
| $E$ | 0 | 1 | 2 | 3 | |
| --- | --- | --- | --- | --- | --- |
| '''0''' | $\infty$ | $\infty$ | $\infty$ | $10$ |
| '''1''' | $8$ | $\infty$ | $9$ | $\infty$ |
| '''2''' | $6$ | $12$ | $\infty$ | $\infty$ |
| '''3''' | $\infty$ | $10$ | $9$ | $\infty$ |
-->
{| class="wikitable" style="text-align:right; vertical-align:middle;margin:0 auto;"
|- style="font-weight:bold;"
! $E$
! 0
! 1
! 2
! 3
|-
| '''0'''
| $\infty$
| $\infty$
| $\infty$
| $10$
|-
| '''1'''
| $8$
| $\infty$
| $9$
| $\infty$
|-
| '''2'''
| $6$
| $12$
| $\infty$
| $\infty$
|-
| '''3'''
| $\infty$
| $10$
| $9$
| $\infty$
|}
<center>Abb. 5: Modifizierte Entfernungsmatrix $E$ nach $0\rightarrow 3$</center>
Das Verfahren zur Herstellung der (übergangsabhängigen) modifizierten Entfernungsmatrix lässt sich aus obigem Beispiel für $a\rightarrow b$ verallgemeinern, indem wir $0$ durch $a$ und $3$ durch $b$ ersetzen.
# $E[a,j]=\infty$ für $j\neq b$: Besuche $b$ von $a$ aus, nicht von einer anderen Stadt her.
# $E[b,a]=\infty$: Der Rückweg von $b$ zu $a$ ist verboten, da $a$ bereits besucht wurde.
# $E[i,b]=\infty$ für $i\neq a$: Nur von $a$ besucht man $b$, von keiner anderen Stadt aus.
===Begrenzung und Ablauf===
Um nun dafür zu sorgen, dass der jeweils vielversprechendste Knoten expandiert wird, benötigen wir eine Bewertungsfunktion. Diese soll für die (modifizierte) Entfernungsmatrix eines aktuellen Blattes des sich entwickelnden Baumes eine Schranke bestimmen. Im Falle des TSP muss dies eine untere Schranke für die Länge der kürzesten Rundreise, die auf diesem Weg erzielbar ist, sein. Für die Bewertungen zweier expandierbarer Knoten entscheidet man sich für den mit der besseren Bewertung, um die Expansion mit diesem fortzusetzen. Für diese Entscheidung werden alle aktuell expandierbaren Knoten herangezogen.
Bei der Suche einer geeigneten Bewertungsfunktion machen wir uns folgende Überlegung zunutze: Wenn man die gegebene Entfernungsmatrix $E$ normiert, d.h. alle Zeileneinträge um das jeweilige Zeilenminimum verringert und anschließend alle Spalteneinträge um das jeweilige Spaltenminimum reduziert, ergibt sich eine Matrix $\hat{E}$. Dies entspricht der Idee, eine Stadt auf dem kürzesten Weg zu betreten und auf dem kürzesten Weg zu verlassen. Die kürzeste Rundreise für eine Städteanordnung mit $\hat{E}$ hat ''mindestens die Länge $0$''. Diese Lösung (Städtefolge) stimmt mit der für $E$ überein, nur dass die Rundreiselänge größer ist. Hieraus ergibt sich eine untere Schranke für die kürzeste Rundreise für $E$ aus der ''Summe aller wie oben gebildeten Zeilen- und Spaltenminima''. Abb. w illustriert das beschriebene Vorgehen der Matrixbewertung für den zunächst nur aus der Wurzel $0$ bestehenden Baum in unserem Beispiel. Die kleinen Zahlen ergeben sich aus der Subtraktion des jeweiligen Zeilenminimums vom ursprünglichen Wert in dem betrachteten Feld von $E$. Die kleinen Zahlen verwendet man anschließend zur Bestimmung der Spaltenminima. Im Beispiel beträgt die untere Schranke $35$.
<!--
| | 0 | 1 | 2 | 3 | '''Min'''|
| --- | --- | --- | --- | --- | --- |
| '''0''' | $\infty$ | $20_{10}$ | $15_5$ | $10_0$ | '''10'''|
| '''1''' | $8_0$ | $\infty$ | $9_1$ | $8_0$ | '''8'''|
| '''2''' | $6_0$ | $12_6$ | $\infty$ | $13_7$ | '''$6$''' |
| '''3''' | $5_0$ | $10_5$ | $9_4$ | $\infty$ | '''$5$''' |
| '''Min''' | '''$0$''' | '''$5$''' | '''$1$''' | '''$0$''' | '''$\mathbf{35}$''' |
-->
{| class="wikitable" style="text-align:right; vertical-align:middle;margin:0 auto;"
|- style="font-weight:bold;"
!
! 0
! 1
! 2
! 3
! '''Min'''
|-
| '''0'''
| $\infty$
| $20_{10}$
| $15_5$
| $10_0$
| '''$10$'''
|-
| '''1'''
| $8_0$
| $\infty$
| $9_1$
| $8_0$
| '''$8$'''
|-
| '''2'''
| $6_0$
| $12_6$
| $\infty$
| $13_7$
| '''$6$'''
|-
| '''3'''
| $5_0$
| $10_5$
| $9_4$
| $\infty$
| '''$5$'''
|-
| '''Min'''
| '''$0$'''
| '''$5$'''
| '''$1$'''
| '''$0$'''
| '''$\mathbf{35}$'''
|}
<center>Abb. 6: Summe der Zeilen- und Spaltenminima als untere Schranke</center>
Da es nur diesen Wurzelknoten gibt, kann nur dieser im nächsten Schritt ''expandiert'' werden. Entscheidet man sich für den Übergang zu Knoten $3$, erhält man die in Abb. 5 angegebene Entfernungsmatrix, die man dem nun aktuellen Blatt zuordnet.
Das zugehörige Bound beträgt wiederum $34$, s. Abb. 7.
<!--
|0>>3| 0 | 1 | 2 | 3 | '''Min''' |
| --- | --- | --- | --- | --- | --- |
| '''0''' | $\infty$ | $\color{red}\infty$ | $\color{red}\infty$ | $10_0$ | '''$10$''' |
| '''1''' | $8_0$ | $\infty$ | $9_1$ | $\color{red}\infty$ | '''$8$''' |
| '''2''' | $6_0$ | $12_6$ | $\infty$ | $\color{red}\infty$ | '''$6$''' |
| '''3''' | $\color{red}\infty$ | $10_{\color{red}1}$ | $9_{\color{red}0}$ | $\infty$ | '''$\color{red}9$''' |
| '''Min''' | '''$0$''' | '''${\color{red}1}$''' | '''${\color{red}0}$''' | '''$0$''' | '''$\mathbf{{\color{red}{34}}}$''' |
-->
{| class="wikitable" style="text-align:right; vertical-align:middle;margin:0 auto;"
|- style="font-weight:bold;"
! 0>>3
! 0
! 1
! 2
! 3
! '''Min'''
|-
| '''0'''
| $\infty$
| $\color{red}\infty$
| $\color{red}\infty$
| $10_0$
| '''$10$'''
|-
| '''1'''
| $8_0$
| $\infty$
| $9_1$
| $\color{red}\infty$
| '''$8$'''
|-
| '''2'''
| $6_0$
| $12_6$
| $\infty$
| $\color{red}\infty$
| '''$6$'''
|-
| '''3'''
| $\color{red}\infty$
| $10_{\color{red}1}$
| $9_{\color{red}0}$
| $\infty$
| '''$\color{red}9$'''
|-
| '''Min'''
| '''$0$'''
| '''${\color{red}1}$'''
| '''${\color{red}0}$'''
| '''$0$'''
| '''$\mathbf{{\color{red}{34}}}$'''
|}
<center>Abb. 7: Bewertung des Knotens $0\rightarrow3$</center>
Die $34$ bedeutet, dass es nicht möglich ist, auf diesem Weg eine kürzere Rundreise zu erzielen, als die der Länge $34$. Die tatsächliche minimale Rundreise könnte also durchaus die Länge $40$, jedoch nicht $30$, haben.
Da der Knoten $0$ durch mögliche Übergänge zu $1$ und $2$ und der Knoten $3$ nach $0\rightarrow 3$ weiterhin expansionsfähig sind, ist ein Bound-Vergleich erforderlich: Wegen $34<35$ wird der Knoten $3$ als nächster expandiert. Geschieht dies mit $3\rightarrow 1$, ergibt sich ein Bound von $35$. Wegen $34<35$ wird wiederum Knoten $3$ expandiert. Hierfür bleibt noch der Übergang $3\rightarrow 2$, was allerdings zu einem Bound von $39$ führt. Da es danach zwei Knoten, nämlich $0$ und $0\rightarrow 3\rightarrow 1$, mit einem Bound von $35$ gibt, ist es gleichgültig, welchen Knoten man als nächstes expandiert. Entscheidet man sich für $0\rightarrow 3\rightarrow 1\rightarrow 2$, ergibt sich wieder ein Bound von $35$. Folglich ist es notwendig, die Wurzel des Baumes, also Knoten $0$ zu expandieren. Sowohl für $0\rightarrow 1$ als auch $0\rightarrow 2$ erhalten wir $40$, sodass wir keine Chance haben, einen kürzeren als den gefundenen Rundweg $0\rightarrow 3\rightarrow 1\rightarrow 2\rightarrow 0$ mit einer Länge von $10+10+9+6=35$ zu finden.
Es ist sehr wichtig, abschließend den Expansionsbaum zur Protokollierung des Ablaufs zu notieren, s. Abb. 8. Die jeweils expansionsfähigen Knoten dieses Baumes sind Wege, die von der Wurzel zu einem der betrachteten Knoten führen, nicht etwa die Knoten selbst. Als Repräsentation der Knoten des Baumes eignen sich die modifizierten Entfernungsmatrizen mit den zugehörigen Bounds.
[[Datei:BnB_TSPBound.png|center|500px]]
<center>Abb. 8: Vollständiger Expansionsbaum</center>
Der in Abb. 8 dargestellte Baum wird durch Branch and Bound nicht vollständig aufgebaut. Die grau dargestellten Teile entfallen, da die Expansionen chancenlos wären. Durch diese Einsparung kann eine Effizienzverbesserung erzielt werden. Eine Verbesserung der Komplexitätsordnung ist nicht zu erwarten.
''Alternative Lösungsraumstruktur'': Der Entscheidungsbaum kann auch binär strukturiert werden, sodass man für jeden Knoten entscheidet, ob eine mögliche Kante dem Weg hinzugefügt (linker Ast) oder nicht aufgenommen (rechter Ast) wird. Es lohnt sich, auch diese Form zu bearbeiten.
===Implementation===
Die Entfernungsmatrix kann sehr einfach als zweidimensionales Array erstellt werden. Zur Repräsentation von Unendlich bieten die meisten höheren Programmiersprachen eine entsprechende Möglichkeit. Mit den Hilfsfunktionen <tt>>delta</tt> und <tt>>modify</tt> erfolgt die Berechnung der Schranke und die Anpassung der Entfernungsmatrix bei Festlegung eines Übergangs. Der eigentliche Algorithmus basiert auf einer Priority Queue die stets den erfolgversprechendsten Knoten zur Expandierung bereitstellt (mit unterer Schranke). Sobald ein Endpunkt erreicht ist (alle Knoten sind im Weg enthalten) ist die kürzeste Rundreise gefunden. Anderenfalls erfolgt die Expansion durch Modifizierung der Matrix und Berechnung der zugehörigen Schranke. Die Begrenzung erfolgt in diesem Fall indirekt durch Zurückstellung (nicht Löschung) der Expansion von Knoten mit einer hohen Schranke.
<code id="5fe9a90e51a33">
import math
import heapq
inf = float("inf")
distanceMatrix = [
[inf, 20, 15, 10],
[8, inf, 9, 8],
[6, 12, inf, 13],
[5, 10, 9, inf]
] # kürzeste Rundreise: 35
def delta(d):
rd = [] # reduzierte Matrix
s = len(d)
delta = 0
for row in range(s):
rowmin = min(d[row]) # Zeilen-Minimum
rd.append([d[row][i] - rowmin for i in range(s)]) # Zeile mit Differenzen
delta += rowmin # Minima summieren
for col in range(s):
colmin = min([rd[i][col] for i in range(s)]) # Spalten-Minimum der Differenzen
delta += colmin # Fehler addieren
return delta
def modify(d, fromP, toP):
m = [] # modifizierte Matrix
s = len(d)
for row in range(s): m.append(d[row].copy()) # Kopie
for row in range(s): # Wege zu toP = unendlich
if row != fromP: m[row][toP] = inf
for col in range(s): # Wege von fromP unendlich
if col != toP: m[fromP][col] = inf
m[toP][fromP] = inf # Weg zurück unendlich
return m
def bnb_TSP(d):
s = len(d)
routes = []
heapq.heappush(routes, (0, ([0], d)))
while len(routes):
node = heapq.heappop(routes) # Knoten mit dem niedrigsten delta
item = node[1]
print("check:",item[0], node[0])
if len(item[0]) == s: # kürzester Weg ist vollständig
return (item[0]+[item[0][0]], node[0])
last = item[0][-1] # zuletzt besuchter Knoten
matrix = item[1] # Ausgangsmatrix
for x in range(s):
# für jeden noch nicht besuchten Knoten der nicht unendlich weit weg ist
if x in item[0] or matrix[last][x] == inf: continue
m = modify(matrix, last, x) # Matrix modifizieren
dt = delta(m) # theoretisch erreichbare Mindestweglänge
print(" extract:", item[0]+[x], dt)
heapq.heappush(routes, (dt, (item[0]+[x], m))) # in Priority Queue einordnen
return "no route"
</code>
<run id="5fe9a90e51bc2">
print("best:", bnb_TSP(distanceMatrix));
</run>