Systematische Suche SS09

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

Man unterscheidet dabei in zwei Formen:

- 0/1 Rucksackproblem :

  der Gegenstand wird vollständig eingepackt oder nicht 

- Bruchteilrucksackproblem:

  der Gegenstand wird teilweise eingepackt 

Wir betrachten nur die erste Form, dass der Gegenstand vollständig oder gar nicht eingepackt wird.

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 ,

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.

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 n Gegenstände hat. Allgemein ergeben sich dann für n Gegenstände 2^n Blätter. Anhand des Baumes kann man das auch mit folgender Formel nachrechnen:

\sum \limits _{k=0}^n {n \choose k}z^k = {n \choose 0}z^0+...+{n \choose n}z^n = (1+z)^n , für z = 1

Die Anzahl der Knoten kann man mit folgender Formel berechnen:

Die Anzahl der Kanten kann man wie folgt berechnet werden:

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:

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

Tiefensuche mit Beschränkung:

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:

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

Breitensuche

Diese Form der Suche erstreckt sich über gesamte Breite, daher werden erst alle Knoten mit Wurzelabstand k, mit k=1 und dann alle mit k+1, dann mit k+2, usw... entdeckt. Alle Knoten müssen vom Startknoten aus erreichbar sein. Man nennt diese Suche auch Breite-zuerst Suche ( englisch: „breadth-first search“ ).

Algorithmus

1. Setzte Startknoten und speichere ihn in einer Warteschlange ab.
2. Entnehme ersten Knoten

           
   
           
   Zielknoten gefunden : Beende Suche mit Erfolg
           
   ansonsten : hänge alle unmarkierten Nachfolger dieses Knotens an das Ende der Warteschlange
           

3. Wiederhole 2. bis Ziel gefunden
4. Warteschlange leer : Beende Suche mit Misserfolg

Nichtdeterminismus

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:

kognitive Effizienz

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.a)Erstellen Sie einen Breitensuchbaum für folgende 4 Gegenstände : '(15 35 42 77)

b)Erzeugen Sie daraus den dazugehörigen reduzierten Breitensuchbaum. Vergleichen sie Ihre Lösung mit der aus Aufgabe 1. ["stimmen mit den Blättern der Tiefensuche überein"]

4. Machen Sie sich mit den Hilfspozeduren 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.
> (summandensucheA '(0 1 2 3 4 5) 6)
(1 5)
b)Schreiben Sie eine Prozedur summandensucheB die, nur Zahlenpaare aus gibt, deren Summe durch 3 teilbar ist.
> (bag-of(summandensucheB '(1 2 3 4 5)))
((1 2) (1 5) (2 1) (2 4) (3 3) (4 2) (4 5) (5 1) (5 4))
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.

> (teilbar_x '(1 2 3 4 5 6 7 8 9) 6)
((1 5) (2 4) (3 3) (3 9) (4 2) (4 8) (5 1) (5 7) (6 6) (7 5) (8 4) (9 3) (9 9))

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

Folien

hier kommt noch unsere pdf zur Vorlesung