AuK/Systematische Suche SS09
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
== Rucksackprobleme ==
Das Rucksackproblem oder engl. Knapsack Problem ist ein Optimierungsproblem der Kombinatorik. Man kann es sich wie folgt vorstellen. Man hat einen Rucksack, welcher eine bestimmte Kapazität <math> K </math> hat und eine nichtleere Menge von <math> n </math> Gegenständen. Jeder Gegenstand besitzt eine Gewicht <math> g_i </math> und einen Wert <math> w_i </math>. <br>
Das Ziel ist es nun die Gegenstände so zu kombinieren, dass die Wertsumme maximal wird, aber die Kapazität nicht überschritten wird. <br>
Man unterscheidet dabei in zwei Formen:
- 0/1 Rucksackproblem :
der Gegenstand wird vollständig eingepackt oder nicht <br>
- Bruchteilrucksackproblem:
der Gegenstand wird teilweise eingepackt <br>
<br>
Wir betrachten nur die erste Form, dass der Gegenstand vollständig oder gar nicht eingepackt wird. <br>
Betrachten wir das Ganze mal mathematisch :
Es gibt verschiedene Gegenstände <math> x_i </math>, mit einem bestimmten Gewicht <math> g_i </math> und einem Wert <math> w_i </math>.
Dazu kommt dann die Kapazität des Rucksacks <math> K </math>.
Die Optimierungsaufgabe ist die maximale Wertsumme bei Nichtüberschreitung der Kapazitätsbeschränkung:
<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>
<br>
Einen Spezialfall des Rucksackproblems ist das Teilmengen-Summen-Problem oder engl. subset-sum problem. <br>
Gegeben sie dafür eine Menge natürlicher Zahlen und gesucht ist eine Teilmenge, deren Elementsummemöglichst nahe an die Vorgabezahl ( Kapazität <math> K </math> . Dieses Problem tritt ein, wenn der Gewicht und der Wert eines Gegenstandes zahlenmäßig übereinstimmen.
Betrachten wir es wieder mathematisch:
<math> M = \{ a_i \vert 1 \leq i \leq n </math> und <math> a_i, n \in N \} </math>
<math> g_i = w_i , </math> <br>
<math> g_i,w_i \in N </math>
== 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. <br>
Der Algorithmus : <br>
1. Bestimme den Knoten mit dem die Suche beginnen soll. <br>
2. Betrachte die erste Kante. <br>
3. Wenn der nächste Knoten erweiterbar ist wird wieder expandiert. <br>
4. Kann nicht expandiert werden gehe mittels backtracking zum darüber liegenden Knoten zurück und betrachte eine alternative Kante.<br>
5. Ist kein Knoten mehr expandierbar wurden alle Ecken bereits besucht.<br>
<br>
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 <math> n </math> Gegenstände hat. Allgemein ergeben sich dann für <math> n </math> Gegenstände <math> 2^n </math> Blätter.
Die Anzahl der Knoten kann man mit folgender Formel berechnen:
<math> \sum_{k=0}^n 2^k = 2^n^+^1 -1 </math>
Die Anzahl der Kanten kann man wie folgt berechnet werden:
<math> \vert E \vert = \vert V \vert -1 </math>
Für die Erzeugung eines gesamten Baumes hat man einen exponentiellen Aufwand von <math> \mathcal{O} (2^n) </math>.
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 <math> \mathcal{O}(\vert V \vert + \vert E \vert) </math>,
Anzahl der Knoten <math> \vert V \vert </math>
Anzahl der Kanten <math> \vert E \vert </math>
rekursive Tiefensuche mit Scheme:
<code>
(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
</code>
<eval>
(rucksack1 '(30 50 10) '())
</eval>
Tiefensuche mit Beschränkung:
<code>
;;; 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)))
</code>
Es kann anstatt der 42 auch eine beliebige andere Kapazität gewählt werden.
<eval>
(rucksack2 '(30 50 10) '() 42)
</eval>
Beschränkte Tiefensuche mit Ergebnisliste:
<code>
;;; 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 '())))))
</code>
<eval>
(rucksack3 '(30 50 10) 42)
</eval>
<!--
<code>
(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>
(rucksack3b 3)
</eval>
-->
== Breitensuche ==
Diese Form der Suche erstreckt sich über gesamte Breite, daher werden erst alle Knoten mit Wurzelabstand <math>k</math>, mit <math>k=1</math> und dann alle mit <math>k+1</math>, dann mit <math>k+2</math>, usw... entdeckt. Alle Knoten müssen vom Startknoten aus erreichbar sein.
Man nennt diese Suche auch Breite-zuerst Suche ( englisch: „breadth-first search“ ).
'''Algorithmus'''<br>
<ol>
<li>Setzte Startknoten und speichere ihn in einer Warteschlange ab. </li>
<li>Entnehme ersten Knoten
<ol>
<li>Zielknoten gefunden : Beende Suche mit Erfolg</li>
<li>ansonsten : hänge alle unmarkierten Nachfolger dieses Knotens an das Ende der Warteschlange</li>
</ol>
</li>
<li>Wiederhole 2. bis Ziel gefunden </li>
<li>Warteschlange leer : Beende Suche mit Misserfolg </li>
</ol>
== Nichtdeterminismus ==
<code hidden>
;;; 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)
</code>
'''Begriffe''':<br>
<b>Rekursion</b>=implizierte Definition von Funktionen
<br>
<b>deskriptive Programmierung</b>=Beschreibung des Ergebnisses
<br>
<b>Nichtdeterminismus</b>=Annahme, dass das gewünschte Resultat zielgerichtet
gefunden wird<br>
Akzeptanz von nichtdeterministischen Algorithmen :
Wenn es eine Lösung gibt, wird sie auch gefunden.
<br> <br>
'''Hilfsmittel''': Scheme.
Um das Konzept in Scheme nachzubauen wird die folgende Datei benötigt:
<math>ambiguous.ss</math>. <br> Sie beinhaltet unter anderem folgende Prozeduren:
'''choice'''
nimmt Liste und gibt "richtiges" Element für den Gesamtausdruck aus
<eval>(< ( choice '(1 2 3 4 5 6 ) ) 4)</eval>
<eval>(< ( choice '(3 4 5 6 ) ) 3)</eval>
'''bag-of'''
Gibt eine Liste mit Elementen, die zum Erfolg führen zurück
<eval>( bag-of (< ( choice '(1 2 3 4 5 6 ) ) 4 ) )</eval>
Um einen weiteren Eindruck von diesen Sprachelementen zu bekommen, folgt nun ein weiteres Beispiel.
<code>
(define summanden
(lambda (ls)
(list (choice ls) (choice ls))))
(define summandensucheA
(lambda (ls summe)
(let ((kandidatenliste (summanden ls)))
(if (= (apply + kandidatenliste) summe)
kandidatenliste
(choice '())))))
</code>
<eval>(summandensucheA '(0 1 2 3 4 5) 6)</eval>
Ausgabe aller Möglichkeiten:
<eval>(bag-of (summandensucheA '(0 1 2 3 4 5) 6))</eval>
'''multichoice'''
nimmt eine Liste und eine Zahl n und gibt n "richtige" Elemente aus der Liste zurück
Beispiel: 6 aus 49
'''randomchoice'''
nimmt Zahl n und liefert (choice '(1 2 3 . . . n ))
<code>
(define rucksack4
(lambda (gls k)
(let ((sls (multichoice gls (randomchoice (length gls)))))
(if (<= (apply + sls) k)
sls
(choice '())))))
</code>
<eval>(rucksack4 '(30 50 10) 42)</eval>
<eval>(bag-of (rucksack4 '(30 50 10) 42))</eval>
<code>
(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>
<eval>
(rucksack5 '(30 50 10) 42)
</eval>
<b>kognitive Effizienz</b>
<ul>
<li>= wie einfach ist ein Algorithmus geistig zu erfassen </li>
<li><ul>
<li>höheres Verständnis des Algorithmus </li>
<li>Übersichtlichkeit, Fehlererkennung </li>
</ul></li>
<li>keine brauchbare Metriken </li>
</ul>
== 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.
<code hidden>
;;; 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)
</code>
a)Schreiben Sie die Prozeduren summandensucheA bzw. summandenA, dass eine Liste als Eingabeparameter angegeben kann.
<code>
(define summandenA
(lambda (ls)
(list (choice ls) (choice ls))))
(define summandensucheA
(lambda (ls summe)
(let ((kandidatenliste (summandenA ls)))
(if (= (apply + kandidatenliste) summe)
kandidatenliste
(choice '())))))
</code>
<eval>(summandensucheA '(0 1 2 3 4 5) 6)</eval>
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 <math>\in</math> N) verallgemenert werden kann.
Der Wert x soll ebenfalls als Eingabewert übergeben werden.
<code>(define teilbar_X
(lambda (ls x)
(bag-of(let ((kandidatenliste (summandenA ls)))
(if (integer? (/ (apply + kandidatenliste) x))
kandidatenliste
(choice '()))))))</code>
<eval>(teilbar_x '(1 2 3 4 5 6 7 8 9) 6)</eval>
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]]
== Folien ==
<document>Wiki_SystematischeSuche.pdf</document>
== Quellen ==
[1] Wagenknecht, Christian: Algorithmen und Komplexität
[2] Thomas H. Cormen: Algorithmen - Eine Einführung
[3] http://de.wikipedia.org/wiki/Breitensuche
[4] http://kik.informatik.fh-dortmund.de/visual/startseite.html
[5] Uwe Lämmel, Jürgen Cleve : Künstliche Intelligenz