文档介绍：: .
（人工智能）人工智能考
例：八数码问题
设：-W(n):不在位的数码个数 n：任意状态
目标状态：-W(n)=0（每个数码就位）
最不利状态-W(n)=-8
（每个数码都不在规定的位置）
基本策略：
试探性的选择一条规则，如果发现此规则不合适，则退回去另选其他规则。关键在于回溯条
件的设定。
特点：a 实用性好(相对不可回撤方式)
b 适用范围较大，在一定程度上能避免盲目性
c 可解决局部极值问题
设计方法：
a 确定合适的回溯条件
b 充分利用可用知识来排列规则，减少回溯次数
例：八数码游戏（主要讨论回溯条件）
回溯条件：
a 新产生的状态已经在搜索过程中出现；
b 应用规则的数量已经超过规定值(深度限制)
c 当前状态，无可用规则
满足上述条件之一则产生回溯，每次回溯一层。
基本策略：
它是一种展开式搜索方法，把问题空间看成一张隐含图，从中搜索出一条解路径。
特点：a 实用性好
b 能保留完整的搜索树
c 对于解空间较大的问题而言，搜索代价较大。
例：八数码问题
这是一个典型的宽度优先策略，所以搜索代价比较大。
总结：三种控制策略的特点
1）不可撤回方式：沿一条路径单向延伸搜索
2)回溯方式：可修正搜索路径
3）图搜索方式：展开式搜索，可保留完整的搜索树。
产生式系统分类
根据规则的应用方式，一般性产生式系统可以分为三种类型：1）正向系统（数据驱动）
采用正向推理方式，即由初始状态推理到目标状态，正向系统里的规则是正向使用的:规则的
前提成立，那么规则的结论成立。
2)反向系统（目标驱动系统）
采用反向推理方式：即由目标状态反向推理找到初始状态。反向系统的规则是反向使用的：
先假设规则的结论成立，在寻找使其成立的前提条件。
3）双向系统
由数据、目标双向驱动，最后终止在某个中间状态。
例：数学证明思路
定义：满足下列性质的产生式系统称为可交换产生式系统
a 给定可以用于数据库 D 的规则集 R，对于使用 R 中的任何规则后产生的任何数据库，规则
集 R 仍然可用。(规则适用性)
b 如果目标条件被 D 满足，则应用 R 中的任何规则于 D 上所产生的任何数据库仍可满足目
标条件。(数据库可用性)
c 应用 R 中一个规则序列于 D 上后，得到的数据库不随这规则序列次序变化而变化。（规则
次序无关性）
定义：任何待求解的数据库都可以分解为若干个独立处理分量的产生式系统称为可分解产生
式系统。
求解方法：将初始数据库分解为几个可独立处理的分量，用规则分别求解，生成新的数据库，
再分解，再求解，知道结束。
可分解产生式系统的一般性算法：
1DATA←初始数据库
2{Di}←DATA，Di 库：独立的分量数据库
3until{Di}的所有元素都满足结束条件之前，do：
4begin5 从{Di}中选择一个不满足结束条件的 D*
6 把 D*从{Di}中删除
7 从规则集 R 中选一条可用于 D*的规则 r，设 D 是人应用于 D*的结果是 D 的分解式。
8 在{Di}添加 di
9end
AI 领域的知识分类
a 陈述性知识：用于描述综合数据库的状态。（如事实等）
b 过程性知识：用于规则中表达问题的知识.（如客观规律等）
c 控制性知识：用于构成控制策略的知识（算法、数据结构等）
AI 系统的一个难题：知识表达问题，要能够客观的描述现实，简化求解过程，有效的提高求
解效率，降低求解代价。
产生式系统的搜索策略
状态空间：由给定问题的所有可能的状态组成的空间（相当于全集 G）
搜索空间：按某种策略在状态空间中选取的部分空间（G 的子集）
解路径（解空间）：求解问题的一条有效路径。
搜索策略的基本思路：搜索空间必须包含解路径，如果问题有解，且尽量缩小搜索空间。搜索策略的评价准则：总体费用最低
费用的划分：a 规则应用的费用：执行规则时所花的费用 b 控制费用：选择规则所花的费用。
1）A 算法 2）爬山算法 3）分支界限算法 4）动态规划算法 5）A*算法
6）h 函数与 A*的关系 7）关于单调性限制 8）A*算法示例
例四皇后问题
定义综合数据库：
设：DATA={ij︱1<=i,j<