当前位置：文档之家 › 第4章 与或图搜索

第4章 与或图搜索

  • 格式：ppt
  • 大小：1.74 MB
  • 文档页数：48

下载文档原格式

  / 48

合集下载

人工智能 -课程简介+课程大纲模板

人工智能 -课程简介+课程大纲模板

人工智能-课程简介+课程大纲模板(总7页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--《人工智能理论与应用》课程简介课程编号：A0940111课程名称：人工智能理论与应用学分/学时：3/48先修课程：《数据结构》、《离散数学》和《高级程序设计语言》适用专业：计算机科学与技术课程性质：限选考核方式：考查考核形式：大作业、实验评估建议教材：人工智能教程，王士同主编，电子工业出版社，2006年2月第2版内容简介：（200字以内）（黑体五号）1、人工智能研究的发展和基本原则：人工智能的研究和应用；人工智能研究的发展；人工智能研究的成果；人工智能研究的基本原则；存在的问题和发展前景2、一般图搜索：回溯策略、图搜索策略、无信息搜索过程、启发式图搜索过程、搜索算法讨论。

3、与或图搜索问题：与或图的搜索、与或图的启发式搜索算法AO*、博弈树的搜索。

4、谓词逻辑与归结原理：命题逻辑、谓词逻辑基础、谓词逻辑归结原理、HERBRAND定理。

5、知识表示：知识、知识表示、知识观、产生式表示方法、语义网络表示、框架表示以及其他表示方法。

6、不确定性推理方法：不确定性推理的基本问题、贝叶斯网络、主观贝叶斯方法、确定性方法、证据理论。

7、机器学习：机器学习概论、实例学习、基于解释的学习、决策树学习、神经网络学习、知识发现与数据挖掘。

8、高级搜索：基本概念、局部搜索算法、模拟退火算法、遗传算法等。

人工智能理论与应用Artificial Intelligence Theory and Application 课程编号：A0940111学分：3学时：48 学时（讲课学时：32 实验学时：16）先修课程：《数据结构》、《离散数学》和《高级程序设计语言》适用专业：计算机科学与技术建议教材：人工智能教程，王士同主编，电子工业出版社，2006年2月第2版主要参考书：（1）高等学校规划教材:人工智能原理及其应用电子工业出版社王万森 2012（2）人工智能及其应用(第4版) 蔡自兴、徐光佑清华大学出版社 2010开课学院：计算机科学与工程学院修订日期：2015年4月一、课程说明（黑体五号）人工智能是一门综合性前沿学科，是计算机学科的重要分支。

人工智能第4章图搜索技术

人工智能第4章图搜索技术

OPEN表的首部，转步2。
例4.4 对于八数码问题，应用
深度优先搜索策略，可得如图4—
6所示的搜索树。
283
深度优先搜索亦称为纵向搜 1 4 765
索。由于一个有解的问题树可能
含有无穷分枝，深度优先搜索如
果误入无穷分枝(即深度无限,但
解不在该分支内)，则不可能找到
目标节点。所以，深度优先搜索
策略是不完备的。另外，应用此
例4.6 设A城是出发地，E城是目的地，边上的数字代表 两城之间的交通费。试求从A到E最小费用的旅行路线。
B 4
6
A
3
4
A
E
C 3
D1
3
4
D2 23
E1 3
C
D
2
(a)
E2
B2 6
深度优先搜索算法：
步1 把初始节点S0放入OPEN表中； 步2 若OPEN表为空，则搜索失败，退出。
步3 取OPEN表头节点N放入CLOSED表中，并冠以顺序编号n；
步4 若目标节点Sg=N，则搜索成功，结束。 步5 若N不可扩展，则转步2； 步6 扩展N，将其所有子节点配上指向N的返回指针依次放入
2831 14 765
第4章 图搜索技术
2 283
14 765
6 83
214 765
7 283 714 65
14 83 214 765
15 283 714 65
22 83 214 765
23 813 24 765
3 23 184 765
8 23
1 84 7 65
9 23 184 765
16 1 23
第4章 图搜索技术
步1 把S0放入OPEN表中，置S0的深度d(S0)=0； 步2 若OPEN表为空，则失败，退出。 步3 取OPEN表头节点N，放入CLOSED表中，并 冠以顺序编号n； 步4 若目标节点Sg=N，则成功，结束。 步5 若N的深度d(N)=dm(深度限制值)，或者若N无 子节点，则转步2； 步6 扩展N，将其所有子节点Ni配上指向N的返回 指针后依次放入OPEN表中前部，置d(Ni)=d(N)+1，转 步2。
与或图搜索问题

与或图搜索问题


与或图搜索问题的特点
组合优化问题
与或图搜索问题是一个典型的组 合优化问题，因为解决方案空间 通常非常大，需要采用高效的搜 索策略来找到最优解。
逻辑约束
与或图中的节点之间存在逻辑约 束，即某些节点必须同时满足与 （AND）或（OR）关系。
决策变量
与或图中的节点代表决策变量， 需要确定它们的取值以最大化目 标函数或满足特定条件。
03
与或图搜索问题的求解算法
深度优先搜索算法
深度优先搜索是一种用于遍历或搜索树 或图的算法。该算法会尽可能深地搜索 树的分支，当节点v的所在边都己被探 寻过，搜索将回溯到发现节点v的那条
边的起始节点。
深度优先搜索算法适合求解与或图中的 AND-OR图问题，可以找到所有解或
最优解。
算法步骤：选择一个起始节点，标记为 已访问，然后递归地搜索与该节点关联 的所有未被访问的节点，直到所有节点
与或图搜索问题的求解目标
找到最优解
与或图搜索问题的求解目标是找到满足所有 逻辑约束的节点组合，以最大化目标函数或 满足特定条件。
高效求解
由于与或图搜索问题通常具有较大的解决方案空间 ，因此需要采用高效的搜索策略和启发式算法来快 速找到最优解。
实际应用
与或图搜索问题在许多实际应用中具有广泛 的应用，如电路设计、计划调度、物流优化 等。
路径规划
在路径规划问题中，与或图搜索问题可以用于寻找满足特定条件的路径， 如最短路径、最少花费路径等，使得路径能够连接起点和终点。
02
与或图搜索问题概述
与或图搜索问题的定义
与或图搜索问题是一种组合优化问题，旨在寻找满足一系列与 （AND）或（OR）逻辑关系的节点组合。
它通常由一个有向图表示，其中节点表示决策变量，边表示 逻辑关系。
第4章 图搜索策略

第4章 图搜索策略


4.1.1 通用或图搜索算法
或图通用搜索算法：
设S0 ：初始状态, Sg：目标状态 1. 产生一仅由S0组成的open表，即open=(S0)； 2. 产生一个空的closed表； 3. 如果open为空，则失败退出； 4. 在 open 表上按某一原则选出第一个优先结点， 称为n，将n放到closed表中，并从open表中去掉 n；
4.1.2 A算法与A*算法
由定义有 f(n’ ） =g(n’ ） +h(n’ ） =g*(n’ ） +h(n’ ） (因为n’在最优路径上） ≤ g*(n’ ） +h*(n’ ） =f*(n’ ） =f*(S0 ） (由于A*的定义h(n) ≤h*(n)) 所以f(n’）≤f*(S0）成立。
4.1.2 A算法与A*算法
推论1 若问题有解，A*算法一定终止。
（2-1）
因为若A*算法不终止，则命题2的
f(n）≥g(n）≥g*(n）≥d*(n）· e
与命题3的
f(n’）≤f*(S0） (2-2）
同时成立，则产生矛盾。
4.1.2 A算法与A*算法
命题 4 若问题有解， A* 算法终止时一定 找到最优解, 即A*算法是可采纳的。
4.1.1 通用或图搜索算法
注1 ： 若生成的后继节点放于：
（ 1 ） Open 表的尾部 —— 相当于 Breadth-firstsearch；
（ 2 ） Open 表 的 首 部 —— 相 当 于 Depth-firstsearch； （3）根据启发式函数f的估计值确定最佳者，放 于Open 表的首部——相当于Best-first-search 最佳优先搜索。
证：A*终止只有两种情况。 (1) 在第3步, 因open为空而失败退出 但由命题 3 可知： A* 终止前， open 表上必 存在一点n’，满足 f(n’）≤f*(S0） 即open表不会空，所以，不会终止于第3步。
与或图

与或图

与或图的搜索 及应用
北京信息科技大学 孙骏 2014.05.13
与或图的搜索策略
1 与或图的一般搜索过程 2 与或图的广度优先搜索
3 与或图的深度优先搜索
4 与或图的有序搜索 5 博弈树的启发式搜索
1 与或图的一般搜索过程

与图: 把一个原问题分解为若干个子问题，P1，P2， P3，…可用“与图”表示；P1，P2，P3，…对应的子问
S0 2
A 6 t1 5 t2 E C 1 t3 2 F 3 1 2 B 2
D 1 G 1
t4 2 t5
解：左边解树， 按和代价：h(A)=11 h(S0)=13; 按最大代价：h(A)=6 h(S0)=8; 右边解树， 按和代价：h(G)=3, h(D)=4, h(B)=6, h(S0)=8; 按最大代价：h(G)=2, h(D)=3, h(B)=5, h(S0)=7
P
E
F
2
G
0 0 2 2 0 0
H
3
2
h(N)=2, h(P)=7, h(C)=3, h(A)=8 左子树h(S0)=9
3
2
2
2
三阶梵塔问题
1 2 3 1 2 3
A
A
B C
B C
初始配置
目标配置

问题描述: 采用三元组表示状态: S=(i,j,k) 其中，i, j, k分别表示金片C,B，A所在的钢针号。 初始状态（1，1，1），目标状态（3，3，3）
a
4-5=-1 b
5-4=1
5-5=0
5-5=0
6-6=0
程可用一个“与或图”来表示
P P1 P11 P12 P2 P31 P3 P32 P33
(搜索推理技术-与或树搜索)

(搜索推理技术-与或树搜索)


7、无判断起始节点1可解
8、从OPEN中删除含有可解先辈节点的节点
删除
OPEN= { B, C, t1, 10, 11, 12, A, t2, t3 }
CLOSED= { 1, 2, 3, 4, 5, 6, 7, 8, 9 } OPEN= {t1, 10, 11, 12, t2, t3}
CLOSED= {1, 2, 3, 4, 5, 6, 7, 8, 9} 说明：对于OPEN表中的叶节点直接移到 CLOSED表，不作任何处理
OPEN= {9, B, C, t1, 10, 11, 12, A} CLOSED= {1, 2, 3, 4, 5, 6, 7, 8}
第九大循环（3、4、5、6、7、8步）： 3、从OPEN表中取出节点9，并送到CLOSED表 4、扩展节点9，生成后继节点 t2、t3，并送到 OPEN表的末端 5、有叶节点 6、实现可解标志过程（可以判断节点9、4、2可解）
即OPEN是堆栈
注意
由于深度限制，深度优先搜索算法有可能找不 到解
例：
深度界限为4
√
2
1
√
√
6
√
3
Ⅹ A √ √
7 √
C
Ⅹ
4
5
8
t
√
Ⅹ B
t
t
t
t
√
√
√
√
注：后生成的节点画在左边
课堂练习：用宽度和深度优先搜索算法找出解树
提示：对于宽度优先搜索，先生成的节点画在左；
对于深度优先搜索，后生成的节点画在左
CLOSED= { 1, 2, 3, 4, 5, 6, 7, 8, 9, t1, 10 }
搜索过程演示
√
与或图搜索问题

与或图搜索问题


f
0
0 1
d b
0 3
m h
1
1
n e
k i
-3 1
6
a
0
c
-3
3
g
5 4
6
j
0
5
-3
3 3
-3
0
2
2
-3
0
-2
3 5 4
1
-3
0 6
8 9
-3
α-β剪枝
极大节点的下界为α。 极小节点的上界为β。 剪枝的条件：
后辈节点的β值≤祖先节点的α值时， α剪枝 后辈节点的α 值≥祖先节点的β值时， β剪枝
α-β剪枝的其他应用
故障诊断
A 风险投资
B
C
D
1
极大
1
b
0
极小
6
a
0
3
1
0
-3
3
-3
-3
-2
1
-3
6
-3
0
5
-3
3 3
-3
0
2
2
-3
0
-2
3 5 4
1
-3
0 6
8 9
-3
5 α-β剪枝
设某博弈问题如下图所示，应用极小极大方法进行搜索。假设搜索的 顺序为从下到上，从左到右。当计算完a的值为0后，由于b是极大节 点，马上就可以知道b的值大于等于0。接下来求c的值。由于c是极小 节点，由d的值为-3，知道c的值小于等于-3。而a和c都是b的子节点， 所以即便不扩展节点e，也可以知道b的值一定为0了。所以在这种情 况下，没有生成节点e的必要。同样，在知道b的值为0后，由于k是极 小节点，所以立即知道k的值要小于等于0。而通过节点f、g，知道h 的值至少为3。这样即便不扩展A所包围的那些节点，也能知道k的值 一定为0。所以A包围的那些节点也没有生成的必要，不管这些节点取 值如何，都不影响k的值。如果在搜索的过程中，充分利用这些信息， 不就可以少生成很多节点，从而提高搜索的空间利用率吗？α-β过程 正是这样一种搜索方法。
人工智能中图搜索算法(PDF 159页)

人工智能中图搜索算法(PDF 159页)


图4—5 八数码问题的广度优先搜索
第9页
第4章 图搜索技术
以上两个问题都是在某个有向图中寻找目标或路径问 题，这种问题图搜索问题。把描述问题的有向图称为状态 空间图，简称状态图。图中的节点代表问题中的一种格局， 一般称为问题的一个状态，边表示两个状态之间的联系。 在状态图中，从初始节点到目标节点的一条路径或者所找 到的目标节点，就是问题的解（路径解）。
谓搜索，顾名思义，就是从初始节点出发，沿着与之相连 的边试探地前进，寻找目标节点的过程(也可以反向进行)。 搜索过程中经过的节点和边，按原图的连接关系，形成树 型的有向图，称为搜索树。搜索过程应当随时记录搜索痕 迹。
1.搜索方式 用计算机来实现状态图的搜索，有两种最基本的方式： 树式搜索和线式搜索。 所谓树式搜索，形象地讲就是以“画树”的方式进行 搜索。 即从树根（初始节点）出发一笔一笔地描出来的。
状态图实际上是一类问题的抽象表示。事实上，有许
多智力问题(如梵塔问题、旅行商问题、八皇后问题、农
夫过河问题等)和实际问题（如路径规划、定理证明、演
绎推理、机器人行动规划等）都可以归结为在某一状态图
中寻找目标或路径的问题。因此，研究状态图搜索具有普
遍意义。
第10页
第4章 图搜索技术
4.1.2 状态图搜索 在状态图中寻找目标或路径的基本方法就是搜索。所
第4章 图搜索技术
3. 搜索算法 由于搜索的目的是为了寻找初始节点到目标节点 的路径，所以在搜索过程中就得随时记录搜索轨迹。 为此，我们用一个称为CLOSED表的动态数据结构来 专门记录考查过的节点。显然，对于树式搜索来说， CLOSED表中存储的正是一棵不断成长的搜索树；而 对于线式搜索来说，CLOSED表中存储的是一条不断 伸长的折线，它可能本身就是所求的路径(如果能找到 目标节点的话)。
人工智能技术导论(第三版)

人工智能技术导论(第三版)

member(X, [_|T])if member(X,T). road(A,B,D):-road(B,A,D).% 因为没向图
road(
“西安”
,”北京”
,1165).
road(
“西安”
,”上海”
,1511)
road(
“西安”
,“广州”
,2129).
road(
“西安”
,”昆明”
,1942)
road(
legal1((X,Y)):-X>=Y,X>=0,Y>=0.
update((X,Y,0),Move,Statu1):-
(A,B)=X,
(C,D)=Y,
(E,F)=Move,
C1 is C+E,
D1 is D+F,
A1 is A-E,
B1 is B-F,
Statu1=((A1,B1),(C1,D1),1).
若传教士和野人的数目均为五人，渡船至多可乘三人，请定义一个启发函数，并给出相 应的搜索树。
解：
( 1)设计该问题的状态。例如：((左岸牧师数，左岸野人数 ),( 右岸牧师数，右岸野人数),船的位置)。(2)定义目标状态。这里是： ((0,0),(3,3),1)(3)描述可能的动作。船上所
能够载人的状态就是可能的操作。用谓词move/2表示。( 4) 判断合法状态( 5)深度优先
update((X,Y,1),Move,Statu1):-
(A,B)=X,
(C,D)=Y,
(E,F)=Move,
C1 is C-E,
D1 is D-F,
A1 is A+E,
B1 is B+F, Statu1=((A1,B1),(C1,D1),0). connect(Statu,Statu1):- move(X,Y), update(Statu,(X,Y),Statu1), legal(Statu1). findroad(X,X,L,L):-write(L). findroad(X,Y,L,L1):- connect(X,Z), not(member(Z,L)), findroad(Z,Y,[Z|L],L1).
与或图搜索

与或图搜索

8
• 解图：
初始节点
目标
目标
该解图的耗散值为: (1+(1+1))+(1+1)=5
9
局部解图的耗散值计算
如果我们也将局部图的耗散值记为k(n,N),则: ① 若n是局部图的一个叶节点，则
k(n,N)=h(n)；
② 若n是一个外向连接符指向后继节点{n1,…, ni}，并设该连接符的耗散值为Cn，则
1
与或图例子
2
2.1 基本概念
与或图是一个超图，节点间通过连接符连接。
超图是图的最一般的表达形式，无论什 么图，你都可以说它是超图，就像无论 整数，无理数，复数，反正都是数一样。
超图的定义由两个集合构成：一个点集A， 另一个是点集A中元素的子集的集合B(B 中所有元素的并集就是集合A)。A中的元 素叫节点；B中的元素就叫边，这样超图 H=(A,B)。
17
与或树的一般搜索过程(续)
• 由上述搜索过程所形成的节点和指针 结构称为搜索树。 • 与或树搜索的目标是寻找解树，从而 求得原始问题的解。如果在搜索的某一 时刻，通过可解标示过程可确定初始节 点是可解的，则由此初始节点及其下属 的可解节点就构成了解树。
18
与或树的一般搜索过程(续)
• 如果在某时刻被选为扩展的节点不可扩 展，并且它不是终止节点，则此节点就 是不可解节点。此时可应用不可解标示 过程确定初始节点是否为不可解节点，
如果可以确定初始节点是不可解的，则搜 索失败；否则继续扩展节点。
19
与或树的性质
• 可解与不可解标示过程都是自下而上进行 的，即由子节点的可解性确定父节点的可解性。
• 在与或树中搜索解树时，如果已确定某个 节点为可解节点，则其不可解的后裔节点就不 再有用，可从搜索树中删去；同样，如果已确 定某个节点是不可解节点，则其全部后裔节点 都不再有用，可从搜索树中删去，但当前这个 不可解节点还不能删去，因为在判断其先辈节 点的可解性时还要用到它。
[笔记]人工智能一种现代的方法（第3版）第4章超越经典的搜索

[笔记]人工智能一种现代的方法（第3版）第4章超越经典的搜索

第4章超越经典的搜索1 局部搜索算法和最优化问题1.1 爬山法（贪婪局部搜索）1.1.1 爬山法（最陡上升版本）1.1.2 随机爬山法1.1.3 首选爬山法1.1.4 随机重启爬山法1.2 模拟退火搜索1.2.1 特点1.3 局部束搜索（Local beam search）1.4 遗传算法（Genetic algorithm，GA）1.4.1 例子：八皇后问题1.4.2 遗传算法伪代码：2 使用不确定动作的搜索2.1 与或搜索树3 使用部分可观察信息的搜索3.1 无观察信息的搜索3.2 部分可观察问题的搜索3.2.1 联机搜索4 总结1 局部搜索算法和最优化问题在第3章中讨论的无信息搜索和有信息搜索有如下性质：环境都是在可观察、确定的、已知的，问题解是一个行动序列。

本章将不受这些环境性质的约束，讨论局部搜索（local search）算法，考虑对一个或多个状态进行评价和修改，而不是系统地搜索从初始状态开始的路径。

局部搜索（local search）算法：从单个当前结点出发，通常只移动到它的邻近状态而不保留搜索路径局部搜索不关心路径代价，但是关注解状态。

Agent不知道前面的状态，只知道当前的状态。

比如八皇后问题，不关心是怎么到目的状态的，只关心最终布局对不对，许多重要应用都有这样的性质，如作业空间调度，自动程序设计等。

虽然局部搜索算法不是系统化的，但是有两个关键优点：占用内存少，通常只用常数级的内存通常能在系统化算法不适用的很大或无限的（连续的）状态空间中找到合理的解。

此外，局部搜索算法对于解决纯粹的最优化问题十分有用，其目标是根据目标函数找到最佳状态。

如果存在解，最优的局部搜索算法总能找到全局最大/最小值？？？1.1 爬山法（贪婪局部搜索）定义：不断向值增大的方向移动，直到到达局部最优。

也被称为贪婪局部搜索，因为它只选择邻居中状态最好的一个，而不考虑下一步怎么走。

贪婪算法很容易改善一个坏的状态，但却经常陷入局部最优无法跳出。

图搜索技术


翻动钱币的操作抽象为改变上述状态的算子，
即F＝{a, b, c}
a:把钱币q0翻转一次 b:把钱币q1翻转一次 c:把钱币q2翻转一次 问题的状态空间为<{Q5},{Q0 Q7}, {a, b, c}>
2021/11/6
人工智能
13
3.1.1 状态、操作和状态空间（10）
状态空间图 a
c （0，0，0） （1，0，0） b
初始状态 S0=(1,1,1,…,1,…,1) 目标状态 Sg1 =(2,2,2,…,2,…,2)
Sg2 =(3,3,3,…,3,…,3)
2021/11/6
人工智能
24
n（n≥3）阶梵塔问题
n阶梵塔问题的操作集合表示为： F={Rk(i,j) | i,j={1,2,3}，k={1，2，…，n}}
S5 2 2 1 S13 0 2 1 S21 2 2 0 S29 0 2 0
S6 2 1 1 S14 0 1 1 S22 2 1 0 S30 0 1 0
S7 2 0 1 S15 0 0 1 S23 2 0 0 S31 0 0 0
2021/11/6
人工智能
17
3.1.2 修道士和野人问题的状态空间（4）
目标状态集合{θ0, θ7}
人工智能
12
3.1.1 状态、操作和状态空间（9）
引入一个三元组(q0,q1,q2)来描述总状态，钱币正面为0，反面 为1，全部可能的状态为：
Q0=(0,0,0) ; Q1=(0,0,1); Q2=(0,1,0) Q3=(0,1,1) ; Q4=(1,0,0); Q5=(1,0,1) Q6=(1,1,0) ; Q7=(1,1,1)。
3.1.1 状态、操作和状态空间 3.1.2 修道士和野人的状态空间 3.1.3 梵塔问题的状态空间 3.1.4 重排九宫问题和隐式图 3.1.5 问题求解的基本框架

《搜索与或图搜索》课件


3
搜索的原理
搜索原理是通过将问题分成更小的子问题，并从这些子问题中选择最优解决方案， 从而解决整个问题。
与或图的定义
与或图是什么？
与或图是一种用来表示集合之间 关系的图形。
与或图的表示方法
与或图可以使用布尔运算符来表 示，例如“与”运算符表示两个集 合中的共同元素，而“或”运算符 则表示两个集合的并集。
3 与或图搜索在实际应
用中的案例
与或图搜索经常应用于人 工智能、专家系统、自然 语言处理等领域。
总结
本次课程的学习内容回顾
在本次课程中，我们学习了搜索和与或图搜索的相关概念，以及这些概念在实际应用中的重 要性。
搜索与或图搜索的应用前景
作为计算机科学领域中的重要问ቤተ መጻሕፍቲ ባይዱ，搜索和与或图搜索的应用前景是非常广阔的。
搜索与或图搜索
在计算机科学领域，搜索和与或图搜索是非常重要的概念。在本次演示中， 我们将会深入探讨这两个主题。
搜索的定义
1
搜索是什么？
搜索是为了找到特定信息而从大量信息中进行查找和筛选的过程。搜索是人工智 能、信息检索及其他领域中重要的问题之一。
2
搜索的分类
搜索有两种主要分类：确定性搜索和非确定性搜索。确定性搜索是使用精确匹配 算法的搜索，而非确定性搜索则是使用模糊匹配算法的搜索。
与或图在电子学中的应用
与或图被广泛应用于电子学中的 逻辑电路设计，例如计算机内部 的运算电路。
与或图搜索
1 与或图搜索的定义
与或图搜索是指在一个由 与或图表示的问题空间中 搜索，以找到解决方案。
2 与或图搜索的算法
与或图搜索可以使用许多 不同的算法来完成搜索。 其中最常用的是A*算法、 BFS和DFS。

4-与或图搜索

全信息
对垒过程中，双方都了解当前格局及过去的历史
非偶然
双方都是理智的分析决定自己的行动，不存在“碰运气”的偶然因
素
11
人工智能
sspu 王帅
博弈树
在博弈过程中，任何一方都希望自己取得胜利。因此，在 某一方当前有多个行动方案可供选择时，他总是挑选对自 己最有利而对对方最不利的那个方案行动。 如果我们站在A方立场，则可供A选择的若干方案之间是 “或”关系，因为主动权在A方手里，他或者选择这个方 案，或者选择另一个方案，完全由A决定 但若B也有若干可供选择的方案，则对A来说这些方案之间 是“与”关系，因为这时主动权在B，这些可供选择的方 案中的任何一个都可能被B选中，A必须考虑对自己最不利 的情况的发生 把上述博弈过程用图表示出来，得到的是一棵“与／或” 树 注意：该“与／或”树是始终站在某一方（例如Ａ方）的 立场上得出的，不能一会站在Ａ方立场，一会又站在Ｂ方 立场
24
人工智能 sspu 王帅
极大极小法—计算倒推值示例
1
b
0
1
a
0
3
1
6
极大
极小
0
-3
3
-3
-3
-2
1
-3
6
-3
0
5
-3
3
3
-3
0
2
2
-3
0
-2
3 5 4
1
-3
0 6
8 9
-3
25
人工智能
sspu 王帅
-剪枝
S0
3 ≥3 S2 ≤2
S1
3
3 5 S3 S4
2 S5 S6
设有博弈树，各端点的估值如 图所示，其中S6还没计算估值。 由S3与S4的估值得到S1的倒推 值为3，这表示S0的倒推值最小 为3。另外，由S5的估值得知S2 的倒推值最大为2，因此S0的倒 推值为3。 这里，虽然没有计算S6的估值， 仍然不影响对上层节点倒推值 的推算，这表示S6这个分枝可 以从博弈树中剪去

与或图搜索策略


注意：终止节点一定是端节点，但端节点不一定是终 止节点。
10
可解节点: 6. 可解节点:节点须满足下列 条件之一： (1) 终止节点是可解节点; (2)一个与节点可解，当且仅当其子节点全都可解； (3)一个或节点可解，只要其子节点至少有一个可解； 7.不可解节点: 不可解节点: 不可解节点 关于可解节点的三个条件全部不满足的节点称为不可 解节点。 8.解树 解树: 解树 由可解节点所构成,并且由这些可解节点可推出初 始节点(它对应于原始问题)为可解节点的子树.
11
可解性判别
1 3 2 4 B 5 t1
t4
t3 t2 A
12
可解性判别
S0
A D
B C 3 G L M 3 0 0 2 2 2 E 2 H F
2
2
13
例题
三阶梵塔
C B A
（1,1,1）
三元组
(i, j, k)
i 代表金盘C所在的杆号；j代表金盘B所在的 杆号；k代表金盘A所在的标号。
14
1 3 2 4 5 t1
3) 4)
t4
t3 t2 A
5)
此时，closed 表就是由节点1,2,3,4,5和t1,t2,t3,t4构成的解树，如图中粗线所示。
22
与／或树的深度优先搜索算法
1、把初始节点S0放入OPEN表； 2、移出为OPEN表的第一个节点N放入CLOSED表，并冠以序号n； 3 、如果节点N 的深度大于等于深度界限,则转第5部的第(1); 4、若节点N可扩展，则做下列工作：
t5 G 2 1 t4 F t3 E 1 D 2 3 B 2 1 2 c S0 2 5 A 6 t1
目标 目标
9
其它几个概念与术语

《人工智能》课程教学大纲

《人工智能》课程教学大纲《人工智能》课程教学大纲一、课程基本信息开课单位课程名称开课对象学时/学分先修课程课程简介：人工智能是计算机科学的重要分支，是研究如何利用计算机来模拟人脑所从事的感知、XXX人工智能课程类别课程编码开课学期个性拓展GT第4或6学期网络工程专业、计算机科学与技术专业36学时/2学分（理论课：28学时/1.5学分；实验课：8学时/0.5学分）离散数学、数据结构、程序设计推理、研究、思考、规划等人类智能活动，来解决需要用人类智能才能解决的问题，以延伸人们智能的科学。

该课程主要讲述人工智能的基本概念及原理、知识与知识表示、机器推理、搜索策略、神经网络、机器研究、遗传算法等方面内容。

二、课程教学目标《人工智能》是计算机科学与技术专业的一门专业拓展课，通过本课程的研究使本科生对人工智能的基本内容、基本原理和基本方法有一个比较初步的认识，掌握人工智能的基本概念、基本原理、知识的表示、推理机制和智能问题求解技术。

启发学生开发软件的思路，培养学生对相关的智能问题的分析能力，提高学生开发应用软件的能力和水平。

三、教学学时分配《人工智能》课程理论教学学时分派表章次第一章第二章第三章第四章第五章第六章首要内容人工智能概述智能程序设计言语图搜索技术基于谓词逻辑的机器推理呆板进修与专家系统智能计算与问题求解合计学时分配35464628教学方法或手段讲授法、多媒体讲授法、多媒体探究式、多媒体讲授法、多媒体概述法、多媒体开导式、多媒体《人工智能》课程实验内容设置与教学要求一览表实学尝试序项目号名称配1)了解PROLOG语言中常1) Prolog运转环境；量、变量的表示方法；实分支2)使用PROLOG举行事实验与循实库、规则库的编写；库、规则库的编写方法；环程3)分支程序设计；一序设4)循环程序设计；一计5)输入出程序设计。

5)掌握PROLOG输入输出程序设计；1）了解PROLOG中的谓词1)谓词asserta和递归实与表实处理验程序二设计4）掌握PROLOG表处理程4)综合应用程序设计。

与或图的搜索算法

与或图的搜索算法
contents
目录
• 与或图的基本概念 • 与或图的搜索算法 • 与或图的优化算法 • 与或图的应用场景 • 与或图搜索算法的挑战与未来发展
01
CATALOGUE
与或图的基本概念
与或图的定义
总结词
与或图是一种特殊的图形结构，用于表示一组逻辑表达式之 间的关系。
详细描述
与或图由节点和边组成，其中节点表示变量或逻辑运算符， 边表示逻辑关系。每个节点可以是一个与节点（AND节点） 或一个或节点（OR节点），表示相应的逻辑运算符。
总结词
A*搜索算法是一种启发式搜索算法，它 结合了最佳优先搜索和Dijkstra算法的特 性。
VS
详细描述
A*算法使用一个启发函数来评估节点的重 要性，并优先探索最有可能达到目标状态 的节点。
03
CATALOGUE
与或图的优化算法
记忆化搜索
要点一
总结词
通过存储已搜索的节点状态，避免重复搜索，提高搜索效 率。
启发式搜索
总结词
利用启发式信息指导搜索方向，优先搜索最有希望达 到目标节点的路径。
详细描述
启发式搜索是一种基于启发式信息的搜索算法，它利 用启发式信息来指导搜索方向，优先搜索最有希望达 到目标节点的路径。启发式信息可以是与目标节点距 离最近的节点、最短路径长度等。在搜索过程中，启 发式搜索会根据启发式信息评估每个节点的优先级， 优先搜索优先级最高的节点。启发式搜索可以在一定 程度上减少不必要的搜索，提高搜索效率。
问题转化
为了扩大算法的应用范围，需要研究如何将其他类型的 问题转化为与或图问题，以便利用该算法进行求解。
THANKS
感谢观看
详细描述
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

解图的定义：
• 是由能解节点构成的一个子图，是包含一节点（n） 到目的(终)节点集合（N）的、连通的能解节点的子 图. • 在一个与或图 G 中，从节点 n 到节点集 N 的解图 记为 G， G 是 G 的子图. 1．若 n 是N的一个元素，则G由单个节点n组成； 2．若 n 有一个指向节点集 {n1…,nk} 的外向连接 符 K，使得从每一个节点 ni 到 N 有一个解图 (i=1,…,k)，则 G由节点 n，连接符 K，以及 {n1 ,…,nk}中的每一个节点到 N 的解图所组成； 3．否则 n 到 N 不存在解图. • 如果 n=s 为初始节点，则解图为所求解问题的解图.
4 与或图启发式搜索算法 AO*
• 假设：G；G；h(n)是从节点 n 到一组终叶节点的 一个最优解图的一个代价估计，评价函数q(n)=h(n) AO*过程: 1.建立初始搜索图，G:=s，计算 q(s)=h(s)，IF GOAL(s) THEN M(s,SOLVED)； 2. Until s 已标记为 SOLVED, do: 3. Begin 4. G := FIND(G)；根据连接符标记（指针）找出一 个待扩展的侯选局部解图G（连接符在11步标记） 5. n := G 中的任一非终节点; 选一个当前节点 6. EXPAND(n),生成子节点集{ni}，如果 ni G， G:= ADD({ni},G),计算 q(nArtificial Intelligence i)=h(ni)，IF GOAL(ni) THEN M(ni, SOLVED);
k(n, N)= Cn+ k(n1, N)+…+ k(ni, N)
• 具有最小耗散值的解图称为最佳解图，其值 也用 h*(n) 标记。 Artificial Intelligence
• 例：从节点 n 开始，正确选择一个外 向连接符，一直进行下去直到产生的 每一个后继节点成为集合N中的一个元 素为止。下图给出了 n0 →{n7，n8}的 三个解图（耗散值分别为 8，7，5）.
h(n0)=3
AO*搜索算法的过程
• • • • • • 主要步骤 第4步(G’) 第5步(n) 第6步 第7步(S) 第11步 • • • • • • 第1循环 (n0) (n0) (n1,n5,n4) (n0) 比较,选 n0→n1; n1 不可解; • • • • • • 第2循环 n0→n1 (n1) (n2,n3) (n1) 1) 比较,选 n1→n3; n3 不可解; 2)比较,选 n0→n5, n4; n5, n4不可 解; • 1) 加n0 → S; 2)无; • • • • • • 第3循环 • n0→n5, n4 • (n5) • (n6,n7,n8) • (n5) • 比较,选 • n5→n7, n8; 改指针; n7, n8可解, n5 可解 第4循环 n0→n5, n4; (n4) (n5,n8) (n4) 1)比较,选 n4→ n8; n8可解, n4 可解; 2) n4 , n5可 解; n0可解.
• 定义：与或图就是包含与节点和或节点 的图，即存在超弧的图，也称为超图. • 超图与状态空间图有什么区别？ 与或图是一种更一般的图. • 定义：一超弧所相关的边数（K）被称为 该超弧的度，实现的连接称为K-连接. • K—连接符：从一个父节点指向一组含有 K个后继节点的节点集.
Artificial Intelligence
Artificial Intelligence
• 问题: 假定我们已经会求矩形的面积，现在要求 如图所示的五边形的面积。 • 方法分析: 五边形的面积转化为矩形面积。
①
I 1
III ③
2 II
3
②
Artificial Intelligence
求解步骤：
① 求五边形面积 求 1面积 求 I面积 求 2面积 求 II面积 求 3面积 求 III面积 求• 面积 ③ I 1 2 II III ③ 3
②
求• 面积 ①
求• 面积 ②
Artificial Intelligence
小结:
• 问题归约法: 当问题复杂时，可把初始问题分解成若 干简单的子问题，若子问题仍复杂，可再进一步分解， 直到这些子问题的解可直接得到。这种问题的描述和 求解方法，称为~. • 本原问题: 可直接解答的问题称为~ ，它是不必证明 的、自然成立的. • 归约法的组成： 1）一个初始问题的描述； 2）一组把问题变成子问题的算子 (分解或转换)； 3） 一组本原问题的描述 • 不同的算子对应不同的关系,从而使问题归约的描述 可用一个与或图的结构来表示. Artificial Intelligence
7 S:={n}; 建立含 n 的节点集合S.（已扩展待修正） 8 Until S为空, do: 9 Begin (m为S中任一节点) 10 REMOVE(m, S),当 mc{S};（m→mc ,从底层开始修正） 11 修改 m 的耗散值 q(m): 对 m 指向节点集 (n1i， n2i, … nki) 的每一个连接符 i 分别计算qi, qi(m)=Ci+q(n1i)+…+q(nki), 并取 q(m):= min qi (m); 加(或修正)指针到 min qi (m) 的连接符上. IF M(nji, SOLVED) THEN M(m, SOLVED);（j=1，2，…， k）若该连接符的所有子节点都是能解的,则m也能解. 12 IF M(m, SOLVED) (q(m) q0(m)) THEN ADD(ma, S); m 能解或修正的耗散值与原先估算q0不同,则把m的所有先 辈节点ma添加到S中. （能解或修正向上传递） 13 end (与8匹配) 14 end (与2匹配) Artificial Intelligence
二次循环后 (5) n0 n2 4 (2) n5
n4 (1)
2
0 n8
n7 0
四次循环后
不带括号的数是启发函数h(n)值,带括号数是估价函数q（n）的修正值； 短箭头用来标记连接符，标明侯选局部解图；已经标注SOLVED的节点 用黑心圆来表示。
Artificial Intelligence
讨论
• 当节点n无后继节点? 在第11步中对 m (n)赋 一个高的 q 值(会传递到s), 从而排除了含有 n的子图被当作候选局部解图的可能性. • 在 G’ 中存在多个非终节点时,选择什么样的 节点先扩展? 一般选择最能导致该局部解图耗 散值发生较大变化的节点先进行扩展, 可促使 及时修改局部解图的标记. • 同A算法类似,若 s→N 存在解图,当 h(n) ≤ h*(n)且h(n)满足单调限制条件时(对n到其子 节点的每一连接符均需要满足),则 AO* 一定 能找到最佳解图.
n0 n1 n2 n3 n5 n6
n7
与或图
• 在与或图中，节 点 n0 有两个连接 符：1-连接符指 n4 向节点 n1；2-连 接符指向节点集 合{n4、n5}； • 对于节点 n0 来讲， n1 可称为或节点， n8 n4、n5 可称为与 节点。
Artificial Intelligence
AO*搜索算法过程分析
• 两个过程的重复:
–自上而下的图生长过程（4-6步）: 先通过有标 记的连接符，找到目前为止最好的一个局部解 图，然后对其中一个非终节点进行扩展，并对 其后继节点赋估计耗散值和加能解标记. –自下而上的估价函数值的修正、连接符的标记 和SOLVED的标注过程(7-12): 耗散值的修正从 刚被扩展的节点n开始，其修正耗散值q(n)取所 有估计值中最小的一个，然后根据耗散值递归 计算公式逐级向上修正其先辈节点的耗散值.只 有下层节点耗散值修正后，才可能影响到上一 层节点的耗散值，如此一直修正到初始节点.
2 与或图
• 与节点：把单个问题分解为几个子问题来求解。只 有当所有子问题都有解，该父辈节点才有解。表示 一种 “与” 关系。 • 或节点：同一问题被转换为几种不同的后继问题。 只要有一个后继问题有解，则原问题有解。表示一 种 “或” 关系。
P P
R (a)
Q
R (b)
Q
• 与节点由与运算连接（超弧），如图（a）. Artificial Intelligence • 或节点由或运算连接，如图（b）.
Artificial Intelligence
n0 n1 h(n1)=2 n3 h(n3)=4
n2 h(n2)=4
n6 h(n6)=2
n7 h(n7)=0
• 例: 各节点启发值如 图，k-连接符的耗散值 = k, 求最佳解图. • 应用 AO* 算法，经 n4 四个循环，可找到解图. h(n4)=1 n5 • 在第一次循环扩展节 h(n5)=1 点 n0；然后,依次扩展 节点 n1、n5、n4。 • 在节点 n4 被扩展之 n8 后，节点 n0 便被标注 h(n8)=0 SOLVED，此时，通过向 下跟踪有标记的连接符， 便获得了解图. Artificial Intelligence
Artificial Intelligence
• 定义：不能解节点的递归定义为:
1．没有后裔的非终节点是不能解的节点； 2．若非终节点有 “或” 子节点时，当且仅 当所有子节点均不能解时，该非终节点才不 能解； 3．若非终节点有 “与” 子节点时，当至少 有一子节点不能解时，该非终节点才不能解.
Artificial Intelligence
3 与或图搜索
• 含义：在与或图上执行搜索的过程，其目的在于标明 起始节点是有解的，即，搜索不是去寻找到目标节点 的一条路径，而是寻找一个解图。 • 定义：一个节点被称为能解节点，其递归定义为： 1．终节点是能解节点（直接与本原问题相关联）； 2．若非终节点 有 “或” 子节点时，当且仅当其子 节点至少有一个能解 ，该非终节点才能解； 3．若非终节点有 “与” 子节点时，当且仅当其子 节点均能解，该非终节点才能解。