Systematische Suche SS10

Aus ProgrammingWiki

Autoren:

Daniel Horbach (sidahorb@stud.hs-zigr.de)

Richard Hettmann (sirihett@stud.hs-zigr.de)

Rucksackproblem

Das Rucksackproblem ist ein Optimierungsproblem der Kombinatorik. Aus einer Menge von Objekten, die jeweils ein Gewicht und einen Wert haben, soll eine Teilmenge ausgewählt werden, deren Gesamtgewicht eine vorgegebene Gewichtsschranke nicht überschreitet. Unter dieser Bedingung soll der Wert der ausgewählten Objekte maximiert werden. Zur Veranschaulichung dieses klassischen Problems wird auch gerne der Dieb herangezogen, der nur einen kleinen Teil der Beute im Rucksack abtransportieren kann und nun versucht, den größtmöglichen Wert herauszuschlagen.

Gegeben sei eine nichtleere Menge von $n$ Gegenständen, von denen jeder einen Wert $w_i$ und ein Gewicht $g_i$ hat. Da unser Rucksack nicht unbegrenzt belastbar ist, brauchen wir noch die Aufnahmekapazität $K$ , welche keinesfalls durch das aktuelle Gesamtgewicht überschritten werden darf.

Man unterscheidet diese zwei grundsätzlich veschiedenen Arten von Rucksackproblemen.

Bruchteilrucksackproblem

Ein beliebiger Teil $t$ eines jeden Gegenstandes darf eingepackt werden.

$t$ , $0 \% <= t <= 100 \%$

0/1 Rucksackproblem

Jeder einzelne Gegenstand wird entweder vollständig (1) oder gar nicht (0) in den Rucksack aufgenommen.

Wir befassen uns hier nur mit dem 0/1 Rucksackproblem, das Bruchteilrucksackproblem wird in einer der folgenden Vorlesungen näher erläutert.

Ziel

Unser Ziel ist das Erreichen der maximalen Wertsumme ohne die Aufnahmekapazität zu überschreiten.

$\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\}$

Teilmengen-Summen-Problem

Das Teilmengen-Summen-Problem ist ein Spezialfall des Rucksackproblems. Aus einer Menge natürlicher Zahlen $M$ wird eine Teilmenge gesucht, deren Elementensumme möglichst nahe an die Kapazitätsgrenze $K$ herankommt und diese auch erreichen darf. Dieser Spezialfall ergibt sich immer dann, wenn Gewicht und Wert eines jeden Gegenstandes zahlenmäßig überein stimmen.

$M = \{ a_i$ $|$ $1 \leq i \leq n$ und $a_i, n \in N \}$

$g_i = w_i ,$ mit $g_i,w_i \in N$

Dieses Problem entsteht beispielsweise in Transportunternehmen, wenn in einem LKW, dessen Ladekapazität natürlich beschränkt ist, unterschiedliche Frachtgüter befördert werden sollen. Um die Transportkapazität optimal nutzen zu können, also das Fahrzeug nicht zu überlasten oder Transportkapazität zu vergeuden, ist eine sorgfältige Auswahl der Transportgüter nötig.

Intuitives Verfahren

Welche Möglichkeiten haben wir um das Rucksackproblem zu lösen? Natürlich könnte man den Rucksack mit zufällig ausgewählten Gegenständen füllen und danach den einen oder anderen Gegenstand austauschen bis man der Meinung ist man hat das globale Wertmaximum erreicht. Da dieses Verfahren aber weder systenmatisch noch zielführend ist, kann man sich dessen niemals sicher sein. Der bessere Weg ist die Benutzung von Suchstrategien, die dafür sorgen das sämtliche Packmöglichkeiten des Rucksacks erzeugt und anschließend bewertet werden. Mit zwei dieser Strategien werden wir uns näher beschäftigen, der Tiefensuche und der Breitensuche.

Die Graphentheorie

Bevor wir näher auf die Tiefesuche und Breitensuche eingehen, befassen wir uns ersteinmal mit der Graphentheorie. Bei der Graphentheorie handelt es sich um ein Teilgebiet der Mathematik, welches die Eigenschaften von Graphen und deren Beziehung zueinander untersucht. Die Graphentheorie ist in der Hinsicht für die Informatik von Bedeutung, da algorithmische Probleme auf Graphen zurückgeführt werden können.

Ein Graph ist eine Menge von Punkten, diese werden auch als Knoten oder Ecken bezeichnet. Diese Knoten und Ecken sind in der Regel durch Linien miteinander verbunden, diese Linien nennt man auch Kanten oder Bögen.

Vom Knoten 1, welcher der Startknoten ist, gehe ich zum Knoten 2 und von dort zum Knoten 4. Diese 3 Knoten werden der Prewalkliste hinzugefügt. Nach 2 erfolglosen Versuchen Knoten 4 zu expandieren, füge ich ihn auch der Central- und Postwalkliste hinzu. Da keine weitere Expansion erfolgen kann gehe ich mittles Backtracking zu Knoten 2 zurück, berühre ihn zum zweiten Mal und füge ihn der Centalwalkliste hinzu. Knoten 2 kann noch expandiert werden, so komme ich zu Knoten 5 , füge ihn der Prewalkliste, und nach zwei erfolglosen Expansionsversuchen auch der Central- und Postwalkliste hinzu. Ich gehe zurück zu Knoten 2 und nach dem Hinzufügen zur Postwalkliste gehe ich wieder auf den Knoten 1, welcher der nächste in der Centralwalkliste ist. Dasselbe mache ich auch mi dem rechten Teil des Graphen. Ist der Graph vollständig durchlaufen, erhalten ich meine vollständigen Durchlauflisten. Das kann man sich auch im Code-Beispiel unten nochmal genauer ansehen.

