DFS

深度优先搜索引入思考题：输入一颗二叉树，对其进行先序遍历右侧二叉树先序遍历结果为：12453672136745二叉树先序遍历的伪代码：FirstTraveral（root）print根节点的值左儿子不为空，FirstTraveral当前节点的左儿子右儿子不为空，FirstTraveral当前节点的右儿子其实这个遍历过程就是DFS(depth-firstsearch)进入某一子树后必先将该子树遍历后再遍历该子树外的节点每次搜索的时候必先搜索尚未搜索的且具有最大深度的节点需要的数据结构：栈-stackDFS基本思想：从初始状态S开始，利用规则生成搜索树下一层任一个结点，检查是否出现目标状态G，若未出现，以此状态利用规则生成再下一层任一个结点，再检查是否为目标节点G，若未出现，继续以上操作过程，一直进行到叶节点（即不能再生成新状态节点），当它仍不是目标状态G时，回溯到上一层结果，取另一可能扩展搜索的分支。生成新状态节点。若仍不是目标状态，就按该分支一直扩展到叶节点，若仍不是目标，采用相同的回溯办法回退到上层节点，扩展可能的分支生成新状态，…，一直进行下去，直到找到目标状态G为止。DFS算法过程：intdfs(Nodes，Nodetarget){for(everychildnodeaofNodes){if(aisthetarget)return1;elseif(dfs(a)==0)continue;elsereturn1;}return0;}搜索过程如下：HALIFBCDEJGKS深度优先搜索示意图油田问题-ZOJ1709这个问题我们之前采用bfs求解了其对应的解。当然我们也可以用dfs来求解这个问题。solution：从每个油田出发，用dfs搜索所有成块的油田。同时将已访问过的油田做上标记，防止被再次搜索。voidDfs(intx,inty){inti;intxx;intyy;grid[x][y]='*';//将该节点转化为非油田for(i=0;i8;i++){xx=x+dir[i][0];yy=y+dir[i][1];if(xx0||yy0||xx=m||yy=n)continue;if(grid[xx][yy]=='@')Dfs(xx,yy);}}八皇后问题先考虑如下问题：在一个n*n的棋盘上放置n个皇后，且使得n个皇后间彼此不会互相攻击，即：每两个皇后不再同一行，同一列，同一对角线。打印输出任意一个解。分析：对于n=1的时候，问题很简单，对于n=2和n=3的时候，问题无解。考虑n=4的时候，怎么求解该问题。因为要输出一个解。那么我们就需要知道每一个皇后是如何放置的。我们来模拟放置皇后的过程。开始的时候，棋盘为空，首先我们先把皇后1添加到第一行第一列，对于皇后2，在经过第一列与第二列的失败尝试后，我们把它放到一个可能的位置（2，3），当我们尝试放置皇后3的时候，我们发现没有办法放置，所以我们回退到放置皇后2，我们改变皇后2的位置，将其放置到（2，4），然后继续尝试放置皇后三，我们很快发现位置(3,2)可以放置，我们开始放置皇后4，但是发现皇后4没有地方放置了，我们只能回退，重新放置3，但是此时皇后3已经没有地方可以放置了，我们继续回退，重新放置皇后2，但是皇后2也没有任何可以放置的位置了，我们继续回退，改变皇后1的位置，(1,2)，然后放置皇后2(2,4)，在探索放置皇后3,(3,1),在放置皇后4，(4,3)此时所有的皇后都被安全放置了。我们找到了一个可行的解，然后就打印输出结果。在寻找可行解的时候，我们总是试探性的放置，放置合法的时候，我们就进行下一个皇后的放置，当遇见无法放置的时候，我们立即返回，修改上一个皇后的位置，然后在进行试探。在放置皇后的过程中，我们在进行这一个与dfs相同的过程。在当前状态下去搜索所有可能的位置，直到找出一个可行的解，如果找不到则返回。我们将上述过程用一棵树表示如右图所示在求解上述问题的时候，我们首先确定一个策略：先放置第一行的皇后1，再去尝试放置第二行的皇后2，再尝试放置皇后3......当放置失败的时候或者没有地方可以被放置的时候即返回到上一行中，重新放置上一行的皇后位置。加强版的dfs基本做法：利用深度优先搜索，在搜索的时候去掉那些不必要的点。基本思想：从一条路往前走，能进则进，不能进则退回来，换一条路再试。具体说,就是：在搜索(依次用各种方法一一去试探)的过程中，当在P点有N种选择，则从第一种开始尝试，若第K种可行，即这一步搜索成功，打上标记，再向前(即P+1点)搜索；如在P点搜索失败(所有的方法都试探过，没有一种可行)，为了摆脱当前的失败，就返回搜索进程中的上一点(即P-1点)，再用第K+1种方法(假设上次在P-1点用第K种方法搜索成功，必须明确以前用过的方法不能再用，否则会陷入死循环)再去搜索，重新寻求解答。这样搜索回溯，再搜索再回溯，如能搜索到终点，问题有解，如最后回溯到出发点，问题就无解。//t为深度voiddfs(intt){if(tn){output(x);return;}else{for(在p点的每一种选择)if(满足约束条件)dfs(t+1);}}dfsdfs算法的效率是比较低的。时间复杂度：O(V+E)空间复杂度：通常情况下为O(h(n))h(n)为搜索过程中最深的深度与BFS比较：对待节点的搜索顺序不同，一个是优先搜索距离为k的，一个是优先搜索k+1的。效率上也是有很大的差别的，一般情况下bfs搜索到的结果是最优解，而dfs需要遍历完所有的节点后才能得到最优解。当节点数与边的数目都很大的时候，dfs与bfs的效率都是很低的，这时怎么办？是不是不能继续使用dfs与bfs？ZOJ1008GnomeTetravex题目大意：有一个N*N(N=5)的方格矩阵与N*N张卡片。每个卡片被划分为4个三角形，每个三角形标有一数字(范围从0到9),分别将这些三角形称作左三角形，右三角形，上三角形，下三角形。要求将这些卡片放置到这N*N的方格中，当放置成功的时候要求任意相邻的两个方格中的卡片中相邻的三角形数字相等。问能否按照要求放置成功，如果放置成功就输出Possible，否则输出Impossible。SampleInputSampleOutput2Game1:Possible5914445668540443dfs在求解问题的时候，有时没必要将所有的可能结果都搜索一遍。如果在搜索一个新的节点的时候，已经可以判断出某一条路不能产生我们想要的解的时候或者不能产生解的时候，我们就没必要再继续走下去了。剪枝：将一些不可能得到解或者最优解的情况从搜索的情况中去掉。即在程序中继续下一层次的搜索的时候，我们可以先判断一下当前选择是不是会得到最优解或者解。如果得不到就不去遍历，如果可能产生就继续遍历。分析：与前面的N皇后问题很相似，只不过前面是求解一个可行的情况并打印输出，而这个是判断是不是可能？其实是一样的，当我们搜索到一个解的时候，不久意味着我们找到了解，也就是问题有解。仍和前面一样，我们仍然是先从这写卡片中任意选取一个，放置在1行1列，然后选取下一个卡片放置到1行2列，放置的时候我们要像判断皇后是不是冲突一样判断这个卡片放置后是不是会满足相邻的卡片的相邻数字是不是相等，如果相等我们就继续放置下一个位置，如果不相等，那么就换下一个卡片放置，如果都不行，那么我们应该返回重新放置前面一个卡片，依次类推。。。。我们似乎已经解决了问题了。但是考虑一下时间效率。。第一个位置有n个选择，第二个位置有n-1个选择，第三个位置有n-2个选择。。。如果所有的点都遍历一遍那么时间效率将会是O(n!)，我们的n=25,25!=15511210043330985984000000,话说这样跑下去我们得多久才会把这个问题解决？悲剧了==！TT难道我们就不能用这个方法解决这个问题？还记不记得我们前面说过，在得不到解的时候我们没必要继续向下搜。这样我们可以去除一些重复情况，这样效率就得到了提升-———剪枝这个题怎么剪枝？如果这写卡片中有10个是相同类型的，那么搜索的结果就变成了15！=1307674368000，比之前的快多了^^那么这里就可以进行剪枝了。怎么做?在读入数据的时候，我们进行相同卡片的判断。用一个数组来记录每种卡片的个数，遇到相同的卡片，对应的个数就加1。是不是还需要其他的剪枝？。。。其实这个剪枝已经足够了。。10s够了。。需要的数据结构用一个结构体来存储每个位置的上下左右四个位置的值。用一个整形数组visit[]来记录每类卡片的个数。用一个二维数组来保存在试探放置过程中的卡片的类型(用下标即可)。一些函数：由于要在输入的时候对卡片的类型进行分类，那么我们需要一个索引函数，用于查找对应的卡片类型。在放置卡片的时候我们需要判断是不是放置合法，怎么判断？我们总是从左到右，从上到下放置的，所有我们只需要检测放置后是不是与其上方与左方的卡片冲突即可。。。在一个就是dfs了，记录一个深度，当深度等于N*N的时候(假设初始的时候是0)我们就可以搜索成功，直接返回练习题