矩形方格步道
网格走描述一类受某些限制的计算穿过给定网格的路径数量的问题。最常见的限制是,唯一有效的移动是那些接近目标的移动;事实上,这是如此普遍,以至于术语“网格行走问题”几乎总是包含这种限制。因此,在以下所有部分,包括“无限制”部分,将始终假定此限制。
由于网格行走问题的有限状态性质,它们特别适合从<一个href="//www.parkandroid.com/wiki/problem-solving-dynamic-programming/" class="wiki_link" title="动态规划" target="_blank">动态规划,实际上,许多实用的方法都是从手动执行动态规划算法派生或等价的。
网格行走问题本身就很重要,但也因为许多组合情况可能很重要<一个href="//www.parkandroid.com/wiki/bijection-injection-and-surjection-definition/" class="wiki_link" title="bijected" target="_blank">bijected到网格行走问题,从而立即建立他们的解决方案。例如,把<一个href="//www.parkandroid.com/wiki/identical-objects-into-distinct-bins/" class="wiki_link" title="不同的垃圾箱" target="_blank"> 相同的对象 不同的垃圾箱等价于遍历一个 网格。
动机
考虑下面的例子:
青蛙开尔文住在原点,他想去拜访他的朋友 .在任何情况下,青蛙Kelvin只能向上或向右跳跃1个单位。从开尔文到他的朋友有多少条路径?
在这种情况下,除了距离减小的条件(在这种情况下开尔文只能向上和向右移动),没有其他限制。
解决这个问题有两种重要的方法。第一种用途<一个href="//www.parkandroid.com/wiki/recursion/" class="wiki_link" title="递归" target="_blank">递归第二种方法使用了一种巧妙的观察方法,该方法适用于网格行走的无限制变体(但通常不适用于其他情况)。
解决方案1:假设开尔文达到了这个点 在某种程度上。那么开尔文一定来自其中任何一个 或 (因为他只能向上和向右跳),意思是
路径的数量 路径数的和是 路径的数量 .
此外,只有一个路径 和 对于任何 .所以我们可以填写一个表格:
5 1 6 21 56 126 252 4 1 5 15 35 70 126 3. 1 4 10 20. 35 56 2 1 3. 6 10 15 21 1 1 2 3. 4 5 6 0 1 1 1 1 1 1 0 1 2 3. 4 所以有252条可能的路径。
这种策略对于较大的网格显然是不切实际的,但它有三个主要优点:
- 这个策略即使在面临额外的限制时也适用,后面的部分将说明这一点。
- 它也适用于非矩形网格,也适用于除了向上/向右移动(例如对角线)之外的更多移动。
- 这对电脑来说很容易<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/rectangular-grid-walk-no-restriction/">执行,使用一个简单的动态规划算法。
此外,这种策略还揭示了<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/learn-and-practice-combinatorics-on-brilliant/">组合问题的根源。仔细检查上面的表格会发现一些有趣的事情:
这有力地表明网格行走与<一个href="//www.parkandroid.com/wiki/properties-of-binomial-coefficients/" class="wiki_link" title="二项式系数" target="_blank">二项式系数.事实上,原因很简单:
解决方案2:达到 开尔文必须向上跳5次,向右跳5次。开尔文没有其他途径可以到达目的地。然而,他可以以任何可能的顺序进行这些移动,每个顺序对应于不同的网格行走。根据二项式系数理论,可以得出有 可能的路径。
没有限制
假设一个粒子从一个 沿着网格的边缘做步骤,将网格移到右上角。
确实有 控件中从左下角到右上角的路径 网格。
通常,一个<一个href="//www.parkandroid.com/wiki/cartesian-plane/" class="wiki_link" title="笛卡儿平面" target="_blank">笛卡儿平面是叠加在网格上的,所以这个问题等价于从 来 .
考虑创建一个受某些约束的“单词”(任何字母字符串)的另一个问题:
- 单词必须有长度 .
- 这个单词只能包含两个字母:R和U。
- 这个词必须包含 R和 你的。
这个问题的答案是由二项式系数的定义之一给出的:有 有效的词汇。
注意,每个单词都描述了一个网格行走 网格,从左下角开始:
- 正常阅读这个单词,一次一个字母,从左到右。
- 每当读到一个R,向右移动 单元在网格中。
- 每读到一个U,向上移动 单元在网格中。
因为这个词包含 R和 当单词结束时,网格行走将在右上角结束。以这种方式描述的每个网格行走都是独特的,因为两个单词中第一个不同的字母被视为两条路径之间的分叉。从左下角到右上角的任何网格移动都可以用这种方式描述,因为每次向右移动时写R,每次向上移动时写U,就可以创建一个有效的单词。
由此可以得出,这样的网格行走的数量与有效单词的数量相同。所以有 可能的网格行走。
因此,方格行走“数字”表确实等于二项式系数表。有几个组合恒等式可以从这种认识中推导出来,其中之一是<一个href="//www.parkandroid.com/wiki/hockey-stick-identity/" class="wiki_link" title="曲棍球棍身份" target="_blank">曲棍球棍身份.
考虑一个维度的网格行走问题 从原点开始,到 .
注意,这样的路径必须沿着线之间的边 这条线 在某个时间点。此外,它必须精确地执行一次。一旦路径到达直线 ,只有一条路可以到达 (上上下下)。由此得出,网格行走的“数字”之和为 通过 一定是网格行走的“数字”为 .换句话说,
曲棍球棍身份
算法方法
回想一下例子问题:
青蛙开尔文住在原点,他想去拜访他的朋友 .在任何情况下,青蛙Kelvin只能向上或向右跳跃1个单位。从开尔文到他的朋友有多少条路径?
计算机可以用相当直接的方式解决这类问题。下面是一些Python代码:
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
但是,如果只需要计算二项式系数,为什么创建这样一个程序是有用的呢?有时候,网格行走问题有进一步的约束条件,比如邪恶的怪物和不方便的墙壁,或者额外的允许动作,比如对角线向上和向右的步骤。
青蛙开尔文住在原点,他想去拜访他的朋友 .然而,一个邪恶的怪物住在 所以开尔文跳不过去。在任何情况下,青蛙Kelvin只能向上或向右跳跃1个单位。从开尔文到他的朋友有多少条路径?
没有一个立即可处理的数学解决方案,特别是当存在许多约束条件时。但是对于这个程序来说,只需要稍微修改一下就可以解决这个问题:
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
一个国王能从一个角落走多少条路 棋盘到对面角落?
国王可以向任何方向移动1个方格,包括对角线。
在本例中,递归如下:
路径的数量 路径数的和是 的路径数 的路径数 .
解决方案。
根据新的递归公式对上述程序稍作修改,可得
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16defdp(米,n,加勒比海盗):如果米= =0或n= =0:返回1如果米<0或n<0:返回0如果加勒比海盗[米] [n]! =0:返回加勒比海盗[米] [n]加勒比海盗[米] [n]=dp(米-1,n,加勒比海盗)+dp(米,n-1,加勒比海盗)+dp(米-1,n-1,加勒比海盗)返回加勒比海盗[米] [n]米=8n=8加勒比海盗=[0]*(米+1)为我在范围(米+1):加勒比海盗[我]=[0]*(n+1)打印(dp(米,n,加勒比海盗))
输出产生答案
限制点
还有一个解决这类问题的数学框架。
青蛙开尔文住在原点,他想去拜访他的朋友 .然而,一个邪恶的怪物住在 所以开尔文跳不过去。在任何情况下,青蛙Kelvin只能向上或向右跳跃1个单位。从开尔文到他的朋友有多少条路径?
解由<一个href="//www.parkandroid.com/wiki/principle-of-inclusion-and-exclusion-pie/" class="wiki_link" title="包容-排斥原则" target="_blank">包容-排斥原则.
暂时忽略怪物的存在,这样就有252条路径 .如果路径的数量 通过 可以算出来,那么有多少 -避免路径可以通过简单的减法计算。
有多少条路径经过 首先,开尔文要从 来 没有限制,确实有 方法。然后他就得从 来 也就是从原点跳到 ,所以有 这样的路径。因此,有 经过的路径 ,这意味着 没有的路径。
这就产生了另一个公式:
确实有 从原点到 没有穿过这个点 .
换句话说,就是从 来 在避开一个限制点的同时 是由到达目的地的路径数给出的 没有限制,减去到达的路径数 通过 .
下面的定理提供了一种更一般的方法<一个href="//www.parkandroid.com/wiki/sets/" class="wiki_link" title="集" target="_blank">集限制点。
一般来说,给定限制点 ,让 就是从哪里出发的路径的数量 来 通过所有的点 .然后,
请注意, 而且,如果 ,然后 .
当 , , 对所有 时,定理转化为(2)的公式<一个href="//www.parkandroid.com/wiki/catalan-numbers/" class="wiki_link" title="加泰罗尼亚的数字" target="_blank">加泰罗尼亚的数字.
这个定理直接由<一个href="//www.parkandroid.com/wiki/principle-of-inclusion-and-exclusion-generalized/" class="wiki_link" title="包容-排斥的广义原则" target="_blank">包容-排斥的广义原则.直观地说,这个定理形式化了这样一个概念:“我们到达那里的方法的数量等于到达那里的所有可能的方法的数量,减去看起来没有吸引力的方法的数量,加上看起来没有吸引力但我们仍然可以工作的方法的数量,减去看起来没有吸引力但可行但实际上被阻塞的方法的数量……”换句话说,每个部分和都是计算答案的一次尝试,这是在之前的部分和尝试的基础上改进的。
青蛙开尔文住在原点,他想去拜访他的朋友 .然而,一个邪恶的怪物住在 所以开尔文跳不过去。另一个邪恶的怪物住在 所以开尔文也不能走到那里。在任何情况下,青蛙Kelvin只能向上或向右跳跃1个单位。从开尔文到他的朋友有多少条路径?
从上面的问题中,有120条路径经过(2,2)。类似地,有120条路径经过(3,3),因此从252条不受限制的路径中减去这两条路径。然而,这将某些路径减去两次,即经过(2,2)的路径而且(3,3)所以它们必须加回来。有 这些路径中,总共有 路径。
墙
如果网格中有墙(或缺失的线),这意味着某些单单元移动是非法的,那么包含-排除论证就会变得更加复杂。例如,
青蛙开尔文住在原点,他想去拜访他的朋友 .然而,中间有一堵墙 而且 ,开尔文跳不过去。在任何情况下,青蛙Kelvin只能向上或向右跳跃1个单位。从开尔文到他的朋友有多少条路径?
寻找一条可以走的路 来 ,它必须从原点移动到 ,向右移动,然后前往 .有 这样的路径,确实存在 避开墙的路径。
确实有 路径从 来 而使用之间的路径 而且 .因此,有确切的 路径从 来 避开中间的墙 而且
任何穿过墙的路径都必须到达某个点(就在穿过墙之前) .有 从… 来 .从那点开始,有一条路可以到达 ,这需要翻过墙。从 ,有 路径 .既然必须避开墙,就有 可能的路径。
根据上述定理中的公式,对于多壁问题也可以采用类似的方法。特别是,如果 是一套墙和 方法的个数是从 来 在通过墙在里面 ,然后
青蛙开尔文住在原点,他想去拜访他的朋友 .然而,中间有一堵墙 而且 和一堵墙 而且 ,开尔文跳不过去。在任何情况下,青蛙Kelvin只能向上或向右跳跃1个单位。从开尔文到他的朋友有多少条路径?
从上面的问题来看,有 穿过第一堵墙的路径。类似地,有 穿过第二堵墙的路。然而,有 穿过两堵墙的小路。因此,有 路径。
其他法律行动
当除标准移动(右和上)之外的移动可用时,递归方法通常优于双射方法。即使存在简单的双射,发现它通常也需要分析递归。例如,
一个国王能从一个角落走多少条路 棋盘到对面角落?
国王可以向任何方向移动1个方格,包括对角线。
有可能解决这些运动的一般情况,称为king-walks,在 网格。然而,没有一个封闭的形式,表达式不像只有两种可能的移动类型时那样。
简而言之,国王步行的数量 是
注意,如果我们知道有多少次向右移动,我们也就知道有多少次向上移动;一定是相同的数字。此外,向右移动的次数加上对角线移动的次数必须为 .所以如果有 正确的移动,然后我们可以计算移动的次数<一个href="//www.parkandroid.com/wiki/combinations/" class="wiki_link" title="结合" target="_blank">结合,知道有 移动总: 对角线移动时, 正确的动作 移动。把所有可能的值加起来 ,国王步行的数量应该是