Systematische Suche SS09

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2009-06-22T09:50:45+00:00. Aktuelle Version

Inhaltsverzeichnis

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

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. Also werden die Knoten wie folgt berührt:

Graphendurchlauf.jpg

prewalk = 1,2,4,5,3,6,7

centralwalk = 4,2,5,1,6,3,7

postwalk = 4,5,2,6,7,3,1

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 jeweil letzten wieder heraus und eintscheidet sich in jedem Knoten anders als vorher (Backtracking).

          • bild erstellen und einfügen*****

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)

Exponentielleraufwand2.jpg

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.


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

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.

<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 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: BS_graph_veranschaulichung.gif


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


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 :

  1. Setzte Startknoten und speichere ihn in einer Warteschlange ab.
  2. Entnehme ersten Knoten
    1. Zielknoten gefunden : Beende Suche mit Erfolg
    2. 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

Analyse

TODO


Besonderheiten

Eigenschaften

Die Breitensuche liefert durch ihre spezifische Arbeitsweise immer den kürzten Pfad zwischen 2 Knoten. Dazu hier 2 Definitionen: TOTO:Wa is s u v

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.


({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:

red.BSTeilB PIC / TODO

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: red. BSBaum

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} & \text{Nur wenn Suchbaum endlich} & \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

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
  • = 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

    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