7图搜索基础.ppt

Cute
Uintage style
7图搜索基础
Add your text here and write down your opninon thank you add your text here
U
i
n
t
a
V4
V8
V1
V2
V3
V5
V4
V7
V6
V8
图的遍历之广度优先遍历(BFS)
14
方法：首先访问指定的起始顶点，然后在与该顶点邻接的顶点中选择一个未被访问的顶点进行访问，接着再从现在访问的顶点的 邻接顶点中任意选择一个未被访问的顶点进行访问，如此继续，若 到达无未被访问的邻接顶点的顶点时，则退回到最近访问过的那 个顶点，若它还有未被访问的邻接顶点，则选择一个进行访问。重复上述过程，直到全部顶点都访问完毕 。
例：
V1
V1
V2
V4
V5
V3
V7
V6
V8
深度优先遍历：
V2
V4
V8
V5
V3
V6
V7
V1
V2
V5
V8
V4
V3
V6
V7
V1
V2
V4
V8
V5
V3
V7
V6
V1
V2
V5
V8
V4
V3
V7
V6
V1
V3
V6
V7
V2
V4
V8
V5
图的遍历之深度优先遍历(DFS)
15
2 显式图&隐式图
在路径问题、连通性问题和网络优化等问题中，图的结构是显式给出的，包括图中的顶点、边及权重，这类图称为显式图，即一般意义上的图。
隐式图是由问题的初始结点，为了求解或求证问题，根据问题的规则(一般是由题目的意思隐含给出的)，也就是生成子结点的约束条件，逐步扩展结点，直至得到目标结点为止的一个隐式的图。
两种典型的隐式图：子集树，排列树
16
2 显式图&隐式图-子集树
当要求解的问题需要在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)。
17
2 显式图&隐式图-子集树
共2n 个状态。若表示为树形结构就是一棵有2n个叶结点的二叉树，对树中所有分支进行遍历的算法都必须耗时O(2n)
18
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! )
19
2 显式图&隐式图-排列树
20
3 图搜索术语&方法分类
穷举搜索（盲目搜索）是对图的最基本的搜索算法，是蛮力策略的一种表现形式。即不考虑给定问题的特有性质，按事先定好的顺序，依次运用规则，盲目搜索的方法。
启发式搜索是利用一些启发信息，提前判断出先搜索哪些状态可能尽快找到问题的解或某些情况不可能取到最优解，从而可以提前舍弃对这些状态的尝试。即考虑给定问题的特有性质，选用合适的细则，提高搜索的效率。
搜索分为两大类：
隐含地检查所有可能情况
21
3 图搜索术语&方法分类
问题状态:树中的每一个结点确定所求解问题的一个问题状态。
状态空间:由根结点到其它结点的所有路径（分支），就确定了这个问题的状态空间。
解状态:是这样一些问题状态S，对于这些问题状态，由根到S的那条路径确定了该解空间中的一个元组。
答案状态:是这样一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这问题的一个解（即它满足隐式约束条件）。
状态空间树:解空间的树结构，又称隐式图。
22
3 图搜索术语&方法分类
活结点：如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。
E-结点：当前正在生成其儿子结点的活结点叫E-结点（正在扩展的结点）。
死结点 ：不再进一步扩展或者其儿子结点已全部生成的结点就是死结点 。
23