Systematische Suche SS09

Aus ProgrammingWiki

Autoren:
Martin Schicht simaschi@ stud.hs-zigr.de
Martin Klemm   simaklem@ stud.hs-zigr.de

Rucksackproblem

Das Rucksackproblem oder engl. Knapsack Problem ist ein Optimierungsproblem der Kombinatorik.

Zu Beginn sollten erstmal einige Begriffe geklärt werden. Man hat eine nichtleere Menge von $n$ -Gegenständen und jeder Gegenstand hat einen Wert $w_i$ und ein Gewicht $g_i$ , zudem kommt dann noch der Begriff der Kapazität $K$ , welcher eine Schranke darstellt, die eingehalten werden muss.

Es geht nun darum einen Rucksack so zu füllen, dass die Wertsumme der eingepackten Gegenstände maximal ist und die Kapazitätsschranke eingehalten wird.

Es gibt zwei Arten von Rucksackproblemen. Das Bruchteilrucksackproblem und das 0/1 Rucksackproblem.

Bruchteilrucksackproblem

Der Gegenstand wird teilweise eingepackt, dass bedeutet man kann einen Gegenstand in prozentualen Teilen einpacken oder nicht.

mathematisch:

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

0/1 Rucksackproblem

Der Gegenstand wird komplett (1) oder gar nicht (0) eingepackt.

Wir betrachten auf dieser Wikiseite nur die zweite Form, dass der Gegenstand vollständig oder gar nicht eingepackt wird.

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

Teilmengen-Summen-Problem

Einen Spezialfall des Rucksackproblems ist das Teilmengen-Summen-Problem oder engl. subset-sum problem.

Gegeben sei dafür eine Menge natürlicher Zahlen und gesucht ist eine Teilmenge, deren Elementsumme möglichst nahe an die Vorgabezahl ( Kapazität $K$ heran kommt, diese aber auch erreichen darf. Dieses Problem tritt ein, wenn das Gewicht und der Wert eines Gegenstandes zahlenmäßig übereinstimmen.

Betrachten wir es wieder mathematisch:

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

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

Zur Anwendung kommt das Teilmengen-Summen-Problem zum Beispiel bei Transportunternehmen, wenn man einen LKW optimal Beladen will, also die Ladekapazität optimal nutzen will ohne sie zu überschreiten.

Lösungsmöglichkeiten für das Rucksackproblem

Wie kann man das Rucksackproblem nun lösen? Man könnte es durch ein intuitives Verfahren versuchen, indem man den Rucksack zufällig befüllt und nachträglich Gegenstände gegen andere austauscht um den Gesamtwert zu erhöhen, dass hat aber zur Folge, dass man nie weiß, wann das Wertmaximum erreicht ist.

Eine bessere Möglichkeit ist es den Rucksack mit Hilfe von Suchalgorithmen, wie der Tiefensuche oder der Breitensuche zu lösen. Die Wahl des Verfahrens hängt vom jeweiligen Problemtyp und der Aufgabenstellungen ab. Außerdem kann entscheidend sein, was gesucht wird, zum Beispiel eine schnelle Lösung oder alle existierenden Lösungen.

Grundlegende Graphentheorie

Aufbau eines Graphen

Dieser Absatz soll dazu dienen, die Grundbegriffe der Graphentheorie und unsere allgemein verwendete Darstellung darzulegen. Ein Graph besteht aus Kanten (engl.: Edge) und Knoten (engl.: Vertex). Die Knoten sind durch Kanten verbunden. Je nachdem auf welche Art und Vielfalt das geschieht, entstehen unterschiedliche Varianten von Graphen.

Eine Variante ist ein Baum. Ein Baum besitzt eine Wurzel. Von dieser Wurzel (auch Startknoten genannt) gehen eine oder mehrere Kante zu neuen Knoten ab. Von diesen wiederum können neue Kanten abzweigen.

Bei einem Binärbaum kann jeder Knoten maximal 2 Kanten haben. Aufgrund dieser Struktur ist er in der Informatik sehr verbreitet, da jeweils die beiden Kanten mit $0$ oder $1$ dargestellt werden können.

Auf dieser Seite werden wir die Knoten wie folgt darstellen:

Knoten = Rucksackliste und Gegenstandliste

Die Elemente dieser Listen bezeichnen die Gegenstände. Eine leere Rucksackliste und eine Gegenstandsliste mit 3 Gegenständen würde so aussehen:

Die Kanten repräsentieren einen alternativen Weg, wo ein Gegenstand der Gegenstandliste entnommen und der Rucksackliste hinzugefügt wird.

Graphendurchlauf

Wenn man einen Graphen durchläuft, dann passiert man die Knoten in einer bestimmten Reihenfolge. Bei der ersten Berührung eines Knoten spricht man von einem Prewalk und passiert man den Knoten dann zum zweiten Mal, ist das der Centralwalk und bei der dritten Berührung spricht man vom Postwalk. Dies ist aber nur bei einem gegebenen Graphen möglich!

Beispiel:

Wir haben einen Binärbaum mit den Knoten 1 bis 7 und führen daran eine Tiefensuche durch.

Ich beginne bei dem Wurzelknoten 1 und gehe zum Knoten 2 und von da zum Knoten 4. Somit habe ich meine ersten 3 Knoten, die ich dem Prewalk hinzufüge. Anschließend versuche ich bei Knoten 4 weiter in die Tiefe zu gehen und da das nicht geht, komme ich wieder zu Knoten 4 und habe meinen ersten Knoten für den Centralwalk. Da ich nun auch noch die andere Kante von Knoten 4 untersuchen muss und wieder zu 4 komme, ist 4 ebenfalls der erste Knoten des Postwalk. Anschließend gehe ich zu Knoten 2 zurück und berühre ihn zum zweiten Mal und füge ihn der Centralwalkliste hinzu. Von da aus gehe ich nun zu Knoten 5 und berühre ihn zum ersten Mal und füge ihn dem Prewalk hinzu. Dann mache ich das selbe nochmal und füge ihn der Centralwalk- und Postwalkliste hinzu. Dann komme ich wieder zurück zum Knoten 1 und berühre ihn zum zweiten Mal und füge ihn der Centralwalkliste hinzu. Nun gehe ich zu Punkt 3 und vollziehe die gleiche Prozedur wie bei Knoten 4 und 5 durch. Ist der Graph vollständig durchlaufen, erhalten ich meine vollständigen Durchlauflisten. Das kann man sich auch im Code-Beispiel unten nochmal genauer ansehen.

;Voraussetzung: Der Baum muss bekannt sein. (INPUTgröße) ;Baumdefinitionen nach Syntax: ;(parent child_left child_right) ;Wenn ein Knoten keine Childs hat, dann muss dies durch eine leere Liste repräsentiert werden! ;natuerlich verschachtelbar :) (define tree '(1 (2 (4 () ()) (5 () ())) (3 (6 () ()) (7 () ())) )) (define tree2 '(+ (* (3 () ()) (4 () ())) (- (5 () ()) (6 () ())) )) ;Definitionen der Walk-Listen (define pre '()) ;Prewalk-Liste (define cen '()) ;Centralwalk-Liste (define pos '()) ;Postwalk-Liste ;Prozedur zum Durchlaufen des Baumes / tree traversal (define walk (lambda ls ;durchlaufen (main_walk (car ls)) ;Ausgabe der Listen: ;( Muss extern geschehen, da Prozedur (main_walk ls) rekursiv aufgerufen wird ; und nur eine Ausgabe stattfinden soll ) (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) ) ;Liste leeren, da mehrfache Aufrufe zu immer weiter expandierdenen Listen führen würden (set! pre '()) (set! cen '()) (set! pos '()) )) ;'eigentlicher' Durchlauf / tree traversal (define main_walk (lambda ls ;Input-Liste, quasi der Baum (set! ls (car ls)) (cond ((null? ls) ()) (else ;Erklärung: Je nach dem in welcher Zeile jeweils die Liste expandiert wird, ; enstehen die unterschiedlichen Listen (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 )) ) )) ;Verbesserungen: (optional) ; Listendefinition mit define durch let/letrec-Ausdrücke ersetzen, damit Nebenwirkungen von z.B.: SET! nicht verschwinden. ;Programmier-Erkenntnis des Tages: Ein Liste ist nicht leer, wenn sie eine leere Liste erhält!

