Tiefensuche und Breitensuche
Das im ersten Abschnitt entwickelte einfache Programm zum Rucksackproblem löst das Problem nicht in allen Fällen.
In diesem Abschnitt geht es darum, alle prinzipiell lösbaren Fälle zu lösen.
Das erste hier betrachtete Verfahren ist die Tiefensuche.
Die Tiefensuche gehört zu den vollständigen, blinden Suchverfahren. Das bedeutet,
dass der Suchraum (prinzipiell) vollständig abgesucht wird und ("uninformiert")
keine Informationen zur Auswahl von Alternativen verwendet werden.
Ein weiterer Begriff dazu ist brute force, da keinerlei andere Intelligenz als
Systematik eingesetzt wird.
Das bei uns als Ziel entwickelte Programm ist allerdings eine optimierte Tiefensuche, da laufend
auf Misserfolg und Erfolg getestet wird und dadurch nur der zulässige Teil des Suchraums bearbeitet wird.
Während bei der Tiefensuche der Suchraum so abgesucht wird, dass zuerst in die Tiefe gegangen wird,
werden bei der Breitensuche zuerst alle Alternativen einer Ebene untersucht, bevor weiter
in die Tiefe gegangen wird.
Aber: Auch die Breitensuche arbeitet brute force.
Präsentationen
- Der Schritt zur Tiefensuche:
P02 Rucksack packen mit TS-Py.pdf - P02-1 Binaerbaum_Container_80.pdf
- P02-2 Binaerbaum_Container_100.pdf
- KI-TS-Demos-mit-Mediator.zip Demos zur Tiefensuche, mit Mediator erstellt (*.exe altes Material)
- P01-d Tiefensuche-mit-backtracking.pdf
- P01-e Tiefensuche mit backtracking Programm.pdf
- P02 Breitensuche iterativ.pdf
- P02 Breitensuche-Praesentation.pdf rekursive Version
- P02-a BS Entwicklung und Kohaesion.pdf
- P02-3 Breitensuche_80_Binaerbaum.pdf
- P01-f TS_und_BS Reihenfolge der Knoten.pdf
- P02-b TS und BS im Vergleich.pdf
- P02-c Satisfizierung oder Optimierung.pdf
- P02-d fuelle-viele.pdf
Projekte
- fuelle-tiefensuche.zip Versionen mit Tiefensuche
- fuelle-tiefensuche-aufrufprotokoll.py Tiefensuchen mit Ausgaben zum Verfolgen der Aufrufe
- fuelle-zwei-ts.zip zwei Container mit Tiefensuche
- fuelle-tiefensuche-zwei-Kurs.py
die im Kurs erarbeitete Version mit zwei zu füllenden Containern - und die im Kurs erarbeitete Version für viele Container
fuelle-tiefensuche-viele-Kurs.py - fuelle-viele-tiefensuche-tiefe-liste.py viele Container mit Tiefensuche, Zeitmessung
- fuelle-TS-tiefeListe-1-2-viele.zip Tiefensuche für einen, zwei und viele Container (auch mit Zeitmessung)
- fuelle-iterativ-HGT-tiefe-liste.py Version mit Breitensuche bei tiefer Liste
- fuelle-breitensuche.zip Versionen mit Breitensuche
- fuelle-iterativ.zip iterative Versionen mit Breitensuche
- Zeitmessung.py eine Klasse Zeit zur Messung von Laufzeiten
- Optimierung.zip Projekte zur Optimierung
Texte
Material zum Python-Kurs
Das Material zum Kurs ist abschnittsweise, auf mehrere Seiten verteilt abgelegt.
- Material zu Python
- Einstieg in den Kurs
- Tiefensuche und Breitensuche
- Kürzester Weg
- Minimales Versorgungsnetz
- Probleme
- A-Stern
- Genetische Algorithmen
Terminplanung
Software
Die mit Python entwickelte Software zum Erstellen von Graphen (siehe auch dieses Bild) finden Sie im Abschnitt zur Software.
Programmierumgebung: Python