第五章1 图的搜索算法
- 格式：ppt
- 大小：1.15 MB
- 文档页数：155
下载文档原格式
合集下载
人工智能[第五章状态空间搜索策略]山东大学期末考试知识点复习
![人工智能[第五章状态空间搜索策略]山东大学期末考试知识点复习](https://img.taocdn.com/s1/m/90a7eb54dd36a32d73758188.png)
第五章状态空间搜索策略搜索是人工智能的一个基本问题，是推理不可分割的一部分。
搜索是求解问题的一种方法，是根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线的过程。
搜索包含两层含义：一层含义是要找到从初始事实到问题最终答案的一条推理路线；另一层含义是找到的这条路线是时间和空间复杂度最小的求解路线。
搜索可分为盲目搜索和启发式搜索两种。
1．1 盲目搜索策略1．状态空间图的搜索策略为了利用搜索的方法求解问题，首先必须将被求解的问题用某种形式表示出来。
一般情况下，不同的知识表示对应着不同的求解方法。
状态空间表示法是一种用“状态”和“算符”表示问题的方法。
状态空间可由一个三元组表示(S，F，Sg)。
利用搜索方法求解问题的基本思想是：首先将问题的初始状态(即状态空间图中的初始节点)当作当前状态，选择一适当的算符作用于当前状态，生成一组后继状态(或称后继节点)，然后检查这组后继状态中有没有目标状态。
如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若没有，则按照某种控制策略从已生成的状态中再选一个状态作为当前状态，重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。
算法5．1 状态空间图的一般搜索算法①建立一个只含有初始节点S0的搜索图G，把S放入OPEN表中。
②建立CLOSED表，且置为空表。
③判断OPEN表是否为空表，若为空，则问题无解，退出。
④选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表中，将此节点记为节点n。
⑤考察节点n是否为目标节点，若是，则问题有解，并成功退出。
问题的解的这条路径得到。
即可从图G中沿着指针从n到S⑥扩展节点n生成一组不是n的祖先的后继节点，并将它们记作集合M，将M中的这些节点作为n的后继节点加入图G中。
⑦对那些未曾在G中出现过的(即未曾在OPEN表上或CLOSED表上出现过的)M中的节点，设置一个指向父节点(即节点n)的指针，并把这些节点加入OPEN 表中；对于已在G中出现过的M中的那些节点，确定是否需要修改指向父节点(n 节点)的指针；对于那些先前已在G中出现并且已在COLSED表中的M中的节点，确定是否需要修改通向它们后继节点的指针。
图搜索技术(穷举式)
如果从m1到t没有路径存在，算法则试探m2到t是 否存在路径，它同样也要试探m2的子状态到t有无路径 存在，等等。
所以，算法中循环和递归是交叉进行的，一方面 是“横向”探索，一方面是“纵向”探索。
更深入的问题： （1）深度问题 （2）死循环问题
解决办法： （1）限制深度：大概估计路径长度 （2）记录从初始到当前状态的路径
与此相对应的，将所有搜索过的状态都记录下来 的搜索方法称为"图搜索"，搜索过的路径除了可以重 复利用外，其最大的优点是可以更有效地利用与问题 有关的一些知识，从而达到启发式搜索的目的。
下面给出一般的图搜索算法（G表示图，s为初始节点， n为当前节点）：
① G:=(s), OPEN:=(s); CLOSED:=(); ② LOOP: IF OPEN＝(), THEN EXIT(FAIL)； ③ n:＝FIRST(OPEN), REMOVE (n, OPEN), ADD (n, CLOSED); ④ IF GOAL (n), THEN EXIT (SUCCESS); 由n返回到s路径上的指针,可给出
递归过程BACKTRACK（DATA） 其功能是：如果从当前状态DATA到目标状态有路 径存在，则返回以规则（操作）序列表示的从DATA到 目标状态的路径；如果从当前状态DATA到目标状态没 有路径存在，则返回FAIL。 变量符号DATA、RULES、R、RDATA、PATH分 别表示当前状态、规则集序列表、当前调用规则、新 生成状态、当前解路径表。常量符号NIL、FAIL、 LOOP分别表示空表、回溯点标记、循环标号。
递归过程BACKTRACK（DATALIST）
DATALIST：从初始到当前的状态表（逆向）
返回值：从当前状态到目标状态的路径或FAIL
所以，算法中循环和递归是交叉进行的，一方面 是“横向”探索，一方面是“纵向”探索。
更深入的问题： （1）深度问题 （2）死循环问题
解决办法： （1）限制深度：大概估计路径长度 （2）记录从初始到当前状态的路径
与此相对应的，将所有搜索过的状态都记录下来 的搜索方法称为"图搜索"，搜索过的路径除了可以重 复利用外，其最大的优点是可以更有效地利用与问题 有关的一些知识，从而达到启发式搜索的目的。
下面给出一般的图搜索算法（G表示图，s为初始节点， n为当前节点）：
① G:=(s), OPEN:=(s); CLOSED:=(); ② LOOP: IF OPEN＝(), THEN EXIT(FAIL)； ③ n:＝FIRST(OPEN), REMOVE (n, OPEN), ADD (n, CLOSED); ④ IF GOAL (n), THEN EXIT (SUCCESS); 由n返回到s路径上的指针,可给出
递归过程BACKTRACK（DATA） 其功能是：如果从当前状态DATA到目标状态有路 径存在，则返回以规则（操作）序列表示的从DATA到 目标状态的路径；如果从当前状态DATA到目标状态没 有路径存在，则返回FAIL。 变量符号DATA、RULES、R、RDATA、PATH分 别表示当前状态、规则集序列表、当前调用规则、新 生成状态、当前解路径表。常量符号NIL、FAIL、 LOOP分别表示空表、回溯点标记、循环标号。
递归过程BACKTRACK（DATALIST）
DATALIST：从初始到当前的状态表（逆向）
返回值：从当前状态到目标状态的路径或FAIL
图搜索策略
图搜索策略112----⎧⎪⎧⎪⎨⎪⎩⎪⎪⎧⎪⎪⎪⎪⎪⎨⎨⎪⎪⎪⎩⎪⎪⎪⎪⎪⎧⎪⎨⎪⎩⎩⎧⎪⎨⎪⎩一、图搜索概论：①，树的定义和基本术语，图的意义②，图的存储结构2，图的定义1，顶点,2，边,③，显示图的常用术图搜索回顾3，图,4，数据元素隐式图术语，子集树，，排列树二、状态图搜索：①，搜索定义②，搜索树定义广度优先盲目穷举式深度优先有界深度优先全局择优1，树式搜索局部择优分启发式状态图搜索③，搜索方式分类*--A --121*2 4A ⎧⎧⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎩⎩⎪⎧⎪⎧⎪⎨⎪⎪⎩⎪⎨⎪⎧⎪⎪⎨⎪⎪⎩⎩⎩⎧⎧⎧⎪⎪⎨⎨⎪⎩⎨⎪⎪⎩⎪⎩A Beam Search 支界限最近择优算法算法随机碰撞盲目回溯穷举2，线式搜索不回溯启发式可回溯深度优先搜索穷举式搜索，盲目搜索广度优先搜索④，搜索策略盲目碰撞搜索，启发式搜索，⑤搜搜寻算法，3，二分取中查索法找算法算， ⎧⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎩⎩Branch and bound1 2⎧⎨⎩⎧⎨⎩1，猴子与香蕉三，简单实例回顾：2，猴子与香蕉的状态空间图，图搜索一般过程四，图搜索过程，图搜索框过程框图五，通过文章加深图搜索策略（《人工智能图搜索策略的研究》）一，图搜索概论：①图搜索回顾：1.11.2②图的存储结构：1.11.2③图及其术语：1.11.2显示图与隐式图：1.3，显示图的常用术语：1.4隐式图术语二，状态图搜索：①，搜索定义，②，搜索树定义：③，搜索方式分类：④图搜索策略：1.1盲目式搜索：1.2启发式搜索：⑤图搜索算法1.1树搜索方法1.3树搜索举例1.4状态图搜索：1.5状态图搜索举例⑥，常见搜索算法下面是一些比较重要的算法，原文罗列了32个，但我觉得有很多是数论里的或是比较生僻的，和计算机的不相干，所以没有选取。
第一讲 图的搜索算法
算法框架
1．算法的基本思路 算法设计的基本步骤为：
1）确定图的存储方式； 2）图的遍历过程中的操作，其中包括为输 出问题解而进行的存储操作；
3）输出问题的结论。
dfs与bfs 深度搜索与广度搜索的相近，最终都要扩展 一个结点的所有子结点. 区别在于对扩展结点过程，深度搜索扩 展的是E-结点的邻接结点中的一个，并将其 作为新的E-结点继续扩展，当前E-结点仍为 活结点，待搜索完其子结点后，回溯到该结 点扩展它的其它未搜索的邻接结点。而广度 搜索，则是扩展E-结点的所有邻接结点，E结点就成为一个死结点。
或改造，加入了一定的“智能因素”，使搜索能尽快接近目标结点，减少了在空间和 时间上的复杂度。 )
二、分支定界 三、A*算法 第三部分 搜索与动态规划的结合 （包括与其他算法的联系和对比）
初级的图搜索算法
• 包括 深度优先遍历,广度优先遍历和双向广度优先遍历 • 图的两种遍历算法：深度优先搜索和广度优先搜索算法 • BFS是一种盲目搜寻法，目的是系统地展开并检查图中 的所有节点，以找寻结果。换句话说，它并不考虑结果 的可能位址，彻底地搜索整张图，直到找到结果为止。 BFS并不使用经验法则算法。
广度优先搜索的应用
【例1】已知若干个城市的地图，求从一个 城市到另一个城市的路径，要求路径中经过的 城市最少 【例2】走迷宫问题
·
【例1】已知若干个城市的地图，求从一个城市到 另一个城市的路径，要求路径中经过的城市最少。
算法设计：
图的广度优先搜索类似与树的层次遍 历，逐层搜索正好可以尽快找到一个结点 与另一个结点相对而言最直接的路径。
如图5-6表示的是从城市A到城市H的交通图。从图中可 以看出，从城市A到城市H要经过若干个城市。现要找出一条 经过城市最少一条路线。 (提示：看到这图很容易想到用邻接距阵来表示，0
第五章5 图的搜索算法
MaxLoading(c1); if (s- bestw <=c2); {print(“The first ship loading”, bestw，“chose：”); for(i=1;i<=n;i++) if(bestx[i]=1) print(i，“，”); print(“换行符 The second ship loading”, s -bestw,“chose”); for(i=1;i<=n;i++) if(bestx[i]=1) print(i,”,”); } else print(“no solution”); }
其实看了下面的例子大家会发现，优先队列式扩展结点的过程，一 开始实际是在进行类似“深度优先”的搜索。 例如：W={10，30，50}，C1=60， 所构成的解状态空间树如下图 所表示：
根据这个实例，我们一起来看一下FIFO限界搜索过程和 LC-搜索的过程
FIFO限界搜索过程为：
1） 初始队列中只有结点A； 2） 结点A变为E-结点扩充B入队，bestw=10； 结点C的装载上界为30+50=80> bestw，也入队； 3） 结点B变为E-结点扩充D入队，bestw=40； 结点E的装载上界为60> bestw，也入队； 4） 结点C变为E-结点扩充F入队，bestw仍为40； 结点G的装载上界为50> bestw，也入队； 5） 结点D变为E-结点，叶结点H超过容量， 叶结点I的装载为40，bestw仍为40；
5） 结点C变为E-结点扩充F入堆，bestw仍为40；
LC-搜索的过程如下：
1）
2）
初始队列中只有结点A；
结点A变为E-结点扩充B入堆，bestw=10；结点C的装载上界
图的遍历和搜索
INPUT.TXT 123456789 3 OUTPUT.TXT 192 384 576 219 438 657 273 546 819 327 654 981
用数组B[0..9]来存储N个数字 存储规则: B[0]存储N个数字中0的个数 B[1]存储N个数字中1的个数 B[2]存储N个数字中2的个数 ………… ………… B[8]存储N个数字中8的个数 B[9]存储N个数字中9的个数
2 1
1 2
设置8个方向变化 初始化board Board[1,1] try(1,1,2,q) q 1
Y
N
输出结果
输出无解信息
K Try(x,y,i,q)
表示对(x,y)位置 作为第i步向前试探 的过程.若试探成 功,逻辑变量q的值 为true,否则为false
0 k←k+1 q1←false u←x+a[1,k] v←y+a[2,k] 合格 Y N Board=0 N Y Board[u,v] ←i i<n*n N
1 3 7 9 0 8 2 6 4 5
For I:=1 to 3 For j:=4 to 9 For k:=11 to 31 For p:=32 to 99
求I*i ,分离各位数字 求j*j ,分离各位数字 求k*k, 分离各位数字 求p*p , 分离各位数字
Y Try(u,v,i+1,q1) Q1:=true Not (q1) N Y Board[u,v]:=0 Q1 OR (K=8) Q:=Q1
试编程将1至N(N≤10)的自然数序列1,2,…, N重新排列,使任意相邻两数之和为素数.例如N =3时有两种排列方案123,321满足要求. 输入要求:N从键盘输入. 输出要求:每行输出一种排列方案(相邻数字之间 用空格分隔). 最后一行输出排列方案总数. 例如输入 3 输出 1 2 3 3 2 1 2
图搜索基础课件
树的定义和基本术语
定义：
树 (Tree) 是 n (n≥0) 个结点的有限集。若 n = 0，称 为空树；若 n > 0，则它满足如下两个条件： (1) 有且仅有一个特定的称为根 (Root) 的结点； (2) 其余结点可分为 m (m≥0) 个互不相交的有限集 T1, T2,
T3, …, Tm，其中每一个集合本身又是一棵树，并称为 根的子树 (SubTree)。
➢ 无向图中顶点vi的度 TD(vi) 是邻接矩阵中第i行1的个数。
➢ 有向图中 顶点vi的出度是邻接矩阵中第i行1的个数。 顶点vi的入度是邻接矩阵中第i列1的个数。
13
第14页/共84页
网的邻接矩阵可定义为：
Ai,
j
wij： 若(vi , v j ) 或
vi , v j
是 VR中的边或弧
：若(vi , v j ) 或 vi , v j 不是VR中的边或弧
对于一个具有n个顶点的图，可用两个数组存储。其中一 个一维数组存储数据元素(顶点)的信息，另一个二维数组(图 的邻接矩阵)存储数据元素之间的关系(边或弧)信息。
邻接矩阵：设 G = (V, {VR}) 是具有 n 个顶点的图，顶 点的顺序依次为 {v1, v2, …, vn}，则 G 的邻接矩阵是具有如 下性质的 n 阶方阵：
树的深度：树中结点的最大层次。
树
森林
有序树一：棵树树中可结以点看的成各是子一树个从特左殊至的右森有林次。序(最左边的不为一第定一是个孩子)。
无序树给：森树林中中结的点各的子各树子树加无上次一序个。双亲结点，森林就变成了树。
2
第3页/共84页
图的定义和基本术语
定义：
图 (Graph) 是一种复杂的非线性数据结构，由顶 点集合及顶点间的关系(也称弧或边)集合组成。可 以表示为： G＝(V, {VR}) 其中 V 是顶点的有穷非空集合； VR 是顶点之间关系 的有穷集合，也叫做弧或边集合。弧是顶点的有序对， 边是顶点的无序对。
定义：
树 (Tree) 是 n (n≥0) 个结点的有限集。若 n = 0，称 为空树；若 n > 0，则它满足如下两个条件： (1) 有且仅有一个特定的称为根 (Root) 的结点； (2) 其余结点可分为 m (m≥0) 个互不相交的有限集 T1, T2,
T3, …, Tm，其中每一个集合本身又是一棵树，并称为 根的子树 (SubTree)。
➢ 无向图中顶点vi的度 TD(vi) 是邻接矩阵中第i行1的个数。
➢ 有向图中 顶点vi的出度是邻接矩阵中第i行1的个数。 顶点vi的入度是邻接矩阵中第i列1的个数。
13
第14页/共84页
网的邻接矩阵可定义为：
Ai,
j
wij： 若(vi , v j ) 或
vi , v j
是 VR中的边或弧
：若(vi , v j ) 或 vi , v j 不是VR中的边或弧
对于一个具有n个顶点的图，可用两个数组存储。其中一 个一维数组存储数据元素(顶点)的信息，另一个二维数组(图 的邻接矩阵)存储数据元素之间的关系(边或弧)信息。
邻接矩阵：设 G = (V, {VR}) 是具有 n 个顶点的图，顶 点的顺序依次为 {v1, v2, …, vn}，则 G 的邻接矩阵是具有如 下性质的 n 阶方阵：
树的深度：树中结点的最大层次。
树
森林
有序树一：棵树树中可结以点看的成各是子一树个从特左殊至的右森有林次。序(最左边的不为一第定一是个孩子)。
无序树给：森树林中中结的点各的子各树子树加无上次一序个。双亲结点，森林就变成了树。
2
第3页/共84页
图的定义和基本术语
定义：
图 (Graph) 是一种复杂的非线性数据结构，由顶 点集合及顶点间的关系(也称弧或边)集合组成。可 以表示为： G＝(V, {VR}) 其中 V 是顶点的有穷非空集合； VR 是顶点之间关系 的有穷集合，也叫做弧或边集合。弧是顶点的有序对， 边是顶点的无序对。
第五讲 图的基本搜索算法及应用_369305440
20
22.2 最短路径
我们要证明对每个顶点v ∈V，BFS过程算 出的d[v]= δ(s, v) 。下面我们首先证明d[v] 是δ(s, v) 的上界。 引理22.2 设G=(V,E)是一个有向图或无向 图，并假设算法BFS从G中一已知源节点 s∈V开始执行，在执行终止时，对每个顶 点v∈V，变量d[v]的值满足d[v] ≥ δ(s, v)。
22.2 广度优先搜索(BFS)
在最小生成树（第23章）和单源最短路径（第24章） 中用到了广度优先搜索类似（队列/扩张）的思想/方 法。 已知图G=(V,E)和一个源顶点s，广度优先搜索系统 地探寻G的边，从而“发现”s所能到达的所有顶点， 并计算s到所有这些顶点的距离(最少边数)。 该算法同时能生成一棵根为s且包括所有可达顶点的 广度优先树。 对从s可达的任意顶点v，广度优先树中从s到v的路径 对应于图G中从s到v的最短路径，即包含最小边数的 路径。该算法对有向图和无向图同样适用。 算法自始至终通过已找到和末找到顶点之间的边界向 外扩展
引理22.1 设G=(V,E)是一个有向图或无向 图，s∈V为G的任意一个结点，则对任意 边(u,v)∈E,有 δ(s, v) ≤ δ(s, u) + 1 证明：
如果从顶点s可达顶点u，则从s也可达v。在这 种情况下从s到v的最短路径不可能比从s到u的 最短路径加上边(u,v)更长，因此不等式成立； 如果从s不可达顶点u，则δ(s, u)=∞，不等式仍 然成立。
若(u,v)∈E且顶点u为黑色，那么顶点v要么是灰色，要 么是黑色，就是说，与黑色顶点邻接的所有顶点都是已 被发现的。 灰色顶点可以与一些白色顶点相邻接，它们代表着已发 现和未发现顶点之间的边界。
13
22.2 广度优先树
在广度优先搜索过程中建立了一棵广度优先树。 起始时只包含根节点，即源顶点s。在扫描某个已 发现顶点u的邻接表的过程中，每当发现一个白色 顶点v，该顶点v及边(u,v)就被添加到树中。 在广度优先树中，称结点u是结点v的先辈或父母 结点。因为一个结点至多只能被发现一次，因此 它最多只能有一个父母结点 祖先和后裔关系的定义和通常一样：如果u处于树 中从根s到结点v的路径中，那么u称为v的祖先，v 是u的后裔。
22.2 最短路径
我们要证明对每个顶点v ∈V，BFS过程算 出的d[v]= δ(s, v) 。下面我们首先证明d[v] 是δ(s, v) 的上界。 引理22.2 设G=(V,E)是一个有向图或无向 图，并假设算法BFS从G中一已知源节点 s∈V开始执行，在执行终止时，对每个顶 点v∈V，变量d[v]的值满足d[v] ≥ δ(s, v)。
22.2 广度优先搜索(BFS)
在最小生成树（第23章）和单源最短路径（第24章） 中用到了广度优先搜索类似（队列/扩张）的思想/方 法。 已知图G=(V,E)和一个源顶点s，广度优先搜索系统 地探寻G的边，从而“发现”s所能到达的所有顶点， 并计算s到所有这些顶点的距离(最少边数)。 该算法同时能生成一棵根为s且包括所有可达顶点的 广度优先树。 对从s可达的任意顶点v，广度优先树中从s到v的路径 对应于图G中从s到v的最短路径，即包含最小边数的 路径。该算法对有向图和无向图同样适用。 算法自始至终通过已找到和末找到顶点之间的边界向 外扩展
引理22.1 设G=(V,E)是一个有向图或无向 图，s∈V为G的任意一个结点，则对任意 边(u,v)∈E,有 δ(s, v) ≤ δ(s, u) + 1 证明：
如果从顶点s可达顶点u，则从s也可达v。在这 种情况下从s到v的最短路径不可能比从s到u的 最短路径加上边(u,v)更长，因此不等式成立； 如果从s不可达顶点u，则δ(s, u)=∞，不等式仍 然成立。
若(u,v)∈E且顶点u为黑色，那么顶点v要么是灰色，要 么是黑色，就是说，与黑色顶点邻接的所有顶点都是已 被发现的。 灰色顶点可以与一些白色顶点相邻接，它们代表着已发 现和未发现顶点之间的边界。
13
22.2 广度优先树
在广度优先搜索过程中建立了一棵广度优先树。 起始时只包含根节点，即源顶点s。在扫描某个已 发现顶点u的邻接表的过程中，每当发现一个白色 顶点v，该顶点v及边(u,v)就被添加到树中。 在广度优先树中，称结点u是结点v的先辈或父母 结点。因为一个结点至多只能被发现一次，因此 它最多只能有一个父母结点 祖先和后裔关系的定义和通常一样：如果u处于树 中从根s到结点v的路径中，那么u称为v的祖先，v 是u的后裔。
第5章 搜索与回溯算法(C 版)
【参考程序】
#include<cstdio> #include<iostream> #include<cstdlib> using namespace std; int a[10001]={1},n,total; int search(int,int); int print(int); int main() {
int print();
//输出方案
int main() {
cout<<"input n,r:"; cin>>n>>r; search(1); cout<<"number="<<num<<endl; }
//输出方案总数
int search(int k) {
int i; for (i=1;i<=n;i++) if (!b[i])
（r<n），试列出所有的排列。
#include<cstdio>
#include<iostream>
#include<iomanip>
using namespace std;
int num=0,a[10001]={0},n,r;
bool b[10001]={0};
int search(int);
//回溯过程
{
for (int j=0;j<=3;j++)
//往4个方向跳
if (a[i-1][1]+x[j]>=0&&a[i-1][1]+x[j]<=4
&&a[i-1][2]+y[j]>=0&&a[i-1][2]+y[j]<=8)//判断马不越界
图搜索—图搜索策略ppt课件
失败
扩展n，把n的后继节点放入OPEN 表的末端，提供返回节点n的指针
是否有后继节点 为目标节点？
是 成功
否 图3.2 宽度优先算法框图
思考：与原始算法比较异同，宽度优先的体现？
14
3.2 盲目搜索
例子 八数码难题（8-puzzle problem）
28 3
1
4
76 5
（初始状态）
12 3
8
4
76 5
❖各自特点：重排OPEN表的依据不同。
❖盲目搜索可能带来组合爆炸。
启发式信息：用来加速搜索过程的问题领域信息，一般与有关问题
具体领域背景有关，不一定具有通用性。
启发式搜索：利用启发式信息的搜索方法
– 特点：重排OPEN表，选择最有希望的节点加以扩展
– 种类：有序搜索、A*算法等
24
3.3 启发式搜索
失败
节点n的深度等于最大深度？ 否
扩展n，把n的后继节点放入OPEN 表的前端，提供返回节点n的指针
是否有后继节点 为目标节点？
是 成功
否
图3.6 深度优先算法框图
19
3.2 盲目搜索
示范：有界深度(4)优先的八数码问题深度优先 搜索树？
28 3
1
4
76 5
（初始状态）
12 3
8
4
76 5
（目标状态）
是依据f(x)=g(x)+h(x)进行的，则称该过程为A算法。
– 定义2 在A算法中，如果对所有的x存在h(x)≤h*(x),则称h(x)
为h*(x)的下界，它表示某种偏于保守的估计。
– 定义3 采用h*(x)的下界h(x)为启发函数的A算法，称为A*算 法。当h=0时，A*算法就变为等代价搜索算法。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
上一页·
下一页·
返回首页
5．1．1 图及其术语
1．显式图与隐式图
在路径问题、连通性问题、可平面性检验、着色 问题和网络优化等问题中，图的结构是显式给出的， 包括图中的顶点、边及权重，这类图我们称为显式图， 也就是一般意义上的图。 隐式图是由问题的初始结点，为了求解或求证 问题，根据题目的规则（一般是由题目的意思隐含 给出的），也就是生成子结点的约束条件，逐步扩 展结点，直到得到目标结点为止的一个隐式的图。
图5-3
n=3的子集树
上一页·
下一页·
返回首页
2）排列树
当要求解的问题需要在n 元素的排列中搜索问题的解时， 解空间树被称作排列树（permutation tree）。 搜索空间为： （1，2，3，„„，n-1，n）, （2，1，3，„„，n-1，n）,
（2，3，1，„„，n-1，n）,（2，3，4，1，„„，n-1，n）, （n，n-1，„„，3，2，1） 第一个元素有n 种选择，第二个元素有n-1种选择，第三个 元素有n-2种选择，……，第n个元素有1种选择，共计n!个状态。 若表示为树形就是一个n度树，这样的树有n! 个叶结点，所以每 一个遍历树中所有节点的算法都必须耗时O(n! )
连通图：对于图中任意两个顶点 v i、 v j ∈V， v i、 v j之间有 道路相连，则称该图为连通图。如 5-1中的 ⑴图。
网络：带权的连通图，如图 5-2所示。
3．隐式图术语
1）子集树
当要求解的问题需要是在n 个元素的子集中进行搜索，其搜 索空间树被称作子集树（subset tree）。这n个元素都有在子 集中或被选取记为1，不在子集中或被舍去记为0，这样搜索空 间为： （0，0，„„，0，0），（0，0，„„，0，1）， （0，0，„„，1，0），（0，0，„„，1，1）， „„（1，1，„„，1，1）。 共2n 个状态。若表示为树形结构就是一棵有2n个叶结点的二叉 树，对树中所有分支进行遍历的算法都必须耗时O（2n）。 上一页· 下一页· 返回首页
2）邻接矩阵表示的图的广度优先搜索算法 bfsm(int k, graph g[][100]，int n) {int i，j； CirQueue Q； InitQueue(Q)； print ("visit vertex"， k)； /访问源点vk/ visited[k]=1； EnQueue(Q，k)； while(not QueueEmpty(Q)) {i=DeQueue(Q)； /vi出队/ for(j=0;j<G->n;j++) /扩展结点/ if(g[i][j]==1 and visited[j]=0) {print("visit vertex"，j)； visited[j]=1； EnQueue(Q，j)；} /访问过的vj人队/ } } 上一页· 下一页· 返回首页·
上一页·
下一页·
返回首页
2．相关概念和术语
问题状态:树中的每一个结点确定所求解问题的一个问题状态。 状态空间:由根结点到其它结点的所有路径（分支），就确定
了这个问题的状态空间。 解状态:是这样一些问题状态S，对于这些问题状态，由根到S 的那条路径确定了这解空间中的一个元组。 答案状态:是这样的一些解状态S，对于这些解状态而言，由 根到S的这条路径确定了这问题的一个解 状态空间树:解空间的树结构又称隐式图。
论”；其中的计算问题包括图的搜索、路径问题、连通性问题、
可平面性检验、着色问题、网络优化等。图论中的著名算法有： 求最小生成树的Kruskal算法、求最短路径的Dijkstra算法
和Floyd算法、求二部图最大匹配（指派问题）的匈牙利算法、
求一般图最大匹配的Edmonds“花”算法、求网络最大流和最 小割的算法等。其中的一些算法在数据结构课程中已经学习过 了。
1）邻接表表示图的广度优先搜索算法
int visited[n]; /n 为结点个数/ bfs(int k,graph head[]) {int i； queue Q ； edgenode *p； /定义队列/ InitQueue(Q)； /队列初始化/ print(“visit vertex”，k)； / 访问源点vk/ visited[k]=1； EnQueue(Q，k)； /vk已访问，将其入队。/ while(!QueueEmpty(Q)) /队非空则执行/ { i=DeQueue(Q)； / vi出队为E-结点/ p=head[i].firstedge； /取vi的边表头指针/ while(p<>null) /扩展E-结点 / {if(visited[p->adjvex]=0) /若vj未访问过/ { print (“visitvertex”，p->adjvex)；/访问vj/ visited[p->adjvex]=1； EnQueue(Q，p->adjvex)；} /访问过的vj人队/ p=p->next ； } /找vi的下一邻接点/ }
5．2．2 广度优先搜索的应用
【例1】已知若干个城市的地图，求从一个 城市到另一个城市的路径，要求路径中经过的 城市最少 【例2】走迷宫问题
上一页·
下一页·
返回首页·
【例1】已知若干个城市的地图，求从一个城市到 另一个城市的路径，要求路径中经过的城市最少。
算法设计：
图的广度优先搜索类似与树的层次遍 历，逐层搜索正好可以尽快找到一个结点 与另一个结点相对而言最直接的路径。
上一页·
下一页·
返回首页
图 (比如表示长度、流量或其他 )，则称其为带权图 。
带权图：j即图5 -2给图 5-1中各图的边上附加一个代表性数据 环 (cycle)：图5-1中 ⑶图中的 v 1点本身也有边相连，这种边 称为环。 有限图：顶点与边数均为有限的图，如图 5-1中的三个图均属 于有限图。 简单图：没有环且每两个顶点间最多只有一条边相连的图，如 图 5-1中的 ⑴图。 邻接与关联：当（ v 1， v 2） ∈E，或 <v 1， v 2 >∈E，即 v 1， v 2间有边相连时，则称 v 1和 v 2是相邻的，它们互为邻 接点（ adjacent），同时称（ v 1， v 2）或 <v 1， v 2 >是与 顶点 v 1、 v 2相关联的边。
上一页·
下一页·
返回首页·
活结点：如果已生成一个结点而它的所有儿子结点还没有 全部生成，则这个结点叫做活结点。
E-结点：当前正在生成其儿子结点的活结点叫E-结点（正 扩展的结点）。 死结点 ：不再进一步扩展或者其儿子结点已全部生成的生 成结点就是死结点 。
5．2．1 算法框架
1．算法的基本思路 算法设计的基本步骤为：
若G是网络，则邻接矩阵可定义为：
A[i,j]=Wij 若（Vi,Vj)或<Vi,Vj>属于E(G); A[i,j]=0或∞ 若（Vi,Vj）或<Vi,Vj> 不属于E(G); 其中，Wij表示边上的权值，∞表示一个计算机允许的，大于 所有边上权值的数； 上一页· 下一页· 返回首页·
上一页·
下一页·
2.显式图的常用术语
v1 v4 v1 v2 v2 v1 v2
⑴
v4 v5
v1 4 3 v2 2 9 6
v4
v3
v3
v3
⑵
v4
⑶
v3
图 5-1
图 5-2
如图5-1所示的 ⑴， ⑵， ⑶均为显式图 (Graph)。图 中的这些点(v1,v2,…,vn)被称为顶点 (vertex)或结点，连 接顶点的曲线或直线称为边 (edge)。 通常将这种由若干个顶点以及连接某些顶点的边所组 成的图形称为图，顶点通常被称作是图中的数据元素 .
1）确定图的存储方式； 2）图的遍历过程中的操作，其中包括为输 出问题解而进行的存储操作；
3）输出问题的结论。
ห้องสมุดไป่ตู้上一页·
下一页·
返回首页
2．算法框架
从广度优先搜索定义可以看出活结点的扩展是按先来先处 理的原则进行的，所以在算法中要用“队”来存储每个E-结点 扩展出的活结点。为了算法的简洁，抽象地定义： queue为队列类型， InitQueue( ) 为队列初始化函数， EnQueue(Q，k)为入队函数， QueueEmpty(Q) 为判断队空函数， DeQueue(Q) 为出队函数。 实际应用中，用数组或链表实现队列。 开辟数组visited记录visited结点的搜索情况。 在算法框架中以输出结点值表示“访问”。 上一页· 下一页· 返回首页· 例1·
上一页· 下一页· 返回首页· 例1·
图7.1
图5-5
图5-1中（1）图的邻接表
上一页·
下一页·
返回首页·
5．1．2 图搜索及其术语
1．穷举搜索与启发式搜索
穷举搜索是对图的最基本的搜索算法，是蛮力策略的一种 表现形式。即不考虑给定问题的特有性质，按事先定好的顺序， 依次运用规则，盲目搜索的方法。 启发式搜索是利用一些启发信息，提前判断出先搜索哪些 状态可能尽快找到问题的解或某些情况不可能取到最优解，从 而可以提前舍弃对这些状态的尝试。即考虑给定问题的特有性 质，选用合适的细则，提高搜索的效率。
返回首页·
2）邻接表
对于图G中的每个结点Vi, 把所有邻接于Vi的顶点Vj链成一个 单链表，这个单链表就称为顶点Vi的邻接表。 邻接表由边表和顶点两部分组成。 边表为一个单链表，每个表结点均有两个域： ① 邻 接 点 域 adjvex ， 存 放 与 vi 相 邻 接 的 顶 点 vj 的 序 号 j 。 ② 链 域 next ， 将 邻 接 表 的 所 有 表 结 点 链 在 一 起 。 顶 点 表 为 一 数 组 ， 每 个 元 素 均 有 两 个 域 ： ① 顶 点 域 vertex ， 存 放 顶 点 vi 的 信 息 ② 指针域firstedge， vi的边表的头指针。 对于无向图来说，Vi的邻接表中每个表结点都对应于与Vi相 关联的一条边， 对于有向图来说，Vi的邻接表中每个表结点对应于Vi为始点 射出的一条边。