walktree anzeigen

(define tree '(1 (2 (4 () ()) (5 () ())) (3 (6 () ()) (7 () ())) )) (define tree2 '(+ (* (3 () ()) (4 () ())) (- (5 () ()) (6 () ())) )) (define pre '()) ;Prewalk-Liste (define cen '()) ;Centralwalk-Liste (define pos '()) ;Postwalk-Liste (define walk (lambda ls ;durchlaufen (main_walk (car ls)) (and (display 'Tree-Liste:) (newline) (display (car ls)) (newline)(newline) (display 'Prewalk-Liste:) (newline) (display pre) (newline)(newline) (display 'Centralwalk-Liste:) (newline) (display cen) (newline)(newline) (display 'Postwalk-Liste:) (newline) (display pos)(newline) ) (set! pre '()) (set! cen '()) (set! pos '()) )) (define main_walk (lambda ls (set! ls (car ls)) (cond ((null? ls) ()) (else (and (set! pre (append pre (list (car ls))));Pre (main_walk (cadr ls)) ;rekursiver Aufruf (set! cen (append cen (list (car ls))));Central (main_walk (caddr ls)) ;rekursiver Aufruf (set! pos (append pos (list (car ls))));Post )) ) ))

(walk tree)

(walk tree2)

Tiefensuche

Die Depth-First-Search ist ein Verfahren zum Suchen eines Knotens in einem Graphen und gehört zu den uniformierten Suchalgorithmen. Expandiert wird der jeweils zuerst auftretende Nachfolgeknoten des Startknotens bis entweder das gesuchte Element gefunden wurde, oder keine weiteren Knoten für die Expansion vorhanden sind. In diesem Fall kehrt der Algorithmus zum zuletzt expandierten Knoten zurück und sucht einen alternativen Nachfolger. Sollte es keinen Nachfolger mehr geben, geht der Algorithmus Schritt für Schritt zum jeweiligen Vorgänger zurück und versucht es dort erneut, bis auf diese Weise entweder ein Ergebnis gefunden oder der komplette Graph einmal durchlaufen wurde.

Algorithmus

Bestimmung des Startknotens
Expandieren des ersten Knotens und speichern sämtlicher Nachfolger in einem Stack
Rekursiver Aufruf der Tiefensuche für jeden Knoten im Stack
Abbruch bei leerem Stack oder wenn das gesuchte Element gefunden wurde

Eigenschaften

Der Speicherplatzbedarf bei der Tiefensuche ist linear. Da im schlimmsten Fall alle möglichen Knoten betrachtet werden müssen lässt sich der Zeitaufwand durch $\mathcal{O} (|V|+|E|)$ beschreiben, wobei |V| für die Anzahl der Knoten und |E| für die Anzahl der Kanten steht. Bei einem unendlichen Graphen ist Tiefensuche nicht vollständig, es ist möglich das ein existierendes Ergebnis nicht gefunden wird. Betracht man die Optimalität trifft dies bei der Tiefensuche nicht zu, weil möglicherweise ein Ergebnis gefunden wird, welches tiefer im Graphen liegt als ein anderes und die Tiefensuche den Graphen erst komplett auf der linken Seite durchsucht.

Anwendung

Tiefensuche findet indirekt Anwendung bei vielen komplexen Algorithmen für Graphen, zum topologischen Sortieren und in Expertensystemen.

Aufbau des Suchbaumes

Bei der Tiefensuche ist der Baum von links aufgebaut und wird als eine Art Protokoll generiert. Da wir hier nur das 0/1 Rucksackproblem behandeln ist an jedem Knoten auch nur eine JA/NEIN Entscheidung möglich. Man spricht hier von einem dynamischen Baum, d.h. jeder Gegenstand wird eingepackt und am nächsten Knoten wird wieder anders entschieden als vorher. Das sogenannte Backtracking bedeutet das Zurückspuren zum letzten Entscheidungspunkt.Bei der Tiefensuche hat man einen aktuellen Rucksackinhalt, dieser wird beschrieben mit s-ls (). Eine Gegenstandsliste mit den Werten (30 50 10) diese wird mit g-ls beschrieben. Den aktuellen Packzustand des Rucksacks beschreiben wir durch (g-ls s-ls).

Berechnungen

Für n Gegenstände ergeben sich im allgemeinen $2^n$ Blätter.

$\sum_{k=0}^n {n\choose k} z^k = {n\choose 0} z^0 + {n\choose 1} z^1 + . . . + {n\choose n} z^n = (1+z)^n$ , für z = 1

Hierdurch ergibt sich ein exponentieller Aufwand $\mathcal {O} (2^n)$ .

Die Anzahl der Knoten lässt sich durch folgende Formel berechnen: $\sum_{k=0}^n 2^k = 2^n^+^1 - 1$ Knoten

Die rekursive Tiefensuche mit Scheme

Das folgende Beispiel hat keine Kapazitätsgrenze, wodurch wir alle möglichen Ergebnisse ausgegeben bekommen.

rucksack1 anzeigen

(define rucksack1 (lambda (g-ls s-ls) (display 'rucksack1) (display g-ls)(display s-ls)(newline) (if (null? g-ls) (begin (display s-ls)(newline)) (begin (rucksack1(cdr g-ls)(cons(car g-ls)s-ls)) (display '-) (rucksack1(cdr g-ls)s-ls)))))

Die Werte sind hier keine Vorgabe, es können andere und mehr gewählt werden.

(rucksack1 '(30 50 10) '())