AuK/Systematische Suche SS10
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
'''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.
==== Grundsätzliches ====
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>. 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 überschrittn wird.
Man unterscheidet diese zwei grundsätzlich veschiedenen Arten von Rucksackproblemen:
==== Bruchteilrucksackproblem ====
Ein beliebiger Teil <math> t </math> eines jeden Gegenstandes darf eingepackt werden, dieses Problem wird aber in dieser Vorlesung nicht näher erläutert.
<math> t </math> , <math> 0 \% <= t <= 100 \% </math>
==== 0/1 Rucksackproblem ====
----
Jeder einzelne Gegenstand wird entweder vollständig (1) oder garnicht (0) in den Rucksack aufgenommen.
Wir befassen uns hier nur mit dem 0/1 Rucksackproblem.
==== 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 Transporunternehmen, 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.
=== Tiefensuche ===
----
Die Depth-First-Search ist ein Verfahren zum Suchen eines Knotens in einem Gaphen 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. Der Zeitaufwand lässt sich durch <math>\mathcal{O} (|V|+|E|)</math> beschreiben.
Im Bezug auf die Vollständigkeit und die Optimalität trifft beides bei der Tiefensuche nicht zu. Da diese weder optimal
noch vollständig ist.
==== Anwendung ====
----
Diese findet indirekt Anwendung bei vielen komplexen Algorithmen für Graphen. Desweiteren zum topologischen Sortieren und in Expertensystemen.
==== Bezug auf 0/1 Rucksackproblem ====
----
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).
==== 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 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.
==== 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
Man hat einen exponentiellen Aufwand zur Erzeugung von <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
=== Breitensuche ===
----
Im Gegensatz zur Tiefensuche wird bei der Breadth-First-Search der Baum schichtenweise abgearbeitet.
Auf das Rucksackproblem bezogen 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/> Abruch der Suche bei gefundenem Element<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. Der Zeitaufwand lässt sich wie bei der Tiefensuche durch <math>\mathcal{O} (|V|+|E|)</math> beschreiben.
Im Bezug auf die Vollständigkeit und die Optimalität trifft dieses im Gegensatz zur Tiefensuche zu. Vollständigkeit und Optimalität werden erfüllt.
==== Anwendung ====
----
Die Breitensuche findet Anwendung bei der Suche nach allen Zusammenhangskomponenten in einem Graphen. Desweiteren des findens aller Knoten in der Zusammenhangskomponente. Sowie der kürzeste Pfad zwischen zwei Knoten und dem kürzeste Kreise Problem.
==== Bezug auf 0/1 Rucksackproblem ====
----
Wie auch bei der Tiefensuche hat man hier eine Rucksackliste s-ls () und eine Gegenstandsliste g-ls hier beispielsweise mit (30,50,10).
==== Aufbau des Breitensuchbaumes ====
----
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. Einen wirklich brauchbaren Baum erhält man erst nach der Reduzierung da vorher Packzustände doppelt vorkommen.
==== 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 ====
----
Wie bereits erwähnt sind einige Knoten überflüssig, da die Reihenfolge des Einpackens bei der Breitensuche keine Rolle spielt. beispielsweise beschreiben die beiden folgenden Listen (30, 50, 10) und (30, 10, 50) denselben Packzustand. es wird der Suchbaum um die Elemente mit gleicher Bedeutung reduziert.
=== 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). So bekommt man in dann nur noch die Werte die <math> \leq42</math> sind ausgegeben.
==== 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. Ist aber auch nicht optimal und wieder unvollständig da nicht alle möglichen Ergebnisse gesucht werden.
=== Iterative Tiefensuche ===
----
Die iterative Suche ist eine Kombination aus den wünschenswerten Eigenschaften von Breiten- und Tiefensuche. In dieser vereint sind der geringe Speicherplatzverbrauch der Tiefensuche und die Optimalität der Breitensuche.
==== Algorithmus ====
----
==== Eigenschaften ====
----
=== Nichtdeterminismus ===
----
<code>
;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
))
)
))
<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>
Es können auch andere Werte als 30, 50 und 10 oder mehr gewählt werden.
<eval>
(rucksack1 '(30 50 10) '())
</eval>
<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. Auch hier können für die 30, 50 und 10 andere Werte gewählt werden.
<eval>
(rucksack2 '(30 50 10) '() 42)
</eval>
Beschränkte Tiefensuche mit Ergebnisliste:
In diesem Codebeispiel wird nun auch die optimale Lösung angezeigt.
<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>
-->
<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>