智能定义（知识阈值理论） 智能就是在巨大的搜索空间中迅速找到一个满意解的能力
智能的综合性定义:智能是知识和智力的总和。其中知识是智能行为的基础。
智能的特征:1）具有记忆与思维能力
存贮有感官得到的外界信息并加以处理（如分析，计算，联想、决策等）
2）具有感知能力：通过感官获取外部信息的能力。
3）具有自适应能力
通过与外部世界交互学习，积累经验，增长知识，以适应环境变化。
4）具有表达能力
通过语言、手势、表情等方式完成信息的输出。
深蓝：能够模拟人的思维，进行博弈的计算机。1997 年 5 月 12 日，一个名为“深蓝”（deep Blue ）
的 IBM 计算机系统战胜当时的国际象棋冠军 盖利.卡斯帕罗夫
图灵测试：两个房间，一个是人，一个是机器，测试者通过一系列的提问，如果提问题的人
无法分辨是人还是机器在回答问题，则认为该机器具有智能
人工智能（Artifical Intelligence，简称 AI）又称机智能 machine intelligence，一般认为起源
于美国 1956 年的一次夏季讨论（达特茅斯会议）在这次会议上，第一次提出了“Artifical
Intelligence”这个词。
AI 的本质问题：研究如何制造出人造的智能机器或系统，来模拟人类的智能活动的能力，
以延伸人们智能的科学。
产生式系统由三个部分组成
1）综合数据库（Globe Database）
也称为：事实库，上下文等。
作用:存放问题求解的过程中产生的状态描述信息。
2）规则库（Rule Base）(问题本身知识、求解知识)
也称为规则基、规则集等。
作用：存放规则知识。
产生式规则的一般表达形式：
IF（前提）…THEN(结论)…
即 ： 如果… 那么….
例：1）数学定理
2）IF A 是一种动物 AND A 是哺乳动物 AND A 吃肉
THEN A 是高级动物
关于不精确推理
当规则的前提成立时，结论并非完全成立。这种推理称为不精确推理。通常采用阈值方
法来解决此类问题。
（3）控制策略（Control Strategy）
a 选择规则库中的规则与综合数据库的已知事实进行匹配，匹配成功的规则为可用规
则，否则为不可用规则。
b 规则冲突的解决（可用规则书>1）。
c 将选中的规则的结论放入综合数据库。
产生式系统的特点： 1 模式化：所有规则具有相同的形式
2 结构化：规则见的关联比较简单，容易维护。
3 自燃性：规则表达了因果关系，比较符合人们的思维方式，容易理解。
4 单一性：智能处理因果关系问题。
5 效率低，规则匹配过程很大。
产生式系统的适用范围：1）知识杂乱、事实众多、无统一理论的领域
2）该领域的知识能够抽象出来
3）该领域的知识可分解为一组独立的动作，以便用规则加以表示。
概括说的说：问题空间从一个状态到另一个状态的转移序列独立的领域可采用产生式系统模
拟。
产生式系统一般性算法：1 DATA ←初始数据库
2 until DATA 满足结束条件条件之前 do：
3 Begin
在规则集中选择某一可用于 DATA 的规则 R
DATA ←R 应用到 DATA 后得到的结果
END
例 1 字符转换
问题：设字符转换规则
A∣B→C A∣C→D
B∣C→G B∣E→F
D→E
已知：A,B
求：F
一、综合数据库
{x} ：其中 x 为字符
二、规则集
IF A∣B THEN C
IF A∣C THEN D
IF B∣C THEN G
IF B∣E THEN F
IF D THEN E
三、控制策略
顺序排队
四、初始条件 {A,B}
五、结束条件：
例 2 八数码游戏
问题：一个 3×3 棋盘有八张牌 1,2，…8 及一个空格，空格周围的牌可以向空格移动。
求解：给定一个初始状态 s 一个目标状态 G，求 S 到 G 的走步序列。
产生式系统的基本控制策略
概括的讲：产生式系统控制策略---搜索
1）不可撤回方式
2）试探性方式
a 回溯方式（Backtracking）
b 图搜索方式（Graph search）
1.不可撤回方式
基本策略：选择规则时只依靠局部知识（信息），而不考虑是否全局最佳选择，只能满足
局部优化条件，用过的规则不再撤回。
特点：
a 方法简单，容易实现
b 具有一定的局限性，适用范围小（只可用于单极值情况）
c 可能会造成规则的多次重复使用。
比如：‘爬山算法’，不可用于解决多极值问题。
关于 局部知识的利用 ：设计局部评价函数 W(n),根据 W(n)最大为原则来选择规则。
例：八数码问题
设：- W(n):不在位的数码个数 n：任意状态
目标状态：- W(n)=0 （每个数码就位）
最不利状态- W(n)= -8
（每个数码都不在规定的位置）
2.回溯方式
基本策略：
试探性的选择一条规则，如果发现此规则不合适，则退回去另选其他规则。关键在于回溯条
件的设定。
特点： a 实用性好(相对不可回撤方式)
b 适用范围较大，在一定程度上能避免盲目性
c 可解决局部极值问题
设计方法：
a 确定合适的回溯条件
b 充分利用可用知识来排列规则，减少回溯次数
例：八数码游戏（主要讨论回溯条件）
回溯条件：
a 新产生的状态已经在搜索过程中出现；
b 应用规则的数量已经超过规定值(深度限制)
c 当前状态，无可用规则
满足上述条件之一 则产生回溯，每次回溯一层。
3.图搜索方式
基本策略：
它是一种展开式搜索方法，把问题空间看成一张隐含图，从中搜索出一条解路径。
特点： a 实用性好
b 能保留完整的搜索树
c 对于解空间较大的问题而言，搜索代价较大。
例：八数码问题
这是一个典型的宽度优先策略，所以搜索代价比较大。
总结：三种控制策略的特点
1） 不可撤回方式：沿一条路径单向延伸搜索
2)回溯方式：可修正搜索路径
3）图搜索方式：展开式搜索，可保留完整的搜索树。
产生式系统分类
1.一般性产生式系统
根据规则的应用方式，一般性产生式系统可以分为三种类型：
1）正向系统（数据驱动）
采用正向推理方式，即由初始状态推理到目标状态，正向系统里的规则是正向使用的:
规则的前提成立，那么规则的结论成立。
2)反向系统（目标驱动系统）
采用反向推理方式：即由目标状态反向推理找到初始状态。反向系统的规则是反向使用的：
先假设规则的结论成立，在寻找使其成立的前提条件。
3）双向系统
由数据、目标双向驱动，最后终止在某个中间状态。
例：数学证明思路
2.可交换产生式系统
定义：满足下列性质的产生式系统称为可交换产生式系统
a 给定可以用于数据库 D 的规则集 R，对于使用 R 中的任何规则后产生的任何数据库，
规则集 R 仍然可用。(规则适用性)
b 如果目标条件被 D 满足，则应用 R 中的任何规则于 D 上所产生的任何数据库仍可满
足目标条件。(数据库可用性)
c 应用 R 中一个规则序列于 D 上后，得到的数据库不随这规则序列次序变化而变化。
（规则次序无关性）
3.可分解产生式系统
定义：任何待求解的数据库都可以分解为若干个独立处理分量的产生式系统称为可分解产生
式系统。
求解方法：将初始数据库分解为几个可独立处理的分量，用规则分别求解，生成新的数据库，
再分解，再求解，知道结束。
可分解产生式系统的一般性算法：
1 DATA ←初始数据库
2{Di} ← DATA， Di 库：独立的分量数据库
3 until {Di} 的所有元素都满足结束条件之前，do：
4 begin 5 从 {Di} 中选择一个不满足结束条件的 D*
6 把 D*从{Di} 中删除
7 从规则集 R 中选一条可用于 D*的规则 r，设 D 是人应用于 D*的结果是 D 的分解式。
8 在 {Di} 添加 di
9 end
AI 领域的知识分类
a 陈述性知识：用于描述综合数据库的状态。（如事实等）
b 过程性知识：用于规则中表达问题的知识.（如客观规律等）
c 控制性知识：用于构成控制策略的知识（算法、数据结构等）
AI 系统的一个难题：知识表达问题，要能够客观的描述现实，简化求解过程，有效的提高
求解效率，降低求解代价。
产生式系统的搜索策略
状态空间：由给定问题的所有可能的状态组成的空间（相当于全集 G）
搜索空间：按某种策略在状态空间中选取的部分空间（G 的子集）
解路径（解空间）：求解问题的一条有效路径。
搜索策略的基本思路：搜索空间必须包含解路径，如果问题有解，且尽量缩小搜索空间。
搜索策略的评价准则：总体费用最低
费用的划分： a 规则应用的费用：执行规则时所花的费用 b 控制费用：选择规则所花的
费用。
1.回溯策略
2.图搜索策略
3.启发式图搜索策略 1）A 算法 2）爬山算法 3）分支界限算法 4）动态规划算法 5）A*算法
6）h 函数与 A*的关系 7）关于单调性限制 8）A*算法示例
例 四皇后问题
定义综合数据库：
设：DATA={ij︱1<=i,j<=4},其中：ij 表示棋子所在行列 如：24 表示第二行第四列有一枚
棋子
因为棋盘上 可放入的棋子数为 0～4 个
所以集合中元素数位 0 ～4 个，即 length（DATA）=0 ～4
图搜索的实质是从问题空间中找出一张包含目标节点的子图。
图搜索的结果：1，一个完整的搜索图 G。2 一个解路径，用指针表示的解路径。
Procedure GraphSearch
1 G=G0(G0=s),open=(s) //s:初始状态
2 closed=()
3Loop:if open=() then exit(fall)
4 n←first(open) remove(n,open), add(n,closed)
5 if goal(n) then exit(success)
6{mj} ←expand(n), //mj 不含 n 的先辈节点
7 open←add(open，mj) // mj 不在 open，closed 中
标记 mj 每个到 n 节点指针
确定是否需要修改已在 open，closed 中的每个节点到 n 的指针
确定是否需要修改已在 closed 中的每个节点的后继节点原来的指针。
8 按照某种方式排列 open 表中的节点，go loop
深度优先算法
Procedrue depth-First-Search
1 G=G0(G0=s),open=(s),closed=() //s:初始状态
2 Loop:if open=() then exit(fall)
3 n←first(open)
4 if goal(n) then exit(success)
5remove(n,open), add(n,closed)
6{mj} ←expand(n), //mj 不含 n 的先辈节点
7 open←add(open，mj) // mj 不在 open，closed 中
标记 mj 每个到 n 节点指针，按照节点深度递减顺序排列 open 中的节点
8 go loop
讨论 1：如果问题有解，有深度优先搜索算法，是否能够找到解？
不一定.解空间是否有限？
讨论 2：本算法的改进之处是 open 中节点按照深度优先排列，但是没有对深度加以控制，
可能造成搜索代价太大
宽度优先算法：Procedrue breadth-First-Search
1 G=G0(G0=s),open=(s),closed=() //s:初始状态
2 Loop:if open=() then exit(fall)
3 n←first(open)
4 if goal(n) then exit(success)
5remove(n,open), add(n,closed)
6{mj} ←expand(n), //mj 不含 n 的先辈节点
7 open 标记每个到 n 节点指针，按照节点深度递增顺序排列 open 中的节点
8 go loop
理论上可以利用宽度优先搜索能够找到解，如果问题有解的话。
讨论：宽度优先算法和深度优先算法可能出现组合爆炸。都没有利用任何启发式信息，所以
称为无信息搜索策略 pen←add(open，mj) // mj 不在 open，closed 中
宽度优先例题：
由一张桌子 T、三个积木 A、B、C 组成一个积木世界，初始状态是 A 在 B 上，B 在桌子
上，C 在桌子上；目标状态是：A、B、C 依次从上到下排列在桌子上。如图
解：1）状态描述（P1，P2，P3）表示按 A、B、C 顺序依次分别在 P1,P2,P3 上其中 Pi 是积
木或者桌子。初始状态时（B、T、T）,目标状态 可以表示（B、C、T）
2）定义操作:move(x,y)表示将积木 x 移到 Y 上 ；
约束条件:a X 顶部必须是空的 b 如果 Y 是积木，Y 的顶部必须是空 c 同一种状态出现
不得多于一次。
1）解题过程 2）open 表和 closed 表
3）节点样子画出整个图 G 和解路径
4）程序何时结束 5）改用深度优先如何？
启发式图搜索策略：基本概念
启发式图搜索的实质是利用启发信息有目的地进行搜索，减少搜索的盲目性。降低搜索空间
找到最佳解
启发式信息用于解决 open 表中节点的排列次序问题，方法是利用一个评价函数计算 open 表
中节点的评价函数值，按照函数值从小到大排列所有节点。
评价函数的目的：把最有希望得到最佳解或者解的排列在前面。
路径 ：给定节点序列（n0，n1，…nk）。如果该序列中的任一节点 ni-1 都有后继节点 ni，
则该节点序列为从 n0 到 nk 的一条路径，路径长度为 K
路径耗散值：路径耗散值等于该路径上所有相邻节点间耗散值的总和。
设 ： 路 径 山 任 两 点 间 的 耗 散 值 为 才 C(ni,nj), 则 从 ni 到 nk 的 路 径 耗 散 值 为
C(ni,nj)=C(ni,nj)+C(nj,nk)
最佳路径耗散值：最佳路径上的实际耗散值，记为：K(ni,nj).
K(ni,nj)<= C(ni,nj)
定义几个函数
1）g*(n)=k(s,n):从初始节点 s 到当前节点 n 的最佳路径的耗散值。
2)h*(n)=k(n,t):从当前节点 n 到目标节点 t 的最佳路径的好三者。
3)f*(n)= g*(n)+h*(n):从初始节点 s 通过当前节点 n 到目标节点 t 的最佳路径的耗散值。
4)评价函数：f(n)=g(n)+h(n),其中 f，g，h 分别是 f*，g*，h*的估计值。
通常约定:f(n)按照升序排列。
讨论：有上述定义，得:1)g(n)>=g*(n)2)当 h=0 且 g(n) =d(n) 时，f(n)=d(n)既宽度优先策略，
d(n):节点深度。3）h(n)称为启发函数。
A 算法：1 G=G0(G0=s),open=(s),closed=() ，f(s)=g(s)+ h(s) //s:初始状态
2 Loop:if open=() then exit(fall)
3 n←first(open)h()
4 if goal(n) then exit(success)
5remove(n,open), add(n,closed)
6{mj} ←expand(n), //mj 不含 n 的先辈节点
计算 f(n,mi)=g(n,mi)+h(mi),(自 s 经过 n，mi 到目标节点的耗散值)
open←add(open，mj) 标记 mj 到 n 的指针 (mj 不在 open，closed 中)
if f(n, mk)<f(mk) then f(mk) ← f(n, mk)标记 mk 到 n 的指针(mk 在 open 中)
if f(n, mL)<f(mL) then f(mL) ← f(n, mL)标记 mL 到 n 的指针(mL 在 closed 中)
add(mL,open),把 mL 放回到 open 中
7 Open 中的节点按 f 值升序排列
8 go loop
例 八数码问题
令：g(n)=d(n) 节点深度
h(n)=w(n) 不在位的数码个数(启发函数)
则 f(n)=d(n)+w(n)
如初始节点 s 的 f 值 f(0)=d(0)+w(0)=0+4=4
有 4 个数码不在位。
对于 f(n)=g(n)+h(n),如果单独考虑 g(n)或者 h(n),即，
1) f(n)=g(n) 只考虑搜索过的路径已经耗费的费用；//分支界限算法
2）f(n)=h(n) 只考虑未来的发展趋势//爬山算法
那么可以得到两种特殊的算法：爬山算法和分支界限算法。
爬山算法：procedure Hill _Climbing
1 n=s2 Loop: if goal(n) then exit(success)3{mi} ←expangd(n),计算每个 h(mi)
nextn ← h(mi)最小值的节点 4 if h(n)<h(nextn) then exit(fail)5 n ←nextn
6go loop 优点，缺点
分支界限算法 f(n)=g(n)：Procedure Branch_Bound
1 queue(s-s),g(s)=0 //queue 中保存的是从 s 出发的路径。
2 Loop：ifqueue=0 then exit（fail）
3 path←FIRST(queue)，n ←LAST(pATH) //取第一条路径，及该路径的最后节点 n
4 if goal(n) then exit(success)
5 {mj} ←expand(n), 计算 g(mj)= g(n,mj)
remove(s-n,queue),add(s-mj,queue)
//删除原来的路径，添加长度加一的路径。
6 queue 队列中分支按 g 值升序排列
7 GO LOOP
例 下图右八城市，城市间的耗散值已经给出，利用分支界限算法给出从 S 到 t 的最佳路径。
动态规划算法：Procedure dynamic_Programming
1 queue(s-s),g(s)=0 //queue 中保存的是从 s 出发的路径。
2 Loop：ifqueue=0 then exit（fail）
3 path←FIRST(queue)，n ←LAST(pATH) //取第一条路径，及该路径的最后节点 n
4 if goal(n) then exit(success)
5 {mj} ←expand(n), 计算 g(mj)= g(n,mj)
remove(s-n,queue),add(s-mj,queue)
//删除原来的路径，添加长度加一的路径。
6 仅保留 queue 中到达某一公共节点路径中耗散值最小的路径，余者删除；queue 队列中分
支按 g 值升序排列
7 GO LOOP
讨论 a 动态规划与分支界限差别在于去掉公共路径的冗余部分，提高效率。
b 如果问题空间是树结构，动态规划与分支界限相同。因为对于树结构不存在到达同一节
点有多重路径的情况。
C 动态规划 改进的代价。比如上例中，增加一个城市。
A 算法总结：1 初始状态，open=（s）
2 正常情况下（非成功非失败），取 open 中的第一个节点 n，将 n 由 open 转移到 closed。
3 扩充节点 n ，将新节点加入到 open 中
4 修改某些节点的路径
5 open 中节点按照升序排列
值得重视的一点：A 算法失败的唯一原因是 open 表为空
思考题：图中：s 是起始点 t 是目标节点；如果存在从 s 到 t 的一条最佳路径。而 n 是最佳
路径上的一点。
1）f*(s) f*(n) f*(t) 的关系
2）如果 f*(s)=10 ,g*(n)=4 问 h*(n)=?
A*算法（最佳图搜索算法）：A*算法定义：
对于算法 A，如果有 h（n）≤ h*（n）,即 h（n）以 h*（n）为上界，则称 该
算法称为 A*算法。
如果令 h（n）=0，则满足 h（n）≤ h*（n）
这就是分支界限算法 和动态规划算法。
再令 g(n)=d(n) (d(n)是节点深度）则 f(n)=d(n);
A*算法就是宽度优先算法。宽度优先算法能找到最佳解。
例：第二章中八数码问题 令 h(n)=w(n)=不在位数字个数。
算法可采纳性：给定任意图，设存在从开始节点 s 到目标节点 t 的路径。如果算法能够结束
在 s 到 t 的最佳路径上，则称该算法是可采纳的。A*是具有可采纳性。
定理 1 对于有限图，如果从 s 到 t 存在路径，则 A 算法一定成功结束。
推论 因为 A*算法是 A 算法的一个特例。所以在有限图上如果如果从 s 到 t 存在路径，
则 A*算法一定成功结束。
定理 2 对于无限图，如果存在 s 到 t 路径，则 A*算法一定成功结束。
推论 ： open 表中任一满足 f(n) ∣f*(s)的节点 n 最终都将被 A*选作扩展节点。
定理 3：如果存在节点 s 到目标节点 t 路径，则 A*算法一定能找到最佳解结束。
推论 ：A*选来扩展的节点都有 f(n) ∣f*(s)
小结 1 如果存在节点 s 到目标节点 t 路径，则 A*算法一定能找到最佳解结束。
2 open 表中所有满足 f(n) ∣f*(s)的节点 n 最终都将被 A*选作扩展节点。
3 A*选来扩展的节点都有 f(n) ∣f*(s) 4 f*(s)作为 A*的一个衡量上限。
h 函数和 A*算法的关系：本节重点来讨论 h 函数（即启发信息量）对 A*算法搜索效率的影
响总结。
定义：给定两个 A*算法 A1 和 A2，都有 f(n1)=g(n1)+h(n1)，f(n2)=g(n2)+h(n2)如果对于所
有非目标节点 n，有 h(n1) <h(n2)，则算法 A2 比算法 A1 有较多启发信息。
讨论：启发信息与 h 函数值成正比。极端情况下，完全没有启发信息时 h=0，则此时 A*算
法就是宽度优先算法。
定理：给定两个 A*算法 A1 和 A2 如果 A2 的启发式信息比 A1 多，则在任何存在节点
s 到目标节点 t 的路径上，搜索结束时，由 A2 扩展的每一个节点必定被 A1 扩展。(A1 扩展
的节点多)，注意搜索空间小，不代表能够找到最佳解。
当 h=0 时，除最下面一层节点外，所有节点都进入 closed 表。求解路径如图红线所示。
当考虑到 h 时，被扩充的节点只有 s、c、 j，解路径相同
h 函数单调性限制
单调性限制的作用是：避免重复计算某些节点的 f 值（主要对连通图而言）以便减少搜索代
价。
单调性定义：给定一个启发函数 h，如果对于所有节点 ni 和 nj (nj 是 ni 的子节点)，如果满
足 h(ni)-h(nj) ≤c(ni,nj) h(t)=0,则称 h 满足单调性限制。
上式可以写成 h(ni)-≤ h(nj)+ c(ni,nj)，可以理解为三角不等式。
定理 5：如果好 h(n)满足单调性限制条件，则 A*算法扩展了节点 n 之后，就找到了到达节
点 n 的最佳路径，即：如果 A*选中节点 n，在单调性限制条件下，有 g(n)=g*(n)
A*算法示例：迷宫问题，定迷宫图如下，找出从入口到出口的最短路径。
解 1）综合数据库 定义 状态集：{（x，y）∣1≤x，y≤4}，其中（x，y）表示任意节点的
坐标，所以问题表示为求解从（1,1）到（4,4）的最短路径。
2 规则集（定义 4 条移动规则），右移 R1： if（x，y）then （x+1，y）
左移 R2： if（x，y）then （x-1，y）
上移 R3： if（x，y）then （x+1，y+1）
下移 R4： if（x，y）then （x+1，y-1）
两种解法：宽度优先，设定 h(n)
3）A*算法 f 函数定义 f(n)=g(n)+h(n)，设每一步的耗散值为 1（单位耗散值）
定义：g(n=d(n)从初始节点 s 到当前节点 n 的搜索深度。h(n)=∣ -xn∣+ ∣ -yn∣
其中是（xg，yg）目标节点的坐标， （xn，yn）是当前节点的坐标。显然满足： h(n) ≤ h*(n)
4）Open 表节点排序，先按 f 值排序，如果 f 值相同，则深度优先，
关于 f 函数值的意义的讨论：为了调整 g 和 h 在 h 中的作用比例， 设 f=g+w*h
1）令 w=0 则 f=g，此时，A*成为宽度优先算法。特点：可扩大搜索范围便于找到最佳解，
但是费用比较大。
2）令 w 为一个大的整数，则加大了 h 在 f 函数中的作用力度。其意义在于：不考虑到目前
已经 消耗的费用，只关心当前节点到目标节点剩余的搜索工作量。
本章算法汇总 1.回溯策略 2.图搜索策略
A 算法：(n)=g(n)+h(n) 1.当 h(n)=0 g(n)=-d(n) 深度优先 2.当 g(n)=0 爬山算法
3.当 h(n)=0 分支界限算法 各分支只保留一个 动态规划算法 (n)=0 g(n)=d(n) 宽度优先
算法
A* 算法 ： 分支界限算法 动态规划算法 宽度优先算法
本章例题汇总 1.四皇后问题 回溯策略 2 积木世界问题 宽度优先
3 八数码问题 A 算法 4 八城市 s-t 分支界限算法。5 迷宫问题 A*算法
命题逻辑
主要内容 1）命题的表示、命题的演算 2）命题演算中的公式及其应用 3）命题逻辑推理
命题是一个能确定真的或假的的判断。
补充二 谓词逻
2-4 前束范式