Mit Hilfe dieser Prozeduren kann man sich die Walk-Listen anzeigen lassen:

(walk tree)

(walk tree2)

Der Durchlauf von 'tree2 und dessen Listen bringen uns zu einer interessanten Erkenntnis.

Die Prewalk-Liste sieht folgendermaßen aus:

Nun fügen wir diesem Ausdruck die Scheme-Syntax, hier nur noch die Klammerung, hinzu:

Diesen Ausdruck kann man sich in Scheme evaluieren lassen:

(eval '(+ (* 3 4) (- 5 6)))

Hier die Centralwalk-Liste:

Man erkennt hier die typische Notation, die uns aus der Mathematik bekannt ist. In Tabellenkalkulationsprogrammen oder Java oder auf Papier liefert uns die Ausführung von

das Ergebnis $11$ .

Beide Ergebnisse stimmen überein und wir haben aus der Baumstruktur 2 Wege gefunden, die den Operationsbaum (tree2) auf verschiedene Weise interpretieren.

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.

Der Algorithmus

1. Bestimme den Knoten mit dem die Suche beginnen soll.

2. Betrachte die erste Kante.

3. Wenn der nächste Knoten erweiterbar ist, wird wieder expandiert.

4. Kann nicht expandiert werden, gehe mittels backtracking zum darüber liegenden Knoten zurück und betrachte eine alternative Kante.

5. Ist kein Knoten mehr expandierbar, wurden alle Ecken bereits besucht.

Suchbaum

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 einer Ja/Nein-Entscheidung. Wird der Baum während einer Suche generiert, als eine Art Protokol spricht man von einem dynamischen Baum. Praktisch heißt das, jeder Gegenstand wird eingepackt, man nimmt den jeweils letzten wieder heraus und eintscheidet sich in jedem Knoten anders als vorher (Backtracking).

Man kann aus jedem Graphen der Tiefensuche einen Binärbaum umformen. Wichtig ist die Kombination der Gegenstände und nicht die Reihenfolge wie sie eingepackt werden. Ein binärer Tiefensuchbaum ist uniform, das bedeutet er hat einen konstanten Verzweigungsgrad und eine einheitliche Tiefe. Der gesuchte Zielknoten liegt mit gleicher Wahrscheinlichkeit in der Maximaltiefe d ( ganz unten im Suchbaum).

Berechnungen

Anzahl der Knoten:

$\vert V \vert = \sum_{k=0}^n 2^k = 2^{n+1} -1$

Anzahl der Blätter:

$2^n$

Anzahl der Kanten:

$\vert E \vert = \vert V \vert -1$

Die Tiefensuche hat folgende Eigenschaften. Sie hat eine Komplexität von $\mathcal{O} (\vert V \vert+\vert E \vert)$ und im worst case müssen alle Knoten betrachtet werden. Sie liefert auch nicht optimale Lösungen und der Speicherplatzbedarf ist linear. Aber das Ergebnis kann schneller gefunden werden, als bei der speicheraufwendigen Breitensuche. Für die Erzeugung eines gesamten Baumes mit $n$ Gegenständen hat man einen exponentiellen Aufwand von $\mathcal{O} (2^n)$

rekursive Tiefensuche mit Scheme

In diesem Abschnitt lassen wir die Kapaität $K$ noch außer betracht. Wir schauen uns nur an welche Kombinationen alle möglich sind, wenn wir kein $K$ haben.

(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 '-); Tiefe (rucksack1 (cdr g-ls) s-ls))))); Breite

Es können auch andere Werte als 30, 50 und 10 oder mehr gewählt werden.

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

Tiefensuche mit Beschränkung

In diesem Abschnitt fangen wir nun an, die Kapazität $K$ mit zu beachten, das heißt sie darf nicht überschritten werden. Sobald $K$ erreicht oder überschritten ist, wird die Suche weiter in die Tiefe abgebrochen und es wird mit dem letzten Knoten davor, der noch eine weitere noch nicht untersuchte Kante hat fortgesetzt. Sind alle Kanten und Knoten schon betrachten worden, dann ist die Suche komplett durchgeführt und es stehen die entgültigen Ergebnisse fest, welche die Bedingung erfüllen.

Beim ersten Codebeispiel werden wieder alle möglichen Kombinationen gesucht und angezeigt, welche das $K$ nicht überschreiten.

;;; Tiefensuche mit Beschraenkung (define rucksack2 (lambda (g-ls s-ls k) (display 'rucksack1) (display g-ls)(display s-ls)(newline) (if (null? g-ls) (begin (display s-ls) (newline)) (begin (if (hoechstens-maxgewicht? s-ls k) (rucksack2 (cdr g-ls) (cons (car g-ls) s-ls) k)) (if (hoechstens-maxgewicht? s-ls k) (rucksack2 (cdr g-ls) s-ls k)))))) (define hoechstens-maxgewicht? (lambda (ls k) (<= (apply + ls) k)))

Es kann anstatt der 42 auch eine beliebige andere Kapazität gewählt werden. Auch hier können für die 30, 50 und 10 andere Werte gewählt werden.

(rucksack2 '(30 50 10) '() 42)

Beschränkte Tiefensuche mit Ergebnisliste:

In diesem Codebeispiel wird nun auch die optimale Lösung angezeigt.

;;; Beschraenkte Tiefensuche mit Ergebnisliste (define rucksack3 (lambda (g-ls k) (let ((max 0) (max-s-ls '())) (letrec ((helfer (lambda (g-ls s-ls) (display s-ls)(newline) (if (null? g-ls) (let ((gesamtgewicht (apply + s-ls))) ; apply wendet + auf die Liste an. (if (and (> gesamtgewicht max) (hoechstens-maxgewicht? s-ls k)) (begin (set! max gesamtgewicht) (set! max-s-ls s-ls))) (cons max-s-ls max)) (begin (if (hoechstens-maxgewicht? s-ls k) (helfer (cdr g-ls) (cons (car g-ls) s-ls))) (if (hoechstens-maxgewicht? s-ls k) (helfer (cdr g-ls) s-ls))))))) (helfer g-ls '())))))

(rucksack3 '(30 50 10) 42)

Breitensuche

Die Breitensuche ist einer der einfachsten Algorithmen für das Durchsuchen eines Graphen. Die Idee findet in anderen Problemen (zum Beispiel die Bestimmung des minimalen Spannbaumes nach Prim und für den Algorithmus von Dikstra für das Problem der kürzesten Pfade) Anwendung.

Der Name beruht auf der Eigenschaft dieser Suche, da sie sich gleichmäßig über die gesamte Breite erstreckt. Das bedeutet im ersten Schritt werden alle Knoten entdeckt, die einen Abstand zum Wurzelknoten 1 haben. Anschließend werden alle Knoten entdeckt, die einen Abstand von 2 haben und so weiter.

Dieser Algorithmus arbeitet sowohl für gerichtete als auch für ungerichtete Graphen.

Suchbaum

Folgendes Bild zeigt einen vollständigen Suchbaum für die Gegenstände '(30, 50, 10) mit dem man sich die Breitensuche veranschaulichen kann, quasi als „Nebenprodukt“ der Breitensuche:

Ein Knoten ist wiefolgt aufgebaut: Rechts vom Strich steht die Gegenstandsliste (welche alle Gegenstände enthält) und links davon die Rucksackliste. Anfangs, ist die Rucksackliste leer. Im ersten Schritt wird nun zu jedem möglichen Gegenstand der entnommen werden kann eine neue Kante erzeugt, dieser Gegenstand kommt also in die Rucksackliste. Im 2.Schritt bilden wieder von jedem Knoten alle möglichen zu entnehmenden Gegenstände eine Kante zu neuen Knoten. Dies wiederholt sich solange, bis für alle Knoten die Gegenstandsliste leer ist.

Ein schönes Bild, was diese Suchabarbeitung verdeutlicht hier:

Da in jedem Schritt ein Gegenstand entommen wird, verringert sich die Kantenanzahl für jede Ebene auch um eins, bedeutet, dass vom Wurzelknoten 3 Kanten abgehen (für 3 Gegenstände) und in der nächsten Ebene jeweils 2 und in der 3,Ebene nur noch jeweils eine Kante, da ja nur noch ein Gegenstand zu entnehmen ist.

Berechnung

Anzahl der Knoten

Anfangs hat man 1 Startknoten. In der nächsten Ebene erhält man genauso viele Knoten wie es Gegenstände gibt, also n. Geht man wieder eine Ebene tiefer, so hat man jetzt $n$ Knoten und von jedem Knoten gehen jetzt $(n-1)$ Kanten ab, also $n*(n-1)$ . Auf der vorletzten Ebene erhält man genau $(n-(n-1))$ , also es bleibt genau noch 1 Gegenstand übrig, der entnommen werden kann. So kommt der letzte partielle Term zustande. Addiert man alle diese Zahlen, dann entsteht folgende Formel:

$1+n+n(n-1)+n(n-1)(n-2)+...+n(n-1)(n-2)(n-3)...(n-(n-1))$

$= \frac{n!}{0!} + \frac{n!}{1!} + \frac{n!}{2!} + ... + \frac{n!}{n!}$

$= \sum_{k=0}^n \frac{n!}{k!}$

Für unser Beispiel mit der Gegenstandsliste '(10, 30, 50) entsteht folgendes Ergebnis:

$=1+3+3(3-1)+3(3-1)(3-2) = 1 + 3 + 3*2 + 3*2*1 = 1 + 3 + 6 + 6 = 16 Knoten$

$=3!/0! + 3!/1! + 3!/2! + 3!/3! = 6/1 + 6/1 + 6/2 + 6/6 = 6 + 6 + 3 + 1 = 16 Knoten$

Anzahl der Kanten

Aufgrund der speziellen Abarbeitung der Breitensuche kann man die Kantenanzahl leicht durch folgende Formel bestimmen:

$Anzahl\ der\ Kanten\ =\ Anzahl\ der\ Knoten$ $- 1$

Für unser Beispiel mit der Gegenstandsliste $'(10, 30, 50)$ ergeben das:

$16 - 1 = 15$ $Kanten$

Anzahl der Blätter

$2^n = 2^3 = 8\ Bl\"atter$

Algorithmus

Im Anfangszustand kennt der Algorithmus nur den Startknoten s und es ist ein Graph G mit Knoten und Kanten gegeben. Nun erforscht die Breitensuche alle Kanten von G, die von s aus erreichbar sind , um somit alle Knoten der nächsten Ebene zu entdecken. Bei diesem Durchforsten entsteht der Breitensuchbaum. Er dient uns zur Visualisierung und beschreibt den Suchprozess. Als eine der wichtigsten Eigenschaft der Breitensuche liefert er zu jedem gefunden Knoten v den kürzesten Abstand dieses Knotens zu s. Wenn alle Kanten die von s Abzweigen gefunden sind, wird nun der erste Knoten der nächsten Ebene auf weitere Kanten untersucht.

Idee der Implementierung

In diesem Abschnitt soll die grundlegende Idee verdeutlicht werden, wie man die Breitensuche implementieren würde. Weiterhin wird damit der allgemeine Ablauf dieser Suche deutlich. Für die Abarbeitung wird eine Liste benötigt. Im Anfangsstadium enthält diese Liste nur den Startknoten.

'(S)

Man nimmt sich den ersten Knotenaus der Liste, dieser wird somit aus der Liste gelöscht. Wenn ein Knoten gefunden wird, wird er an diese Liste hinten angehangen.

'(A,B,C)

Wenn alle Kanten die vom Startknoten ausgehen untersucht worden sind, wird nun das erste Element der Liste entnommen. Nun werden zu dem Knoten A alle Kanten untersucht. Falls ein Knoten gefunden wird, wird dieser an die Liste hinten angehangen. Somit ist gesichert dass erst alle Knoten dieser Ebene untersucht werden.

'(B,C,A1,A2)

Nun wird wieder das erste Element entnommen, hier der Knoten B und dieser wird auch auf alle Kanten untersucht. Diese Schleife wird solange wiederholt, bis die Liste leer ist.

'()

Wird der Zielknoten zu einem beliebigen Zeitpunkt gefunden, dann stoppe die Suche mit Erfolg. Wenn die Suche beendet ist und die Liste leer ist, hat dies zur Folge, dass die Suche erfolglos endet.

Hier nochmal der Algorithmus in Kurzform als Pseudocode :

Setzte Startknoten und speichere ihn in einer Warteschlange ab.
Entnehme ersten Knoten
1. Zielknoten gefunden : Beende Suche mit Erfolg
2. ansonsten : hänge alle unmarkierten Nachfolger dieses Knotens an das Ende der Warteschlange
Wiederhole 2. bis Ziel gefunden
Warteschlange leer : Beende Suche mit Misserfolg

Analyse

Speicheraufwand

Bei der Breitensuche muss der komplette bisher besuchte Graph gepseichert werden. Also zu jedem Knoten alle Folge Knoten der nächsten Ebene. Dies ergibt einen expenentiellen Aufwand:

$O(b^d)$ , wobei

b...Verzweigungsgrad

d...max. Tiefe / Anzahl der Ebenen

Dies beansprucht bei komplexeren Problemen sehr sehr viel Speicher, weshalb ist die Breitensuche für größere Probleme ungeeignet ist.

Zeitaufwand

Generell gilt, dass immer alle Knoten der oberen Ebene, also der 'Ebene mit Zielknoten -1' durchsucht werden müssen. Dabei ergeben ich folgende Fälle: best case: erster Knoten der nächsten Ebene ist Zielknoten worst case: letzter Knoten der letzten Ebene ist Zielknoten

Eigenschaften

Die Breitensuche liefert durch ihre spezifische Arbeitsweise immer den kürzesten Pfad zwischen 2 Knoten. Dazu hier ein 2 Definitionen:

kürzester Pfad = Pfad der Länge vom Startknoten bis zum Knoten

kürzester Abstand = minimale Anzahl von Kanten über alle Pfade vom Startknoten bis zum Knoten

Die Breitensuche hat zwei weitere Eigenschaften die diese Suche spezifiziern, sie ist vollständig und fair. Als 2 bekannte Adjektive unsere deutschen Sprache sind sie im Allgemeinen durchaus uch ohne Kontext positiv zu bewerten. Aber was beteuden sie im Hinblick auf die Breitensuche?

Angenommen der linke Pfad würde nicht enden, das heisst es würden immer wieder neue Kanten entdeckt werden, dann würde dies keinen Unterschied bei der Breitensuche machen, denn es werden alle Ebenen mit Abstand (von der Wurzel) 1 und dann 2,3,... usw. untersucht, somit hat dieser "unendliche Pfad" keinen direkten Einfluss auf die anden Kanten einer beliebigen Ebene. Diese Eigenschaft wird als Fairness bezeichness, denn es werden immer alle Kanten fair behandelt.

Die Breitensuche ist für eine endliche Anzahl von Kanten vollständig, das heisst, wenn es eine Lösung existiert wird sie auch gefunden.

Führt man Kantengewichte ein, wie z.B.: Pfadkosten, liefert die Breitensuche nicht das optimale Ergebnis. Deswegen gilt die Breitensuche (im allgemeinen) als nicht optimal. Dieses Problem umgeht man indem man die Breitensuche zur uniformen Kostensuche erweitert.

Damenproblem

Ein Beispiel wofür die Breitensuche gute Ergebnnisse liefert ist das Damenproblem. Das Problem ist folgendes: Auf ein handelsübliches Schachbrett ( $8*8= 64\ Felder$ ) sollen 8 Damen so aufgestellt werden, dass sie sich nicht gegenseitig schlagen können. Hier interessieren uns alle Lösungen die existieren, daher es reicht nicht aus wenn wir ein paar Lösungen haben.

Das Problem wurde erstmals 1848 vom bayrischen Schachmeister Max Bezzel(1824-1871) formuliert.Zwei Jahre später fand Franz Nauck erstmals alle 92 Lösungen des Schachbrettes.Auch Gauß(1777-1855) untersuchte dieses Problem. 1874 wurde der Beweis vom englischen Mathematiker Lee Glaisher(1848-1928) erbracht des es für ein normles Schachbrett nicht mehr als 92 Lösungen geben kann.

Desweiteren müssen wir die Lösungsmenge unterteilen, denn durch Spiegelung oder einfaches Drehen des Schachbrettes entstehen mitunter gleich Lösungen. Für ein normales Schachbrett gibt es insgesamt 92 Lösungen, aber es nur davon 12 eindeutige Lösungen. Nun kann man (wie in der Mathematik und Informatik) nicht mit einem normalen Schachbrett zufrieden sein. Man kann das Prolem auf beliebig $n * n$ große Schachbretter ausweiten.

In der Tabelle werden für einige $n$ die Anzahl der Lösungen angegeben: $\begin{array}{l|l|l|l|l|l|l|l} \text{n} & 1 & 2 & 3 & 8 & 16 & 22 & 25\\ \hline \text{eindeutig}& 1 & 0 & 0 & 12 & 1.846.955 & 336.376.244.042 & 275.986.683.743.434 \\ \hline \text{insgesamt}& 1 & 0 & 0 & 92& 14.772.512 & 2.691.008.701.644 & 2.207.893.435.808.352\\ \hline \end{array}$

So simpel die Lösungen vielleicht bis zu $n=4$ erscheinen mag, desto komplizierter werden und unvorstellbarer werden die Lösungen für größere n. Die Effizienz von Algorithmen trifft hier auf ein reales Problem, denn für $n=23$ wird schon so viel Rechenleistung benötigt, dass auf einem normalen PC es sehr viel Zeit in Anspruch nimmt, das Problem zu lösen. Generell wird derzeit an $n=26$ gerechnet, soll bedeuten dass bisher die Anzahl aller Lösungen nicht bestimmt werden konnte.

reduzierter Breitensuchbaum

Da das Rucksackproblem ein Problem der Kombinatorik ist, kann die Reihenfolge vernachlässig werden. Dies führt uns, wenn man den vollständigen Breitensuchbaum anschaut, dazu dass es Knoten und Blätter gibt,welche die gleiche Rucksack- und Gegenstandsliste haben.

Bei einer Gegenstandsliste mit n Gegenständen führt das dazu dass es nur noch einen Knoten gibt, wo alle Gegenstände eingepackt sind. Also können die Knoten der letzten Ebene:

durch nur 1 Blatt repräsentiert weden. Diesen Sachverhalt kann man dadurch realisieren, das man bei jedem Schritt die Gegenstandsliste reduziert. Die Herangehensweise ist dabei wiefolgt:

Bei der Wurzel ergibt sich keine Veränderung.

Nun wird der erste Gegenstand eingepackt und es entsteht der Knoten:

Im nächsten Schritt wird der 2. Gegenstand mitgenommen, aber da für den ersten Gegenstand ein Knoten bereits existiert, befindet sich nun nur noch Gegenstand 3 in der Gegenstandsliste (rechts vom Strich).

Im letzten Knoten wir der Gegenstand 3 eingepackt. Nun wurden in den bereits existierenden Knoten (dieser Ebene), die Gegenstände ${g}_{1}$ und ${g}_{2}$ eingepackt und eben jetzt der 3.Gegenstand, damit wird aus der Basismenge $'({g}_{1},{g}_{2},{g}_{3})$ eine leere Menge $'()$ . Also sieht der letzte Knoten so aus:

Bisher ist folgender Baum entstanden:

Auf der nächsten Ebene, wird das gleiche gemacht: Man entnimmt zuerst den 2.Gegenstand und es bleit nur noch Gegenstand 3 übrig.

Wenn man nun zu ${g}_{1}$ , ${g}_{3}$ aus der Gegenstandliste entnimmt, ist wieder zu beachten das Gegenstand 2 zuvor entnommen wurde, also ist die Gegenstandsliste (schon) leer.

Führt man die Suche komplett aus, entsteht folgender reduzierter Breitensuchbaum:

Wenn wir die Gegenstände nun durch konkrete Zahen ersetzen, wie in den obrigen Beispielen, dann ergibt sich folgende Baum:

Dieser Baum hat 8 Knoten, diese entsprechen genau mit den 8 Blätter der Tiefensuche überein.

Vergleich

$\begin{array}{l|l|l} \text{Kriterium}& \text{Tiefensuche}& \text{Breitensuche}\\ \hline \text{Schneller, wenn Ergebnis im ... Teil des Suchbaumes ist.} & \text{linken} & \text{rechten}\\ \text{Vollst\"andigkeit, bei endlichen Suchbaum} & \text{ja} & \text{ja} \\ \text{Optimal bzgl. Pfadl\"ange} & \text{nein, liefert auch nicht-optimale L\"osungen} & \text{ja}\\ \text{speichert} & \text{nur f\"ur einen Pfad} & \text{ganzen bisher besuchte Graph} \\ \text{Findet Anwendung, wenn ... gesucht wird.} & \text{zuerst gefundene L\"osung} & \text{alle L\"osungen} \\ \text{Beispiel} & \text{8-Puzzle} & \text{Graphentheorie} \end{array}$

Nichtdeterministische Suche

;;; Nondeterminism ;; amb (which stands for ambiguous) ;; Inventor: McCarthy; MzScheme implementation: Dorai Sitaram ;; Source: "Teach yourself Scheme in Fixnum Days" ;; This is a Chez Scheme implementation. (define amb-fail '*) (define initialize-amb-fail (lambda () (set! amb-fail (lambda () (error "amb" "It fails"))))) (initialize-amb-fail) (define-syntax amb (syntax-rules () ((amb alt ...) (let ((+prev-amb-fail amb-fail)) (call/cc (lambda (+sk) (call/cc (lambda (+fk) (set! amb-fail (lambda () (set! amb-fail +prev-amb-fail) (+fk 'fail))) (+sk alt))) ... (+prev-amb-fail))))))) (define-syntax bag-of (syntax-rules () ((bag-of e) (let ((+prev-amb-fail amb-fail) (+results '())) (if (call/cc (lambda (+k) (set! amb-fail (lambda () (+k #f))) (let ((+v e)) (set! +results (cons +v +results)) (+k #t)))) (amb-fail)) (set! amb-fail +prev-amb-fail) (reverse! +results))))) (define choice (lambda (ls) (eval (cons 'amb (map (lambda (x) (list 'quote x)) ls))))) (define multichoice (lambda (ls n) (if (= n 0) '() (let ((item (choice ls))) (cons item (multichoice (delete item ls) (- n 1))))))) (define delete (lambda (item ls) (cond ((null? ls) '()) ((eqv? (car ls) item) (cdr ls)) (else (cons (car ls) (delete item (cdr ls))))))) (define randomchoice (lambda (n) (letrec ((enumerate (lambda (i) (if (= i 0) '() (cons i (enumerate (- i 1))))))) (let ((numberlist (enumerate n))) (choice numberlist))))) ; ------ examples using nondeterminism ----- (define number-between (lambda (lo hi) (let loop ((i lo)) (if (> i hi) (amb) (amb i (loop (+ i 1))))))) (define assert (lambda (pred) (if (not pred) (amb)))) (define prime? (lambda (n) (letrec ((helper (lambda (i) (cond ((> i (ceiling (sqrt n))) #t) ((zero? (modulo n i)) #f) (else (helper (+ i 2))))))) (cond ((= n 1) #f) ((= n 2) #t) ((= n 3) #t) ((even? n) #f) (else (helper 3)))))) (define gen-prime (lambda (hi) (let ((i (number-between 2 hi))) (assert (prime? i)) i))) ; (bag-of (gen-prime 20)) (define all-divider-of (lambda (n) (let ((i (number-between 2 (- n 1)))) (assert (zero? (modulo n i))) i))) ; (bag-of (all-divider-of 18)) (initialize-amb-fail)

Ein alternative Möglichkeit zu Suchen ist die nichtdeterministische Suche. Aber was bedeutet dies? Unter gewissen Umständen sind wir in der Ausgangsposition dass der Suchbaum nicht bekannt ist, bzw. wir nicht wissen wie groß er ungefähr sein könnte. Durch den Nichtdeterminismus, kurz das zielgerichtete Finden der Lösung, wird hier eine Lösungsalternative untersucht. Man kümmert sich nicht um den Weg zum Ziel, sondern es interessiert nur das Ergebnis. Diese Art nennt man auch deskriptive Programmierung. Vorraussetzung ist, dass falls eine Lösung existiert diese auch gefunden wird. Praktisch gesehen, findet die Suche also zielgerichtet ihren Weg zum Zielknoten.

Mit Scheme steht uns ein Hilfsmittel zur Verfügung um dieses Konzept nachzuvollziehen. Wir benötigen hierführ die Datei $ambiguous.ss$ .

Um mit dieser Datei zu arbeiten, muss sie zuerst initialisiert werden:

(initialize-amb-fail)

Sie definiert unter anderem die Prozedur $choice$ .

 
IN     : Liste
OUT : Gibt „richtiges“ Element aus der Liste zurück, für den Gesamtausdruck aus.

Je nach dem in welchen Ausdruck $choice$ eingebettet ist, wird das Ergebnis geliefert. Solch ein Ausdruck kann z.B.: der Vergleich einer Zahl, ein Anfangswert oder ein enthaltenes Element sein.

Im 1.Beispiel liefert der Ausdruck den Wert $\#t$ , da es in der Liste einen Wert gibt, der kleiner als 4 ist.

(< ( choice '(1 2 3 4 5 6 ) ) 4)

Nun hätten auch die Elemente $2$ und $3$ die Bedingung erfüllt. Um alle Werte zu erhalten gibt es die Prozedur $bag-of$

 
IN     : Ausdruck mit  
OUT : Liste, mit allen Elementen die  unter der Bedingung liefert.

Dazu das passende Beispiel:

( bag-of (< ( choice '(1 2 3 4 5 6 ) ) 4 ) )

Und gleich ein weiteres, welches uns jeweils $\#t$ oder $\#f$ ausgibt, jenachdem ob dass Element eine Liste ist,eben weil sie die Bedingung erfüllen:

(bag-of (list? ( choice '(a () 2 (5) #t ))))

Um einen weiteren Eindruck von diesen Sprachelementen zu bekommen, folgt nun ein weiteres Beispiel. Die Prozedur $summandensucheA$ liefert uns als Ergebnis eine Liste mit 2 Summanden welche addiert mit den als Eingabewert angegeben Wert übereinstimmt.

(define summanden (lambda (ls) (list (choice ls) (choice ls)))) (define summandensucheA (lambda (ls summe) (let ((kandidatenliste (summanden ls))) (if (= (apply + kandidatenliste) summe) kandidatenliste (choice '())))))

(summandensucheA '(0 1 2 3 4 5) 6)

Auch hier sind wieder alle Möglichkeiten interessant:

(bag-of (summandensucheA '(0 1 2 3 4 5) 6))

Im folgenden eine Prozedur die eine Liste nimmt und eine Zahl. Als Ergebnis liefert sie alle möglichen Paare Zweier Zahlen, deren Sume die angegebene Zahl ist. Sie Prüft also die Teilbarkeit der Summe von 2 Zahlen aus der Liste.

(define teilbar_x (lambda (ls x) (bag-of(let ((kandidatenliste (summanden ls))) (if (integer? (/ (apply + kandidatenliste) x)) kandidatenliste (choice '()))))))

(teilbar_x '(1 2 3 4 5 6 7 8 9) 6)

Nun 2 weitere Sprachelemente:


IN     : Liste und Zahl
OUT : Gibt genau  „richtige“ Elemente aus dieser Liste zurück.

Ein sehr schönes Beispiel ist die Ziehung der Lottozahlen. Es gibt eine Liste mit 49 Zahlen und aus dieser Liste werden dann 6 richtige gezogen.

(multichoice '(1 2 3 4 ... 49) 6)


IN     : Zahl
OUT : Liefert

Diese Elemente können wir nun nutzen um sie auf das Rucksackproblem anzuwenden:

(define rucksack4 (lambda (gls k) (let ((sls (multichoice gls (randomchoice (length gls))))) (if (<= (apply + sls) k) sls (choice '())))))

Der folgende Aufruf liefert uns alle Packzustände unter der Bedingung dass die Kapazität 42 nicht unterschreiten darf:

(bag-of (rucksack4 '(30 50 10) 42))

Jetzt haben wir alle Lösungsmöglichkeiten, aber welche ist nun die Beste? In der Prozedur $rucksack5$ wird dies realisiert:

(define rucksack5 (lambda (gls k) (let ((max 0) (resultat '())) (let ((alle-sls (bag-of (rucksack4 gls k)))) (map (lambda (sls) (let ((slssumme (apply + sls))) (if (> slssumme max) (begin (set! max slssumme) (set! resultat sls))))) alle-sls)) (cons resultat max))))

Zusätzlich wird der durch die beste Möglichkeit noch das daraus resultierende Gesamtgewicht ausgegeben.

(rucksack5 '(30 50 10) 42)

Die Effizienz von Algorithmen kann außer den Speicher- und Zeitaufwand, auch durch folgenden Aspekt definiert werden:

kognitive Effizienz = Aussage darüber wie einfach ist ein Algorithmus geistig zu erfassen ist.

Zuerst muss man sagen dass dieser Punkt keine feste Metrik hat, man kann nur sehr schlecht eine exakte Aussage (in Zahlen) machen, das entsteht hauptsächlich dadurch, dass das „geistige“ Erfassen eine subjektive Wahrnehmung ist und bei Menschen verschieden sein kann, auch bei unterschiedlich langen Programmiererfahrungen. Aber im Allgemeinen kann man sagen das ein kurzer, verständlich lesbarer Algorithmus (fast) immer besser als ein langer, komplexer Code ist. „Besser“ bedeutet z.B.: dass weniger Fehler drin sein können oder wenn ein Programmierer zum ersten Mal den Code sieht, ihn leichter verstehen kann wenn er übersichtlicher ist und nicht viele Unterschleifen hat.

Ein anschauliches Beispiel hierfür ist der Gaußscher Algorithmus zur Bestimmung des Ostersonntags.

Nicht zu vergessen ist, dass die kognitive Effizienz keine! Aussage darüber macht, wie zeitlich Effizient der Algorithmus nun ist.

Aufgaben

1. Erstellen Sie auf einem Blatt Papier einen beschränkten Tiefensuchbaum für die Werte 15,35,42 und 77 bei einer Kapazität von 55.

2. Lösen Sie Aufgabe 5.2 im Buch auf Seite 82.

3. Erstellen Sie einen reduzierten Breitensuchbaum für folgende 4 Gegenstände: '(15 35 42 77).

4. Machen Sie sich mit den Hilfsprozeduren von Scheme für das Konzept des Nichtdeterminismus aus der Vorlesung vertraut.

a)Schreiben Sie die Prozeduren summandensucheA bzw. summandenA, dass eine Liste als Eingabeparameter angegeben kann.

b)Schreiben Sie eine Prozedur summandensucheB die, nur Zahlenpaare aus gibt, deren Summe durch 3 teilbar ist.

c)Verändern Sie summandensucheB so, dass auf Teilbakeit von x (x $\in$ N) verallgemenert werden kann. Der Wert x soll ebenfalls als Eingabewert übergeben werden. s

Wer diese und die Aufgaben im Buch durchgearbeitet hat, kann als Zusatz folgende bearbeiten:

ZA*** : Verändern Sie die 4.c so,dass es zu keinen doppelten Pärchen mehr kommt. Es soll verhindert werden, dass (3,1) und (1,3) beide in der Ergebnisliste zu sehen ist.

ZA*** : Implementieren Sie das n Damenproblem oder die Breitensuche in Scheme oder in einer anderen Programmiersprache.

Hier finden Sie die Lösungen: SystemSuche_Loesung