Systematische Suche SS09

Aus ProgrammingWiki

Archivierte Version vom 2009-06-15T07:59:03+00:00. Aktuelle Version

Rucksackproblem

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 K hat und eine nichtleere Menge von n Gegenständen. Jeder Gegenstand besitzt eine Gewicht g_i und einen Wert w_i .

Das Ziel ist es nun die Gegenstände so zu kombinieren, dass die Wertsumme maximal wird, aber die Kapazität nicht überschritten wird.

Bruchteilrucksackproblem

der Gegenstand wird teilweise eingepackt

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

0/1 Rucksackproblem

der Gegenstand wird vollständig eingepackt oder nicht

Betrachten wir das Ganze mal mathematisch :

Es gibt verschiedene Gegenstände x_i , mit einem bestimmten Gewicht g_i und einem Wert w_i . Dazu kommt dann die Kapazität des Rucksacks K .

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

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

Grundlegende Graphentheorie

Aufbau eines Graphen

Graphendurchlauf

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ärend einer Suche generiert, als eine Art Protokol spricht man von einem dynamischen Baum.

Algorithmus am obrigen Beispielgraphen

Betrachten wir nun den Algorithmus nochmal an einem Beispiel:

Wir bestimmen den Startknoten, in diesem Fall ist das S. Dann betrachen wir die erste Kante, Startknoten zu Knoten 1. Da dieser Knoten erweiterbar ist wird also expandiert. Das selbe geschieht nun auch mit Konten 1 zu Knoten 2. Da der Knoten 2 nun nicht mehr erweiterbar ist gehen wir mittels backtracking bis zum Knoten 1 zurück und betrachten nun die nächte mögliche Kante Knoten 1 zu Knoten 3. Das ganze setzt sich soweit fort bis wir bei Knoten 11 angekommen sind und wir nicht mehr weiter expandieren können.

Berechnungen

Gehen wir mal davon aus, dass man n Gegenstände hat. Allgemein ergeben sich dann für n Gegenstände 2^n Blätter.

Die Anzahl der Knoten kann man mit folgender Formel berechnen:

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

Die Anzahl der Kanten kann man wie folgt berechnet werden:

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

Für die Erzeugung eines gesamten Baumes hat man einen exponentiellen Aufwand von \mathcal{O} (2^n) .

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 \mathcal{O}(\vert V \vert + \vert E \vert) ,

Anzahl der Knoten \vert V \vert

Anzahl der Kanten \vert E \vert

rekursive Tiefensuche mit Scheme

(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

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

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

Bild:BS_Baum.jpg

Ein Knoten ist wiefolgt aufgebau: 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:

Bild:BS_Baum_Abarbeitung2

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:

Anzahl der Kanten = 16 – 1 = 15 Kanten.

Anzahl der Blätter 2^n = 2^3 = 8 Blätter

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

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

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

Systematische Suche SS09

Inhaltsverzeichnis

Rucksackproblem

Bruchteilrucksackproblem

0/1 Rucksackproblem

Grundlegende Graphentheorie

Aufbau eines Graphen

Graphendurchlauf

Tiefensuche

Der Algorithmus

Suchbaum

Algorithmus am obrigen Beispielgraphen

Berechnungen

rekursive Tiefensuche mit Scheme

Tiefensuche mit Beschränkung

Breitensuche

Suchbaum

Berechnung

Nichtdeterministische Suche

Aufgaben

Folien

Quellen

Suche