DFS_深度优先搜索.pptx

213547A6B9810DFS——深度优先搜索 许杰浩从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到“ 尽头 ”而没达到目的地的时候, 再倒回上一个出发点, 从另一个可能出发, 继续搜索.如从A找一条路到B的时候深度优先搜索的搜索策略是： 尽可能“深”的搜索某一分支。在深度优先搜索中，对于最先发现的结点，如果还有以此为起点的未搜索边，则沿此边继续搜索下去。当结点V的所有边都已经被探寻过，搜索将回溯到发现点V的那条边的始结点。重复此过程直至源结点可到达的所有结点为搜的顺序是：1-2-4-7---5-8---3-61树的深搜23伪代码：void dfs(int u){ for(u的每一个子节点v){ dfs(v); } }45678深搜的顺序是：1-2-4-7---5-8---3-6过程在可以看做是栈的结构dfs(1) dfs(1) dfs(1) dfs(1) dfs(1) dfs(1) dfs(1) dfs(1) dfs(2) dfs(2) dfs(2) dfs(2) dfs(2) dfs(3) dfs(3) dfs(4) dfs(4) dfs(5) dfs(5) dfs(6) dfs(7) dfs(8)SAHBFLICDGJKE图的深搜Hdu 1241题目大意：给定一个图，上边有*和@两种标记，其中@表示石油，好多@连在一起可以看成一个大的石油区，问在这个区域中有多少个石油区0 1 27 _ 36 5 4int dx[8]={-1,-1,-1,0,1,1, 1, 0};Int dy[8]={-1, 0, 1,1,1,0,-1,-1};Void dfs(int x,int y){ g[x][y]=‘*’; for(int i = 0; i 8; i++){ xx = x + dx[i] ; yy = y + dy[i] ; if(xx 0 || yy 0 || xx = m || yy = n ) continue ; if(g[xx][yy]==@) dfs(xx , yy) ; }}yxPOJ 2676题意：数独，找出一个可行解即可（数独规则：：把一个9行9列的网格，再细分为9个3*3的子网格，要求每行、每列、每个子网格内都只能使用一次1~9中的一个数字，即每行、每列、每个子网格内都不允许出现相同的数字。）0是待填位置，其他均为已填入的数字。粗暴的方法 DFS加回溯大概的框架： dfs(int x,int y){ for(int i=1;i=9;i++){ if(这个位置能填 i ){ g[x][y]=i; (找到下一个为0的位置为(xx,yy)); dfs(xx,yy); g[x][y]=0; } }}Dfs的优化剪枝：在求解问题的时候，有时没必要将所有的可能结果都搜索一遍。如果在搜索一个新的节点的时候，如果可以判断到这一个节点不会得到解或是最优解，就可以直接放弃往下的搜索，同理搜索过的状态也可以直接放弃。ZOJ 1008 Gnome Tetravex题目大意： 有一个N*N(N=5)的方格矩阵与N*N张卡片。每个卡片被划分为4个三角形，每个三角形标有一数字(范围从0到9),分别将这些三角形称作左三角形，右三角形，上三角形，下三角形。要求将这些卡片放置到这N*N的方格中，当放置成功的时候要求任意相邻的两个方格中的卡片中相邻的三角形数字相等。问能否按照要求放置成功，如果放置成功就输出Possible，否则输出Impossible。Sample Input Sample Output2 Game 1: Possible5 9 1 44 4 5 66 8 5 40 4 4 3分析：如果我们先从这写卡片中任意选取一个，放置在1行1列，然后选下一个卡片放1行2列（放置的时候我们要像判断符不符合条件），依次下去问题就应该解决了。但是如果第一个位置有n个选择，第二个位置有n-1个选择，第三个位置有n-2个选择。。。如果所有的点都遍历一遍那么时间效率将会是O(n!)，当n=25,25! = 15511210043330985984000000嗯，妥妥的超时了这时候就要进行剪枝了。利用剪枝，去掉一些重复的情况。这个题怎么剪枝？如果这写卡片中有10个是相同类型的，那么搜索的结果就变成了15！= 1307674368000所以这一个剪枝就是，记录有多少种不同的卡牌，记录同种卡牌的数量还有一些技巧就是:从上往下，从左往右去放，假设从0开始放，当放到N*N的时候就是搜索成功的时候01bool dfs(int index){ if(index==N*N) return true; else { …… }}23习题：ZOJ 1008ZOJ 1004P