Systematische Suche SS09
Inhaltsverzeichnis |
Rucksackprobleme
Stellen Sie sich vor, Sie wollen von einem Ort A zu einem Ort B kommen und haben für diesen Weg einen Rucksack dabei, damit Sie verschiedene Gegenstände, welche ein Gewicht und einen Wert haben transportieren wollen. Das Problem ist, dass der Rucksack nur eine Gesamtkapazität hat, die nicht überschritten werden darf. Die Aufgabe besteht nun darin, den Rucksack so zu füllen, dass die Wertsumme der eingepackten Gegenstände, unter Beachtung seiner Kapazitätsschranke, maximal ist.
Man unterscheidet dabei in zwei Formen:
- der Gegenstand wird vollständig eingepackt oder nicht
- der Gegenstand wird teilweise eingepackt
Wir betrachten nur die erste Form, dass der Gegenstand vollständig oder gar nicht eingepackt wird.
Betrachten wir das Ganze mal mathematisch :
Es gibt verschiedene Gegenstände x_i , mit einem bestimmten Gewicht g_i und einem Wert w_i . Dazu kommt dann die Kapazität des Rucksacks K .
Die Optimierungsaufgabe ist die maximale Wertsumme bei Nichtüberschreitung der Kapazitätsbeschränkung: \sum \limits _{i =1}^n {x_i w_i} \to max , wobei \sum \limits _{i =1}^n {x_i g_i} \leq K , mit x_i \in \{0,1\}
Tiefensuche
Die Tiefe-zuerst-Suche, englisch depth-first search oder kurz Tiefensuche, ist ein Verfahren zum Suchen eines Knotens in einem Graphen. Sie zählt zu den uniformierten Suchalgorithmen.
Wie ist der Graph oder Entscheidungsbaum nun aufgebaut?
Da es sich in diesem Kapitel nur um das 0/1 Rucksackproblem handelt, kommt es in jedem Knoten zu eine Ja/Nein-Entscheidung. Wird der Baum wärend einer Suche generiert, als eine Art Protokol spricht man von einem dynamischen Baum.
Wie sieht so ein Baum nun aus und welche Eigenschaften hat er?
Gehen wir mal davon aus, dass man n Gegenstände hat. Allgemein ergeben sich dann für n Gegenstände 2^n Blätter. Anhand des Baumes kann man das auch mit folgender Formel nachrechnen:
\sum \limits _{k=0}^n {n \choose k}z^k = {n \choose 0}z^0+...+{n \choose n}z^n = (1+z)^n , für z = 1
Die Anzahl der Knoten kann man mit folgender Formel berechnen:
\sum_{k=0}^n 2^k = 2^n^+^1 -1Die Anzahl der Kanten kann man wie folgt berechnet werden:
\vert E \vert = \vert V \vert -1Für die Erzeugung eines gesamten Baumes hat man einen exponentiellen Aufwand von \mathcal{O} (2^n) .
Kommen wir zur Laufzeit der Tiefensuche:
Da im schlimmsten Fall alle möglichen Pfade zu allen möglichen Knoten betrachtet werden müssen, beträgt die Laufzeit von Tiefensuche \mathcal{O}(\vert V \vert + \vert E \vert) ,
Anzahl der Knoten \vert V \vert
Anzahl der Kanten \vert E \vert
rekursive Tiefensuche mit Scheme:
<eval> (trace rucksack1) (rucksack1 '(30 50 10) '()) </eval>
Breitensuche
Diese Form der Suche erstreckt sich über gesamte Breite, daher werden erst alle Knoten mit Wurzelabstand k, mit k=1 und dann alle mit k+1, dann mit k+2, usw... entdeckt. Alle Knoten müssen vom Startknoten aus erreichbar sein. Man nennt diese Suche auch Breite-zuerst Suche ( englisch: „breadth-first search“ ).
Die Darstellung in Bäumen dient zur Veranschaulichung des Suchprozesses. Außerdem sind die Berechnungen der Aufwände sowie allgemeinen Berechnungen bei Bäumen bekannt.
Alle hier beschrieben Graphen sind ungewichtete Graphen, bedeutet sie sind nicht gewichtet bzw. haben das Gewicht Eins.
Ein Graph heißt Baum, falls er zusammenhängend ist und keinen Kreis enthält. Aus diesem Grund können diese Begriffe in diesem Zusammenhang synonym verwendet werden.
Arbeitsweise:
Am Anfang ist nur der Startknoten bekannt.
Im ersten Schritt werden alle Knoten entdeckt, welche durch eine (k=1) Kante verbunden ist.
Im zweiten Schritt werden alle Knoten entdeckt, welche eine Entfernung von k=2 vom Startknoten. Dies wiederholt sich bis alle Knoten entdeckt sind.
Der kürzeste Abstand ist die minimale Anzahl von Kanten über alle Pfade von der Wurzel bis zum Knoten. Der kürzeste Pfad eines Knotens beschreibt die Länge von dem Startknoten bis hin zu diesen Knoten.
Sei G = (V, E) ein Graph und s Element von V ein beliebiger Knoten. Dann gilt für jede Kante (u,v) in E
\delta (s, v) <= \delta(s, u)+1.
Nichtdeterminismus
Wir haben die Baumstruktur verwendet um Suchprozess zu verdeutlichen, dieser existiert nicht real. Da viele Verzweigungen entstehen können, die zu gleichen bzw. ähnlichen Code führt wird Rekursion verwendet. Hier wird deskriptiv programmiert, also es wird das „Wunsch-Blatt“ angegeben und die Schritte die dahin führen müssen nicht explizit durch den Programmierer angegeben werden. Da wir nicht wissen dass solch ein Blatt existiert, handelt sich um einen nichtdeterministischen Algorithmus.