DFS中的奇偶剪枝学习笔记
DFS中的奇偶剪枝学习笔记
奇偶剪枝学习笔记
描述
现假设起点为(sx,sy)，终点为（ex,ey），给定t步恰好走到终点，
s | ||||
|---|---|---|---|---|
| | ||||
| | ||||
| | ||||
+ | — | — | — | e |
如图所示（“|”竖走，“—”横走，“+”转弯），易证abs(ex-sx)+abs(ey-sy)为此问题类中任意情况下，起点到终点的最短步数，记做step，此处step1=8；
s | — | — | — | |
|---|---|---|---|---|
— | — | + | ||
| | + | |||
| | ||||
+ | — | — | — | e |
如图，为一般情况下非最短路径的任意走法举例，step2=14；
step2-step1=6，偏移路径为6，偶数（易证）；
结论
推广之，若 t-[abs(ex-sx)+abs(ey-sy)] 结果为非偶数（奇数），则无法在t步恰好到达；
返回，false；
反之亦反。
原理补充
鉴于很多同学对奇偶剪枝根本原理的兴趣，所以hj决定再补充一下本词条。
还是以这个为例子吧，现在我把矩阵填满 0 和 1 [1]
0 | 1 | 0 | 1 | 0 |
|---|---|---|---|---|
1 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 1 | 0 |
我们现假设从 0 开始走，则不难证明，
从任意 0 走到任意 1 始终是奇数步；
从任意 0 走到任意 0 始终是偶数步；
引用描述里的“例子”， s 到 e 的最短步数为 t (当然你也可以理解成此时到终点刚好剩余 t 步等等)。
则，我们从 s 到 e 的步数之和(或者说总距离)总可以表示成 sum= t + extra ( extra>=0 )，其中 extra 表示额外的步数。[2]
比如“例子”里面的，做例1吧
s | — | — | — | |
|---|---|---|---|---|
— | — | + | ||
| | + | |||
| | ||||
+ | — | — | — | e |
此时 t=8，sum=14，所以我们容易得到 extra=6。也就是说按照这个走法，需要在最短的步数上再走额外的 6 步(先不用太在意这些偏移是在什么地方产生的)。
在来一个例2吧，
s | — | — | — | |
|---|---|---|---|---|
— | — | + | ||
| | + | |||
| | + | — | e | |
+ | — | — |
此时，t=7，sum=15，所以我们也容易得到 extra=8。
根据理科生的天性，由这两个一般性的例子，我们很容易嗅察到 extra 都为偶数。先带着疑惑，
再来看我给的 0 、1 矩阵。
0 | 1 | 0 | 1 | 0 |
|---|---|---|---|---|
1 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 1 | 0 |
设左上角坐标为（1，1），右下角坐标为（5，5）.
那么我们给的例1，
起点 s 的坐标为（1，1），此点为“0”；
终点 e 为（5，5），此点为“0”。
所以t=8，为偶数。
现在我们再倒过来看，从终点(也就是 e )出发，把最短步数 t=8 耗费掉，不妨这样走，
s | + | |||
|---|---|---|---|---|
+ | — | |||
| | ||||
+ | — | |||
— | — | e |
如图所示从 e （5，5）耗费 8 步走到了（1，5）点。
因为是从 0 走偶数步，所以走到的坐标也一定是 0 ，就像这里的（1，5）点是 0 一样。
这是一个递归的过程，首先如果从0开始，目的地也是0，那末其中的最短距离t必然是个偶数，可其中有可能有障碍物或需要绕弯的情况，那末我们就现将最短距离t用于绕弯，从开始的0，走t步不管怎么走都只能到0，而这个0到终点0的最短路径t也必然是偶数，一直递归下去，直到你绕够了到达终点，这中间你额外的步数都是偶数。
注意到，（1，5）点和起点 s （1，1）都是 0，也就是说，这个 extra 必然是偶数！
再看例2，同样从终点 e 开始耗费 t=7 步，
则所到的点一定是 0 (不管她在哪里)，再从这个点回到起点 s ，所用的 extra 也必然是个偶数！
所以无论如何，sum= t + extra ( extra>=0 ) 中的 extra 都是一个偶数
那么我们就可以用公式 t-[abs(ex-sx)+abs(ey-sy)] 计算出extra是否为偶数来判断当前点能否恰好在这么多步到达终点了。
有的同学可能会说以 1 为 起点呢。。其实是一样的啦，自己去捣鼓吧。
核心代码：
ans=t-time-abs(dx-x)-abs(dy-y);
if(ans<0||ans&1) return;说了这么多，再总结一下吧！
什么是奇偶剪枝？
把矩阵看成如下形式： 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 走向 0 但是要求时间是偶数的，都可以直接判断不可达！
比如有一地图：
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，永远只能是最短距离(奇数步)加上某个偶数步。
这里我来讲一下搜索中要用到的奇偶剪枝的原理：
看张图，没障碍物#时，S到E的最短路长为6，但是当有障碍物时，就要绕行了
看这张图，黑色为最短路径，当他绕行（红色加蓝色部分）时，其中蓝色部分其实还是最短路径部分平移来的，所以多走的步数也就是红色部分
对于红色部分我们可以分为两部分，一部分是远离最短路径的步数，另一部分是回到最短路径的部分，他们一定是对称的，所以多走的步数一定是偶数！！！
所以要是问走x步能否到达e，就算出最短路径长y，如果x-y是偶数就能到达，否则不能到达！