Systematische Suche SS09

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

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:

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

In diesem Abschnitt lassen wir die Kapaität K noch außer betracht.

<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

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:

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

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. 

1. Entnehme ersten Knoten
   1. Zielknoten gefunden : Beende Suche mit Erfolg
   2. ansonsten : hänge alle unmarkierten Nachfolger dieses Knotens an das Ende der Warteschlange
2. Wiederhole 2. bis Ziel gefunden
3. Warteschlange leer : Beende Suche mit Misserfolg

Analyse

TODO

Besonderheiten

Eigenschaften

Die Breitensuche liefert durch ihre spezifische Arbeitsweise immer den kürzten Pfad zwischen 2 Knoten. Dazu hier 2 Definitionen:

kürzester Pfad= Pfad der Länge von Startknoten s und Knoten v

kürzester Abstand = minimale Anzahl von Kanten über alle Pfade von s nach v

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.

Hier wird ein großer Unterschied zur Tiefensuche deutlich. Die Breitensuche ist für eine endliche Anzahl von Kanten vollständig, das heisst, wenn es eine Lösung existiert wird sie auch gefunden, auch bei unendlichen Graphen.

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.

(g1,g2) | (g3) = (g2,g1) | (g3)		

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:

(g1,g2,g3) | (g3) = (g1,g3,g2) | () = (g2,g1,g3) | () = (g2,g3,g1) | () = (g3,g1,g2) | () = (g1,g3,g2) | () 

durch nur 1 Blatt repräsentiert weden. TODO

Nichtdeterministische Suche

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>(&lt; ( choice '(1 2 3 4 5 6 ) ) 4)</eval> <eval>(&lt; ( choice '(3 4 5 6 ) ) 3)</eval>

bag-of Gibt eine Liste mit Elementen, die zum Erfolg führen zurück <eval>( bag-of (&lt; ( choice '(1 2 3 4 5 6 ) ) 4 ) )</eval>

Um einen weiteren Eindruck von diesen Sprachelementen zu bekommen, folgt nun ein weiteres Beispiel.

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

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

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

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

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