Tiefensuche
Von "fuelle" zur Tiefensuche
Das im ersten Abschnitt entwickelte Programm zum Rucksackproblem löst leider das Problem nicht in allen Fällen. Nun geht es darum alle prinzipiell lösbaren Fälle zu lösen.
Das hier betrachtete Verfahren ist die Tiefensuche.
Die Tiefensuche gehört zu den vollständigen, blinden Verfahren. Das bedeutet, dass der Suchraum (prinzipiell)
vollständig abgesucht wird und keine Informationen zur Auswahl von Alternativen verwendet werden.
Ein weiterer Begriff dazu ist brute force, da keinerlei Intelligenz, nur Systematik eingesetzt wird.
Das bei uns entwickelte Programm fuelle-ts.scm ist allerdings eine optimierte Tiefensuche, da laufend auf Misserfolg
und Erfolg getestet wird und dadurch nur der zulässige Teil des Suchraums bearbeitet wird.
Präsentationen
- P01-c Rucksack packen mit TS.pdf nun geht alles.
- P01-d Tiefensuche-mit-backtracking.pdf
- P01-e Tiefensuche mit backtracking Programm.pdf
- P01-f TS_und_BS Reihenfolge der Knoten.pdf
- P01-g fuelle-viele.pdf
Projekte
- fuelle-ts.scm
- fuelle-ts-mit-Aufrufprotokoll.scm
zum Beobachten von Aufrufen und Rueckgaben
dazu wird die Datei breakpoint.scm benötigt. - fuelle-ts-andere-Aufrufreihenfolge.scm erst ohne das Stück, dann erst mit versuchen
- fuelle-ts-Optimierung.scm der Container soll nicht zwingend
vollständig gefüllt werden, sondern optimal
(Optimierungsproblem statt Satisfizierungsproblem) - fuelle-zwei-ts.scm mit zwei verschiedenen Containern
- fuelle-zwei-ts-Alternative.scm eine Alternative
- fuelle-viele-ts.scm Erweiterung auf mehr Container
- fuelle-viele-ts-laufzeit.scm nun mit Laufzeitmessung,
dazu wird die Datei laufzeit-messung.scm benötigt.
Texte
- KI-01 Suchprobleme.pdf
- KI-01-d Stack bei Tiefensuche.pdf
- KI-01-d-1 Stack bei fuelle mit Tiefensuche.pdf einfach grafisch veranschaulicht
- Laufzeit-viele-ts.pdf Tabelle und Grafik mit Laufzeiten (ms) in Abhängigkeit von der Zahl der Stücke und der Container
Arbeitsblätter
Material zum Kurs
Das Material zum Kurs ist abschnittsweise, auf mehrere Seiten verteilt abgelegt.
- Startseite "Intelligente Suchverfahren"
- Material zu Scheme
- Einstieg in den Kurs
- Tiefensuche
- Breitensuche
- Kürzester Weg
- Minimales Versorgungsnetz
- Probleme
- A-Stern
- Genetische Algorithmen
Software
Die mit Python entwickelte Software zum Erstellen von Graphen finden Sie im Abschnitt zur Software.
Programmierumgebung: Racket