专栏首页小樱的经验随笔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是偶数就能到达,否则不能到达!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU 2520 我是菜鸟,我怕谁

    我是菜鸟,我怕谁 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (...

    Angel_Kitty
  • 浅析ASCII、Unicode和UTF-8三种常见字符编码

    什么是字符编码? 计算机只能处理数字,如果要处理文本,就必须先把文本转换为数字才能处理。最早的计算机在设计时采用8个比特(bit)作为一个字节(byte),...

    Angel_Kitty
  • 关于前端的photoshop初探的学习笔记

    写在前边 这还是高三的时候暑假的时候学习这个软件时记的笔记呢,今天又在电脑上找到了它,总觉得不应该让他尘封在我的硬盘上,于是挂了出来。 温馨提示:比较乱,写给自...

    Angel_Kitty
  • MySQL 编码和解码

    背景:目前正在进行业务重构,需要对使用MySQL的业务库表进行重新设计,在迁移时,遇到了中文字符乱码问题(源库表的默认编码是LATIN1,新库表的默认编码为UT...

    skylerxu
  • 浅谈乱码原因及解决方案

    其实作为程序猿来讲,中国的程序猿遇到的问题可能会比国外的程序猿遇到的问题多很多。 一个原因是因为各种标准的制定、各种IDE的编写,都是由老外来完成的,制定出...

    roobtyan
  • 挑战程序竞赛系列(75):4.3强连通分量分解(2)

    挑战程序竞赛系列(75):4.3强连通分量分解(2) 传送门:POJ 3180: The Cow Prom 题意: 求结点大于等于2的强连通分量个数。 直接上...

    用户1147447
  • 挑战程序竞赛系列(76):4.3强连通分量分解(3)

    挑战程序竞赛系列(76):4.3强连通分量分解(3) 传送门:POJ 1236: Network of Schools 题意: 校园网:给定N所学校和网络,目...

    用户1147447
  • MYSQL完整安装和主从双机配置

    ################################# mysql 完整安装 ########################### groupad...

    一见
  • MySQL是如何利用索引的

    在MySQL中进行SQL优化的时候,经常会在一些情况下,对MySQL能否利用索引有一些迷惑。例如:

    用户1516716
  • 10分钟让你明白MySQL是如何利用索引的

    一、前言 在MySQL中进行SQL优化的时候,经常会在一些情况下,对MySQL能否利用索引有一些迷惑。 譬如: MySQL 在遇到范围查询条件的时候就停止匹配了...

    用户1263954

扫码关注云+社区

领取腾讯云代金券