【总结】DFS常用技巧详解 —— 奇偶剪枝

约定不等于承诺〃 2023-07-03 03:17 21阅读 0赞

> 以下内容整合了网上收集以及自己写的部分

**剪枝**

*  剪枝策略就是在搜索过程中利用过滤条件来剪去完全不用考虑（已经判断这条路走下去得不到最优解）的搜索路径，从而避免了一些不必要的搜索，大大优化了算法求解速度，还保证了结果的正确性。
 *  简单的说就是把不可行的一些情况剪掉，例如走迷宫时运用回溯法，遇到死胡同时回溯，造成程序运行时间长。剪枝的概念，其实就跟走迷宫避开死胡同差不多。若我们把搜索的过程看成是对一棵树的遍历，那么剪枝顾名思义，就是将树中的一些“死胡同”，不能到达我们需要的解的枝条“剪”掉，以减少搜索的时间。

**奇偶剪枝**

把矩阵看成如下形式：(0和1代表奇偶性) 
    0 1 0 1 0 1 
    1 0 1 0 1 0 
    0 1 0 1 0 1 
    1 0 1 0 1 0 
    0 1 0 1 0 1 
    
    从为 0 的格子走一步，必然走向为 1 的格子 。
    从为 1 的格子走一步，必然走向为 0 的格子 。
    即： 从 0 走向 1 必然是奇数步，从 0 走向 0 必然是偶数步。
    
    所以 当遇到从 0 走向 0 (从 1 走向 1 ) 但是要求时间是奇数的
    或者 从 1 走向 0 (从 0 走向 1 ) 但是要求时间是偶数的
    都可以直接判断不可达！
    
    比如有一地图：
    S...
    ....
    ....
    ....
    ...D
    
    要求从S点到达D点，此时，从S到D的最短距离为
     s = abs ( dx - sx ) + abs ( dy - sy )
    
    
    如果地图中出现了不能经过的障碍物：
    S..X
    XX.X
    ...X
    .XXX
    ...D
    
    此时的最短距离 s' = s + 4
    绕开障碍就会偏移原路线，但不管偏移几个点，最终都要回到原路径上
    偏移的距离都是最短距离 s 加上一个偶数距离（因为一出一进）
    
    就如同上面说的矩阵
    要求你从0走到0，无论你怎么绕，永远都是最短距离 (偶数步) 加上偶数步
    要求你从1走到0，永远只能是最短距离 (奇数步) 加上偶数步
    
    结论：路径的偏移量永远为偶数。
    因为最短路径步数 + 偏移量（偶数）= 某一可行解歩数
    又 偶数 + 偶数 = 偶数，奇数 + 偶数 = 奇数
    故 某一可行解步数的奇偶性由最短路径步数决定
    即 最短路歩数和某一可行解歩数的奇偶性相同

**例题：**[【HDU】1010 Tempter of the Bone  
][HDU_1010 Tempter of the Bone]

*  **题意：** 小狗能否从起点S，经过时间T，恰好到达终点D。‘.’表示可以走的路，’\#’表示不能走的墙，’S’表示开始位置，‘D’表示结束位置，不能走回头路。
 *  **思路：** 奇偶剪枝的典型题。没有剪枝就会 TLE。设当前位置 (x, y) 到 D 点 (dx, dy) 的最短距离为 minn，到达当前位置 (x, y)已经花费时间 (步数) sum，题目要求的时间T。
    
    1.  奇偶剪枝：对于当前位置 (x, y)，如果 T - sum 与 minn 的奇偶性不同，则剪掉。
    2.  可达性剪枝：如果 T - sum < minn，则剪掉。
    3.  可达性剪枝：如果一开始给定时间与最短路径差值不是偶数或者比最短路径小就可以直接输出 “NO” 了。

**Code：**

import java.util.Scanner;
    public class Main { 
    	static int n,m,t,sx,sy,ex,ey;
    	static boolean flag;
    	static int[][] dir = { { 1,0},{ -1,0},{ 0,1},{ 0,-1}};
    	static boolean[][] vis = new boolean[10][10];
    	static char[][] maps = new char[10][10];
    	static void dfs(int x,int y,int sum) { 
    		if(flag)	return;		//巨坑，没这句就会TLE
    		if(maps[x][y]=='D' && sum==t) { 
    			flag=true;
    			return;
    		}
    		if((t-sum)%2!=(Math.abs(x-ex)+Math.abs(y-ey))%2)	return;		//奇偶剪枝
    		if(t-sum<Math.abs(x-ex)+Math.abs(y-ey))	return;	//可达性剪枝
    		for(int i=0;i<4;i++) { 
    			int xx=x+dir[i][0];
    			int yy=y+dir[i][1];
    			if(xx>=1 && xx<=n && yy>=1 && yy<=m && !vis[xx][yy] && maps[xx][yy]!='X') { 
    				vis[xx][yy]=true;
    				dfs(xx,yy,sum+1);
    				vis[xx][yy]=false;
    			}
    		}
    		return;
    	}
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner cin = new Scanner(System.in);
    		while(cin.hasNext()) { 
    			flag=false;
    			for(int i=0;i<=8;i++)
    				for(int j=0;j<=8;j++) { 
    					vis[i][j]=false;
    					maps[i][j]='0';
    				}
    			n = cin.nextInt();	m = cin.nextInt();	t = cin.nextInt();
    			if(n==0 && m==0 && t==0)	break;
    			for(int i=1;i<=n;i++) { 
    				String str = cin.next();
    				for(int j=1;j<=m;j++) { 
    					maps[i][j] = str.charAt(j-1);
    					if(maps[i][j]=='S') { 
    						sx=i;
    						sy=j;
    					}
    					if(maps[i][j]=='D') { 
    						ex=i;
    						ey=j;
    					}
    				}
    			}
    			int minn = (Math.abs(sx-ex)+Math.abs(sy-ey));
    			if((t-minn)%2==1 || t<minn) { 	//奇偶剪枝
    				System.out.println("NO");
    				continue;
    			}
    			vis[sx][sy]=true;
    			dfs(sx,sy,0);
    			if(flag)	System.out.println("YES");
    			else	System.out.println("NO");
    		}
    	}
    }

[HDU_1010 Tempter of the Bone]: http://acm.hdu.edu.cn/showproblem.php?pid=1010