Constraint Satisfaction Problems 吉建民 USTC jianminQustc.edu.cn 2022年3月21日 4口◆4⊙t1三1=，￥9QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Constraint Satisfaction Problems 吉建民 USTC jianmin@ustc.edu.cn 2022 年 3 月 21 日
Used Materials Disclaimer:本课件采用了S.Russell and P.Norvig's Artificial Intelligence-A modern approach slides,徐林莉老师课件和其他网 络课程课件，也采用了GitHub中开源代码，以及部分网络博客 内容 口卡4三4色进分QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Used Materials Disclaimer: 本课件采用了 S. Russell and P. Norvig’s Artificial Intelligence –A modern approach slides, 徐林莉老师课件和其他网 络课程课件，也采用了 GitHub 中开源代码，以及部分网络博客 内容
课程回顾 Best-first search Heuristic functions estimate costs of shortest paths Good heuristics can dramatically reduce search cost Greedy best-first search expands lowest h incomplete and not always optimal A*search expands lowest g+h complete and optimal also optimally efficient(up to tie-breaks,for forward search) Admissible heuristics can be derived from exact solution of relaxed problems 4口◆4⊙t1三1=，￥9QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 课程回顾 Best-first search ▶ Heuristic functions estimate costs of shortest paths ▶ Good heuristics can dramatically reduce search cost ▶ Greedy best-first search expands lowest h ▶ incomplete and not always optimal ▶ A* search expands lowest g + h ▶ complete and optimal ▶ also optimally efficient (up to tie-breaks, for forward search) ▶ Admissible heuristics can be derived from exact solution of relaxed problems
课程回顾 Local search algorithms the path to the goal is irrelevant;the goal state itself is the solution keep a single "current"state,try to improve it Hill-climbing search depending on initial state,can get stuck in local maxima Simulated annealing search escape local maxima by allowing some "bad"moves but gradually decrease their frequency Local beam search Keep track of k states rather than just one Genetic algorithms 口卡4三4色进分QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 课程回顾 Local search algorithms ▶ the path to the goal is irrelevant; the goal state itself is the solution ▶ keep a single “current” state, try to improve it ▶ Hill-climbing search ▶ depending on initial state, can get stuck in local maxima ▶ Simulated annealing search ▶ escape local maxima by allowing some “bad” moves but gradually decrease their frequency ▶ Local beam search ▶ Keep track of k states rather than just one ▶ Genetic algorithms
Table of Contents CSP examples Backtracking search for CSPs Problem structure and problem decomposition Local search for CSPs 4口◆4⊙t1三1=，￥9QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table of Contents CSP examples Backtracking search for CSPs Problem structure and problem decomposition Local search for CSPs