5 DFS.ppt

5 DFS及回溯法
1
学习要点
复习图的广度优先算法
理解回溯法的深度优先搜索策略。
掌握用回溯法解题的算法框架
(1)递归回溯
(2)迭代回溯
(3)子集树算法框架
(4)排列树算法框架
通过应用范例学习回溯法的设计策略。
(1)装载问题;(2)批处理作业调度;(3)符号三角形问题
(4)n后问题;(5)0-1背包问题; (6)图的m着色问题
(7)旅行售货员问题
回溯法
2
深度优先搜索DFS ( Depth First Search )
深度优先搜索的示例
3
DFS 在访问图中某一起始顶点 v 后,由 v 出发,访问它的任一邻接顶点 w1;再从 w1 出发,访问与 w1邻接但还没有访问过的顶点 w2;然后再从 w2 出发,进行类似的访问,…如此进行下去,直至到达所有的邻接顶点都被访问过的顶点 u 为止。接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。
4
图的深度优先搜索算法
template<class NameType, class DistType>
void Graph <NameType, DistType> :: DFS ( ) {
int * visited = new int [NumVertices];
for ( int i = 0; i < NumVertices; i++ )
visited [i] = 0; //访问标记数组 visited 初始化
DFS (0, visited );
delete [ ] visited; //释放 visited
}
template<class NameType, class DistType>
void Graph<NameType, DistType> ::
DFS ( const int v, int visited [ ] ) {
5
cout << GetValue (v) << ‘’; //访问顶点 v
visited[v] = 1; //顶点 v 作访问标记
int w = GetFirstNeighbor (v);
//取 v 的第一个邻接顶点 w
while ( w != -1 ) { //若邻接顶点 w 存在
if ( !visited[w] ) DFS ( w, visited );
//若顶点 w 未访问过, 递归访问顶点 w
w = GetNextNeighbor ( v, w );
//取顶点 v 的排在 w 后面的下一个邻接顶点
}
}
6
算法分析
图中有 n 个顶点,e 条边。
如果用邻接表表示图,沿 Firstout  link 链可以找到某个顶点 v 的所有邻接顶点 w。由于总共有 2e 个边结点,所以扫描边的时间为O(e)。而且对所有顶点递归访问1次,所以遍历图的时间复杂性为O(n+e)。
如果用邻接矩阵表示图,则查找每一个顶点的所有的边,所需时间为O(n),则遍历图中所有的顶点所需的时间为O(n2)。
7
有许多问题,当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时,往往要使用回溯法。
回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。
回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。
回溯法
8
问题的解空间
问题的解向量:回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。
显约束:对分量xi的取值限定。
隐约束:为满足问题的解而对不同分量之间施加的约束。
解空间:对于问题的一个实例,解向量满足显式约束条件的所有多元组,构成了该实例的一个解空间。
注意:同一个问题可以有多种表示,有些表示方法更简单,所需表示的状态空间更小(存储量少,搜索方法简单)。
n=3时的0-1背包问题用完全二叉树表示的解空间
9
生成问题状态的基本方法
扩展结点: 一个正在产生儿子的结点称为扩展结点
活结点: 一个自身已生成但其儿子还没有全部生成的节点称做活结点
死结点: 一个所有儿子已经产生的结点称做死结点
深度优先的问题状态生成法:如果对一个扩展结点R,一旦产生了它的一个儿子C,就把C当做新的扩展结点。在完成对子树C(以C为根的子树)的穷尽搜索之后,将R重新变成扩