第03章约束推理.pptVIP

* 史忠植 高级人工智能 * 3.2 Backtracking Algorithm Based on depth-first recursive search Approach Tests whether solution has been found If found solution, return it Else for each choice that can be made Make that choice Recur If recursion returns a solution, return it If no choices remain, return failure Some times called “search tree” 第29页，共68页，编辑于2022年，星期五 * 史忠植 高级人工智能 * 3.2 Solution to 8-Queens Puzzle 八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。 第30页，共68页，编辑于2022年，星期五 * 史忠植 高级人工智能 * 4-Queens Puzzle 第31页，共68页，编辑于2022年，星期五 * 史忠植 高级人工智能 * 4-Queens Tree 第32页，共68页，编辑于2022年，星期五 * 史忠植 高级人工智能 * 3.2 回 溯 法 Backtracking-Top(P) 1 f := the null assignment 2 return Backtracking(f,P) 第33页，共68页，编辑于2022年，星期五 * 史忠植 高级人工智能 * 3.2 回溯法 Backtracking(f,P) 1 if f is a total assignment of the variables in P 2 answer := f 3 else 4 v := some variable in P that is not yet assigned a value by f 5 answer := Unsat 6 for each value while answer = Umsat 7 f(v) := x 8 if f satisfies the constraints in P 9 answer := Backtracking(f,P) 10 return answer 第34页，共68页，编辑于2022年，星期五 * 史忠植 高级人工智能 * 3.2 回溯法 尽管回溯法好于生成测试法，但对于非平凡问题仍然是低效的。其原因在于搜索空间中不同路径的搜索重复相同的失败子路径。一些研究者认为，造成这种反复的原因是所谓的局部不一致性。最简单的情形是所谓的结点不一致性。对一个变量vi的一个一元约束。存在域中一个值vi不满足该约束。这样，每当vi取到 a 时就会出现不一致性。 另一种重复的情形是所谓的弧不一致性。 第35页，共68页，编辑于2022年，星期五 * 史忠植 高级人工智能 * 3.3 约束传播 如果对vi 的当前域中的所有值x，存在vj的当前域中的某值y使得 vi=x和vj=y是vi与vj之间的约束所允许的，则弧(vi, vj)是弧一致的。 弧一致性的概念是有向的。即(vi, vj) 是弧一致的并不自动地意味着(vj, vi)是一致的。 第36页，共68页，编辑于2022年，星期五 * 史忠植 高级人工智能 * 3.3 约束传播CONSTRAINT PROPAGATION (red, green) (red,blue) (red, green, blue) 弧一致性（Arc consistency） 第37页，共68页，编辑于2022年，星期五 * 史忠植 高级人工智能 * 3.3 CONSTRAINT PROPAGATION All of the Mackworth algorithms make use of a R