资源描述：
《【精品】DFS讲义(基础)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、回溯及深度优先搜索内容提要：图的概述、搜索概述、回溯算法、深度优先搜索、搜索的剪枝预备知识1、图的概念1736年瑞士数学家欧拉(Euler)发表了图论的第一篇论文“哥尼斯堡七桥问题”。在当时的哥尼斯堡城有一条横贯全市的普雷格尔河，河中的两个岛与两岸用七座桥联结起來，见图(1)。当吋那里的居民热衷于一个难题：游人怎样不重复地走遍七桥，最后回到岀发点。为了解决这个问题，欧拉用A,B,C,D4个字母代替陆地，作为4个顶点，将联结两块陆地的桥用相应的线段表示，如图(2),于是哥尼斯堡七桥问题就变成了图(2)屮，是否存在经过每条边一次且仅一次，经过所有的顶点
2、的冋路问题了。欧拉在论文小指出，这样的冋路是不存在的。图町以定义为6=(V,E),其中V是顶点的非空集合，E是边的集合；一般用(Vx,Vy)表示边，其中Vx,VyeVo根据边和顶点的不同特也图可以分为有向图、无向图、带权图等。CD图的遍历：即从某个顶点出发，依次访问每个顶点一次。【例题】两只蚂蚁比赛问题。两只蚂蚁甲、乙分别处在图G中的顶点a,b处,并设图中各边长度相等。甲提出同乙比赛：从它们所在顶点出发，走过图中所有边最后到达顶点c处。如果它们速度相同，问谁最先到达目的地？2、树的概念树形结构是结点z间有分支，并具有层次关系的结构，它非常类似于占然
3、界屮的树。树结构在客观世界中是人量存在的，例如家谱、行政组织机构都可用树形象地表示。緊删菠兗条屈张体张f#5RT探华张輔以上表示很像一棵倒画的树。其中“树根”是张源，树的“分支点”是张明、张亮和张平，该家族的其余成员均是”树叶”，而树枝（即图屮的线段）则描述了家族成员之间的关系。显然，以张源为根的树是一个人家庭。它可以分成张明、张亮和张丽为根的三个小家庭；每个小家庭乂都是一个树形结构。树可以用树形图、恢套集合、I叫入表等方式表示。其中树形图表示是树结构的主耍表示方法：结点用圆圈表示，结点的名字写在圆圈旁边（有时亦可写在圆圈内）。旳形诞军轮树中某个结
4、点的子树Z根称为该结点的孩子(Child)或儿子，相应地，该结点称为孩子的双亲(Parents)或父亲。树结点的层数(Level)从根起算：根的层数为1,其余结点的层数等于其双亲结点的层数加1。(注：很多文献小将树根的层数泄义为0。)双亲在同一层的结点互为堂兄弟。树中结点的最大层数称为树的高度(Height)或深度(Depth)。3、树和图的关系树是一种特殊的图。所冇棊于图的算法均町直接应用到树中，但往往不是一定是最高效的，树作为一种特殊的数据结构，也就冇其特殊的一系列算法。一、搜索概述搜索是人工智能中的一种基本方法，也是信息学竞赛选手所必须熟练学
5、握的一种方法。搜索的进程可以看作是从状态空间树的树根出发，根据题冃约束条件遍历搜索树的过程。根据结点扩展方向的不同，搜索可以有两种实现：深度优先搜索(DFS——DepthFirstSearch)和宽度优先搜索(BFS——BreadthFirstSearch)o本节重点讲述深度优先搜索(DFS)o【例1】货郎担问题某售货员要到若十个城市销售货物，已知各城市Z间的交通费用，求一条旅行线路，使每个城市仅经过一次，最后冋到出发城市，而总费用最低。这里我们约定，售货员住在笫1个城市(即从笫1个城市出发。例如：售货员住在城市1,下图表示各城市之间的交通费用。O
6、OCO178co5172OO6253OO计算机中存储方式城市旅游费用【分析】用一个二维数组来存储上而的有向带权图，数组中X表示两城市间不连通。如果我们把回到出发城市略去，先得到一个遍历所冇城市的路径，然后再來考虑回到出发城市的条件（因为条件特殊目•易实现），那么4个城市间所有可能的走法如下图所示:城市一編号我态空间树结点状态空间树可以将问题的有效解空间形象的表示出來,搜索过程小所经过的路径和顶交通费用点，牛成所谓的搜索树。在上图中，所牛成的搜索树用粗线表示。搜索的过程描述如下:（1）初始化最小费cost用为8；（2）从结点A开始搜索，由于城市1和2
7、不连通，所以结点B为“死结点”；返回到“扩展结点”A；（3）在“活结点”C和D中选一个节点开始扩展，这里不妨选择结点C（后而均按“活结点”的序号由小到大选择）；（4）若从A到当前结点费用Z和小于cost,则从C结点继续向下扩展；(5)找到一条合适的路径“A・C・G・M”，这时M为叶子节点且所有城市均遍历过,；若城市4和城市1连通,R费川Z和小于cost,则找到一条旅行路线，更新cost,返I川上层结点，继续搜索；肓到A的所有儿子结点全部搜索完毕，结束搜索。(5)得到一条长为6的最短回路"1-3-2-4-1”。二、深度优先搜索入门(DFS)所谓“深度
8、”是对产生问题的状态结点而言的，“深度优先”是一种控制结点扩展的策略，这种策略是优先扩展深度人的结点，把状态向纵深发展。【
