AuK/Systematische Suche SS10
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
'''Autoren:'''
<p>Daniel Horbach ([mailto:sidahorb@stud.hs-zigr.de sidahorb@stud.hs-zigr.de])</p>
<p>Richard Hettmann ([mailto:sirihett@stud.hs-zigr.de sirihett@stud.hs-zigr.de])</p>
----
=== 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 <math> n </math> Gegenständen, von denen jeder einen Wert <math>w_i</math>
und ein Gewicht <math>g_i</math> hat. Da unser Rucksack nicht unbegrenzt belastbar ist, brauchen wir noch die Aufnahmekapazität <math>K</math>, welche keinesfalls durch das aktuelle Gesamtgewicht überschritten werden darf.
Unser Ziel ist es nun, den Rucksack so zu füllen, dass die Wertsumme der eingepackten Gegenstände
maximal ist und die Aufnamekapazität nicht überschritten wird.
Man unterscheidet diese zwei grundsätzlich veschiedenen Arten von Rucksackproblemen.
==== Bruchteilrucksackproblem ====
Ein beliebiger Teil <math> t </math> eines jeden Gegenstandes darf eingepackt werden.
<math> t </math> , <math> 0 \% <= t <= 100 \% </math>
==== 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 [http://www.michael-hielscher.de/wiki/index.php/AuK/Greedy-Algorithmen_SS10 Vorlesungen] näher erläutert.
==== Ziel ====
Unser Ziel ist das Erreichen der maximalen Wertsumme ohne die Aufnahmekapazität zu überschreiten.
<math> \sum \limits _{i =1}^n {x_i w_i} \to max </math>, wobei <math> \sum \limits _{i =1}^n {x_i g_i} \leq K </math> , mit <math> x_i \in \{0,1\} </math>
==== Teilmengen-Summen-Problem ====
Das Teilmengen-Summen-Problem ist ein Spezialfall des Rucksackproblems. Aus einer Menge natürlicher Zahlen
<math> M </math> wird eine Teilmenge gesucht, deren Elementensumme möglichst nahe an die Kapazitätsgrenze
<math> K </math> herankommt und diese auch erreichen darf. Dieser Spezialfall ergibt sich immer dann, wenn Gewicht und Wert eines jeden Gegenstandes zahlenmäßig überein stimmen.
<math> M = \{ a_i </math> <math>|</math> <math> 1 \leq i \leq n </math> und <math> a_i, n \in N \} </math>
<math> g_i = w_i , </math> mit <math> g_i,w_i \in N </math>
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 das man das globale Wertmaximum erreicht hat. 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.
[[Bild:Graphendurchlauf.jpg]]
Vom Knoten 1, welcher der Startknoten ist, gehe ich zum Knoten 2 und von dort zum Knoten 4. Diese 3 Knoten werdn 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.
<code id="4bd080647d19f" hidden>
(define tree
'(1 (2 (4 () ())
(5 () ()))
(3 (6 () ())
(7 () ()))
))
(define tree2
'(* (+ (4 () ())
(5 () ()))
(- (6 () ())
(7 () ()))
))
;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
))
)
))
</code>
<eval id="4bd0806483afa">
(walk tree)
</eval>
<eval id="4bd08064846b3">
(walk tree2)
</eval>
=== Tiefensuche ===
----
Die Depth-First-Search ist ein Verfahren zum Suchen eines Knotens in einem Graphen und gehört zu den [http://de.wikipedia.org/wiki/Suchalgorithmus#Heuristische_.28Informierte.29_Suchalgorithmen 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 <math>\mathcal{O} (|V|+|E|)</math> 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. Tiefensuche ist nicht optimal, weil möglicherweise ein Ergebnis gefunden wird, welches tiefer im Graphen liegt als ein anderes, da die Tiefensuche den Graphen erst komplett auf der linken Seite durchsucht.
==== Anwendung ====
Tiefensuche findet indirekt Anwendung bei vielen komplexen Algorithmen für Graphen, zum [http://de.wikipedia.org/wiki/Topologische_Sortierung topologischen Sortieren] und in [http://de.wikipedia.org/wiki/Expertensystem 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. Alle Knoten werden in ihrer Reihenfolge besucht, den erstmaligen Besuch nennt man den prewalk, den zweiten nennt man centralwalk und der dritte und letzte ist der postwalk. 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).
[[Bild:Rucksack1graph2.jpg]]
==== Berechnungen ====
Für n Gegenstände ergeben sich im allgemeinen <math> 2^n</math> Blätter.
<math> \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</math>, für z = 1
Hierdurch ergibt sich ein exponentieller Aufwand <math>\mathcal {O} (2^n)</math>.
Die Anzahl der Knoten lässt sich durch folgende Formel berechnen: <math> \sum_{k=0}^n 2^k = 2^n^+^1 - 1</math> Knoten
==== Die rekursive Tiefensuche mit Scheme ====
Das folgende Beispiel besitzt keine Kapazitätsgrenze, wodurch wir alle Ergebnisse die möglich sind bekommen.
<code id="4bd080647dd90" hidden>
(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)))))
</code>
Die Werte sind hier keine Vorgabe, es können andere und mehr gewählt werden.
<eval id="4bd08064852f1">
(rucksack1 '(30 50 10) '())
</eval>
=== Breitensuche ===
----
Im Gegensatz zur Tiefensuche arbeitet die Breadth-First-Search den Baum schichtenweise ab und liefert uns somit alle möglichen Ergebnisse.
Bezieht man dies auf das Rucksackproblem hat der Baum gerade soviel Äste wie sich Gegenstände in der Liste befinden.
==== Algorithmus ====
#Bestimmung des Startknotens und Speicherung dieses Knotens in einer Warteschlange
#Entnahme des ersten Knotens der Warteschlange und dessen Markierung<br/> Gefundenes Element = Abbruch nach durchsuchen der Ebene<br/> Anhängen aller bisher unmarkierten Nachfolger dieses Knotens an das Ende der Warteschlange
#Wiederholung von Schritt 2
#Abbruch bei leerer Warteschlange = Kein Ergebnis gefunden
==== Eigenschaften ====
Der Speicherplatzbedarf bei der Breitensuche ist exponentiell, da alle besuchten Knoten gespeichert werden. Der Zeitaufwand lässt sich wie bei der Tiefensuche durch <math>\mathcal{O} (|V|+|E|)</math> beschreiben, auch hier müssen im schlimmsten Fall alle Knoten untersucht werden. Da der Graph gleichmäßig in der gesamten Breite untersucht wird, findet die Breitensuche den Knoten mit der optimalen Tiefe und auch alle anderen Ergebnisknoten.
==== Anwendung ====
Die Breitensuche findet Anwendung bei der Suche nach allen [http://de.wikipedia.org/wiki/Zusammenh%C3%A4ngender_Graph Zusammenhangskomponenten] in einem Graphen, dem Suchen aller Knoten in der Zusammenhangskomponente,der Suche nach dem [http://de.wikipedia.org/wiki/K%C3%BCrzester_Pfad kürzesten Pfad] zwischen zwei Knoten und dem Kürzeste-Kreise-Problem.
==== Aufbau des Breitensuchbaumes ====
Wie auch bei der Tiefensuche hat man hier eine Rucksackliste s-ls () und eine Gegenstandsliste g-ls hier beispielsweise mit (30,50,10).
Beim Beginn der Suche ist die s-ls leer und die g-ls enthält die Gegenstände. Der erste Gegenstand wird entnommen und der Rest verbleibt in der Warteschlange. Es wird wieder ein neuer Knoten gebildet dieses wiederholt sich solange bis die g-ls leer ist.
[[Bild:BS_Baum4.jpg]]
==== Berechnung ====
Die Anzahl der Knoten lässt sich durch folgende Formel berechnen.
<math>1+n+n(n-1)+n(n-1)(n-2)+...+n(n-1)(n-2)(n-3)...(n-(n-1))<br/>= \frac{n!}{0!}+\frac{n!}{1!}+\frac{n!}{2!}+...+\frac{n!}{n!}<br/>= \sum_{k=0}^n \frac{n!}{k!}</math>
==== Beschränkung des Breitensuchbaumes ====
Einige der Knoten sind überflüssig, da die Reihenfolge des Einpackens bei der Breitensuche keine Rolle spielt, beispielsweise beschreiben die Listen (30, 50, 10) und (30, 10, 50) denselben Packzustand. Wir reduzieren den Suchbaum um die Elemente mit gleicher Bedeutung.
[[Bild:BS_red4.jpg]]
=== Beschränkte Tiefensuche ===
----
Durch das Setzen einer Kapazitätsgrenze lässt sich der Tiefensuchbaum beschränken. Nimmt man die g-ls mit folgendem Inhalt (30, 50, 10) und setzt die Kapazitätsgrenze auf (42), bekommt man nur noch die Werte die <math> \leq42</math> sind ausgegeben.
<code id="4bd080647e8f5" hidden>
(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)))
</code>
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.
<eval id="4bd0806485ea5">
(rucksack2 '(30 50 10) '() 42)
</eval>
Beschränkte Tiefensuche mit Ergebnisliste:
In diesem Codebeispiel wird nun auch die optimale Lösung angezeigt.
<code id="4bd080647f4a0" hidden>
(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 '())))))
</code>
<eval id="4bd0806486a5e">
(rucksack3 '(30 50 10) 42)
</eval>
<!--
<code id="4bd080648005b">
(define mrl
(lambda (n)
(cond
((= n 1)(list (random n[100])))
(else (append (list (random n[100])) (mrl (- n 1)))))
))
(define rucksack3b
(lambda (n)
(let ((k -1)
(g-ls -1))
(set! k (random n[100]))
; (define g-ls -1)
(set! g-ls (mrl n))
(and
(display 'rs3b)
(display g-ls)
(display 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 ;rek. Aufufe
(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 '()))))))
</code>
<eval id="4bd0806487611">
(rucksack3b 3)
</eval>
-->
==== Eigenschaften ====
Wie auch bei dem nicht reduzierten Tiefensuchbaum ist der Speicherplatz linear. Der Zeitaufwand lässt sich ebenfalls durch <math>\mathcal{O} (|V|+|E|)</math> berechnen. Optimalität und Vollständigkeit sind auch hier nicht gegeben.
=== Vergleich beider Suchstrategien ===
----
Stellt man die Suchstrategien einander gegenüber, so wird man feststellen das ja nach Suche beide ihre Vor- und Nachteile haben. Bei der Tiefensuche wird das Ergebnis schneller gefunden wenn sich dieses in der linken Baumhälfte befindet. Betrachtet man beide an einem endlichen Baum so kann man sehen das beide vollständig sind. Hinsichtlich des Speicheraufwandes ist die Breitensuche nicht gerade optimal da bei dieser der gesamte Graph gespeichert wird. Ein Vorteil der Breitensuche ist wiederrum das alle möglichen Ergebnisse gefunden werden. Bei der Tiefensuche hingegen wird nur der besuchte Pfad gespeichert und die zuerst gefundene Lösung ausgeben. Die Beste Strategie ist somit eine Kombination aus Breiten- und Tiefensuche.
=== Iterative Tiefensuche ===
----
Die iterative Suche ist eine Kombination aus den wünschenswerten Eigenschaften von Breiten- und Tiefensuche, das heisst der geringe Speicherplatzverbrauch der Tiefensuche und die Optimalität der Breitensuche.
==== Algorithmus ====
#Bestimmung des Startknotens
#Aufruf von reduzierter Tiefensuche mit aktueller Suchtiefe
#Erhöhung der Suchtiefe um 1
#Wiederholung von Schritt 2
==== Eigenschaften ====
Der Speicherplatzbedarf ist linear. Die iterative Tiefensuche ist vollständig und optimal. Zeitsaufwandsberechnung wieder mit der alt bekannten Formel <math>\mathcal{O} (|V|+|E|)</math>.
==== Das Damenproblem ====
Bei dem Damenproblem geht es darum das auf einem handelsüblichen Schachbrett mit 8*8 Feldern, acht Damen so positioniert werden das sich diese nicht gegenseitig schmeißen können. Das Problem wurde erstmals 1848 vom bayrischen Schachmeister Max Bezzel(1824-1871) betrachtet. 1850 fand Franz Nauck erstmals alle 92 Lösungen, wobei man hier sagen muss das nur 12 davon eindeutig sind.
Hier eine Tabelle für verschiedene <math>n</math>.
<math>
\begin{array}{l|l|l|l|l|l|l|l|l|l}
\text{n} & 1 & 2 & 3 & 4 & 8 & 12 & 16 & 24 & 26\\
\hline
\text{eindeutig}& 1 & 0 & 0 & 1 & 12 & 1.787 & 1.848.955 & 28.439.272.956.934 & 2.789.712.466.510.289\\
\hline
\text{insgesamt}& 1 & 0 & 0 & 2 & 92 & 14.200 & 14.772.512 & 227.514.171.973.736 & 22.317.699.616.364.044\\
\hline
\end{array}
</math>
=== Nichtdeterminismus ===
----
Bei der Baumdarstellung handelt es sich um eine strukturierte Darstellungsform des Suchprozesses. Die rekursive Baumstruktur kann unmittelbar auf die rekursive Programmstruktur abgebildet werden. Die Formulierung eines Suchziels von der Angabe des zugehörigen Suchprozesses zu entkoppeln führt zu einer deskriptiven Programmierung. Dies bedeutet das potenzielle Resultat so zu beschreiben das die Software selbst den Prozess zu dessen Bestimmung erzeugt. Den Wunsch das ein solches Programm den Pfad treffsicher erahnt falls er existiert führt uns zu einem nichtdeterministischem Algorithmus. Nichtdeterminismus beschreibt eine übernatürliche Fähigkeit das richtige vorherzusehen. Weder Mensch noch Maschine sind dazu in der Lage. Deshalb ist es sinnvoll Algorithmen zu betrachten.
Um mit einem nichtdeterministischen Algorithmus experimentieren zu können, müssen wir diesen implementieren. Wir laden hierfür die Datei ambiguos.ss in Scheme. Danach stehen uns 5 wichtige und erforderliche Sprachelemente zur Verfügung.
*choice gibt aus einer Liste das "richtige Element" zurück
*bag of gibt aus einer Liste eine Liste aller richtigen Elemente zurück
*initialize-amb-fail nullstellige Prozedur zur Initialisierung des Ambiguous Systems
*multichoice nimmt eine Liste <math>ls</math> und eine natürliche Zahl <math>n</math> und gibt die richtigen Elemente aus (LOTTO 6 aus 49)
*randomchoice nimmt eine Zahl <math>n</math> und berechnet <math>(choice '(1 2 3 . . . n))</math>
In diesem Beispiel wird gefragt ob ein Element das <math><4</math> enthalten ist.
<code id="4bd033189e77b" hidden>
(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)
</code>
<eval id="4bd033189f795">(< ( choice '(1 2 3 4 5 6 ) ) 4)</eval>
Bei bag-of bekommen wir eine Liste mit <math>#t</math> für die Elemente <math><4</math> und für die Elemente <math> \geq 4</math> ein<math>#f</math>.
<eval id="4bd033189ff67">( bag-of (< ( choice '(1 2 3 4 5 6 ) ) 4 ) )</eval>
Das folgende Beispiel gibt durch <math>#t</math> oder <math>#f</math> aus ob das Element eine Liste ist.
<eval id="4bd03318a06ba">(bag-of (list? ( choice '(a () 2 (5) #t ))))</eval>
Im nächsten Beispiel liefert uns die Prozedur als Ergebnis eine Liste mit Summanden welche wenn man sie adddiert mit dem Eingabewert übereinstimmen.
<code id="4bd0806480c15" hidden>
(define summanden
(lambda (ls)
(list (choice ls) (choice ls))))
(define summandensuche1
(lambda (ls summe)
(let ((kandidatenliste (summanden ls)))
(if (= (apply + kandidatenliste) summe)
kandidatenliste
(choice '())))))
</code>
<eval id="4bd03318a0e8c">(summandensuche1 '(0 1 2 3 4 5) 6)</eval>
Hier wieder mit bag-of.
<eval id="4bd03318a1657">(bag-of (summandensuche1 '(0 1 2 3 4 5) 6))</eval>
Die nachfolgende Prozedur prüft die Teilbarkeit der Summe von zwei Zahlen aus der Liste.
<code id="4bd08064817cb" hidden>
(define teilbar_x
(lambda (ls x)
(bag-of(let ((kandidatenliste (summanden ls)))
(if (integer? (/ (apply + kandidatenliste) x))
kandidatenliste
(choice '()))))))
</code>
<eval id="4bd08064881d0">(teilbar_x '(1 2 3 4 5 6 7 8 9) 6)</eval>
Nun noch ein Beispiel für <math>multichoice</math> und <math>randomchoice</math>. Diese Elemente nutzen wir nun um sie auf das Rucksackproblem anzuwenden.
<code id="4bd0806482384" hidden>
(define rucksack4
(lambda (gls k)
(let ((sls (multichoice gls (randomchoice (length gls)))))
(if (<= (apply + sls) k)
sls
(choice '())))))
</code>
Der folgende Aufruf liefert uns alle Packzustände die 42 nicht überschreiten.
<eval id="4bd0806488d87">(bag-of (rucksack4 '(30 50 10) 42))</eval>
Jetzt haben wir alle Packzustände aber welcher ist nun am Besten? Die nächste Prozedur gibt uns darüber Auskunft.
<code id="4bd0806482f3a" hidden>
(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))))
</code>
Hier können wir uns nun den Packzustand und sein Gewicht anzeigen lassen.
<eval id="4bd080648993d">(rucksack5 '(30 50 10) 42)</eval>
=== Übungsaufgaben ===
----
1. Erstellen Sie die Prewalk-, Centralwalk- und Postwalkliste für diesen Graphen
[[Bild:Walks.JPG]]
2. Erstellen Sie einen kompletten Tiefensuchbaum mit der Gegenstandsliste (9,2,5,7)
3. Erstellen Sie einen reduzierten Breitensuchbaum mit der Gegenstandsliste (9,2,5,7)
4. Erstellen Sie einen Suchbaum für das 4-Damenproblem wo alle Lösungen ersichtlich werden
5. Experimentieren Sie mit diesem [http://www.faust.fr.bw.schule.de/mhb/backtrack/achtdamen/autoacht.htm Programm] und finden so verschiedene Lösungen für das 8-Damenproblem.
Hier finden Sie die Lösungen: [[SystematSuche_Loesung]]
=== Quellen ===
----
;[1] Wagenknecht, Christian:Algorithmen und Komplexität.- Fachbuchverlag Leipzig, 2003.- ISBN 3-446-22314-2
;[2] http://de.wikipedia.org/wiki/Breitensuche
;[3] http://kik.informatik.fh-dortmund.de/visual/kurs_breitensuche.html
;[4] http://www.tilman.de/uni/ws03/alp/tiefen-breitensuche.php
;[5] http://de.wikipedia.org/wiki/Tiefensuche
;[6] http://de.wikipedia.org/wiki/Iterative_Tiefensuche
;[7] http://de.wikipedia.org/wiki/Damenproblem
;[8] http://de.wikipedia.org/wiki/Graphentheorie
;[9] http://www.tinohempel.de/info/info/sonstiges/expertensystem.pdf
=== Weblinks ===
----
http://de.wikipedia.org/wiki/Suchalgorithmus#Heuristische_.28Informierte.29_Suchalgorithmen
http://de.wikipedia.org/wiki/Topologische_Sortierung