Table of ContentsLecture 8 Randomized Search Algorithms Part I: Backtrack Search Coming Up… Variable and Value Selection Inference in CSP’s: So Far… N-queens Demo Question of the Day Problem Domain: ?Chess Fiber Optic Networks PPT Slide PPT Slide PPT Slide Timetabling Paramedic Crew Assignment (Austin, Texas) PPT Slide PPT Slide Quasigroup Completion Problem A Framework for Studying Search PPT Slide QCP as a CSP PPT Slide PPT Slide PPT Slide Complexity of Quasigroup Completion PPT Slide These results for the QCP - a structured domain, nicely complement previous results on phase transition and computational complexity for random instances such as SAT, Graph Coloring, etc. Constrainedness Effect of Constrainedness PPT Slide Distributions of Randomized Backtrack Search PPT Slide PPT Slide Heavy-Tailed Distributions Decay of Distributions PPT Slide How to Check for “Heavy Tails”? PPT Slide Consequence for algorithm design: PPT Slide Restarts Tuning Cutoff PPT Slide Eliminating Heavy Tails Deterministic Search Restarts Summary |
Author: Henry Kautz
Email: kautz@cs.washington.edu Home Page: www.cs.washington.edu/homes/kautz |