Systematische Suche SS09

Aus ProgrammingWiki

Archivierte Version vom 2009-06-23T06:26:20+00:00. Aktuelle Version

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 Begin 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 nach der Begriff der Kapazität K , welcher eine Schranke darstellt, die eingehalten werden muss.

Es geht nun darum einen Rucksack so zu fühlen, 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 sie dafür eine Menge natürlicher Zahlen und gesucht ist eine Teilmenge, deren Elementsummemöglichst nahe an die Vorgabezahl ( Kapazität K . Dieses Problem tritt ein, wenn der 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.

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 weis wann Wertmaximum erreicht ist.

Eine bessere Lösung 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 entscheident 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, um 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 Vielfat dies geschieht, entstehen unterschiedliche Varienten von Graphen.

Ein ist der Baum. Ein Baum besitzt eine Wurzel und von dieser Wurzel (auch Startknoten genannt) gehen mehrere oder nur eine Kante zu neuen Knoten ab. Von diesen wiederum können neue Kanten abgehen.

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 wiefolgt 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:

()|{g}_{1}, {g}_{2}, {g}_{3}

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

Graphendurchlauf

Prewalk = 1.Berührung eines Knotens

Centralwalk = 2. Berührung eines Knotens

Postwalk = 3. Berührung eines Knotens

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.

;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 leer Liste repräsentiert werden!
;naturlich 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!

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

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

Die Prewalk-Liste folgendermaßen aus:

(+ * 3 4 - 5 6)

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

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

Diesen Ausdruck kann man sich in Scheme evaluieren lassen:

Die Centralwalk-Liste folgendermaßen aus:

(3 * 4 + 5 - 6)

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

=(3 * 4 + 5 - 6)

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 eine 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, 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, dass kommt daher, da die Reihenfolge wie ich die Gegenstände in den Rucksack packe egal ist, sondern nur die Kombination der Gegenstände ist wichtig. Ein binärer Tiefensuchbaum ist uniform, das bedeutet er hat einen konstanten Verzweigungsgrad und eine einheitliche Tiefe. Der Zielknoten den wir suchen liegt mit gleicher Wahrscheinlichkeit in der Maximaltiefe d ( ganz unten im Suchbaum).

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

Die Anzahl der Blätter des Graphen beträgt 2^n und die Anzahl der Kanten ist die Anzahl der Knoten -1

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

Die Tiefensuche hat folgende Eigenschaften. Sie hat eine Komplexität von **formel komplexität 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 gegenüber der Breitensuche, schneller gefunden werden, als bei der speicherauwendigen 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

<eval> (rucksack1 '(30 50 10) '()) </eval>

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.

<eval> (rucksack2 '(30 50 10) '() 42) </eval>

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 '())))))

<eval> (rucksack3 '(30 50 10) 42) </eval>

Breitensuche

Die Breitensuche ist einer der einfachsten Algorithmen für das Durchsuchen eines Graphen. Die Idee finden 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, dass 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. Dies wird am besten durch folgene graphische Darstellung deutlich: <pic></pic>

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

Besonderheiten

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.

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.


({g}_{1},{g}_{2}) | ({g}_{3}) = ({g}_{2},{g}_{1}) | ({g}_{3})

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:


({g}_{1},{g}_{2},{g}_{3}) | ({g}_{3}) = ({g}_{1},{g}_{3},{g}_{2}) | () = ({g}_{2},{g}_{1},{g}_{3}) | () = ({g}_{2},{g}_{3},{g}_{1}) | () = ({g}_{3},{g}_{1},{g}_{2}) | () = ({g}_{1},{g}_{3},{g}_{2}) | ()

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:

({g}_{1})|({g}_{2},{g}_{3})

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).

 ({g}_{2})|({g}_{3})

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:

 ({g}_{3})|()

Bisher ist folgender Baum entstanden:

PIC

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

 ({g}_{1},{g}_{2})|({g}_{3})

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.

 ({g}_{1},{g}_{3})|()

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

PIC

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)

Begriffe:
Rekursion=implizierte Definition von Funktionen
deskriptive Programmierung=Beschreibung des Ergebnisses
Nichtdeterminismus=Annahme, dass das gewünschte Resultat zielgerichtet gefunden wird
Akzeptanz von nichtdeterministischen Algorithmen : Wenn es eine Lösung gibt, wird sie auch gefunden.

Hilfsmittel: Scheme. Um das Konzept in Scheme nachzubauen wird die folgende Datei benötigt: ambiguous.ss.
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.

(define summanden
  (lambda (ls)
    (list (choice ls) (choice ls))))

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

<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 ))

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

<eval>(rucksack4 '(30 50 10) 42)</eval> <eval>(bag-of (rucksack4 '(30 50 10) 42))</eval>

(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))))

<eval> (rucksack5 '(30 50 10) 42) </eval>

kognitive Effizienz

= wie einfach ist ein Algorithmus geistig zu erfassen

höheres Verständnis des Algorithmus
Übersichtlichkeit, Fehlererkennung

keine brauchbare Metriken

TODO'

Bilder einfügen*
BS: Analyse*
treetraversal:Code schreiben
Kapitel 5 ausformulieren-w*
Graphenaufbau
Quellen expandieren*
RS prüfen

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

Folien

Hier die überarbeitete PDF-Datei zu unserer Präsentation:

Wiki_SystematischeSuche.pdf

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

[6] http://www.iicm.tugraz.at/greif/node6.html

Systematische Suche SS09

Inhaltsverzeichnis

Rucksackproblem

Bruchteilrucksackproblem

0/1 Rucksackproblem

Teilmengen-Summen-Problem

Grundlegende Graphentheorie

Aufbau eines Graphen

Graphendurchlauf

Tiefensuche

Der Algorithmus

Suchbaum

rekursive Tiefensuche mit Scheme

Tiefensuche mit Beschränkung

Breitensuche

Suchbaum

Berechnung

Algorithmus

Analyse

Besonderheiten

Vergleich

Nichtdeterministische Suche

Aufgaben

Folien

Quellen

Suche