人工智能：一种现代方法ch06 Constraint satisfaction problems - 2016.pdf

约束满足问题 1 何谓CSP ：求解n-qeens、CSP形式化、约束图 、约束类型 2 约束传播与局部相容性(结点相容、弧相容、 路径相容） 3 CSP形式化为一个有哪些信誉好的足球投注网站问题（回溯法） 4 提高有哪些信誉好的足球投注网站效率（变量顺序、值的顺序、提前检 查失败、利用树形结构） 1 求解n-qeens、CSP形式化、约束图、约束类型 何谓CSP ？ 3 Review: local search - hill climbing  h = number of pairs of queens that are attacking each other, either directly or indirectly 4 what is CSP?  使用要素化表示来描述状态：一组变量，每个 变量有自己的值。当每个变量都有自己的赋值 同时满足所有关于变量的约束时，问题就得到 了解决。这类问题称为约束满足问题 ，简称 CSP 5 Constraint Propagation  Place a queen in a square  Remove the attacked square from future consideration 6 Constraint Propagation  Count the number of non- attacked squares in every row and column  Place a queen in a row or column with minimum number  Remove the attacked squares 5 5 5 5 5 6 7 from future consideration 6 6 5 5 5 5 6 7 Constraint Propagation  Count the number of non- attacked squares in every row and column  Place a queen in a row or column with minimum number  Remove the attacked squares 4 3