logo标签列表

三角形中的路径数量

algorithmrecursiondynamic-programmingcombinatorics
4
我最近遇到了一个更难的变种问题，但我意识到我无法为这个非常简单的情况生成解决方案。我在 Stack Overflow 上搜索，但找不到以前回答过这个问题的资源。
给定一个三角形 ABC，您必须计算从'A'开始并以其结束的特定长度路径的数量。如果调用我们的函数 f(3)，它必须返回从A开始并以A结束的长度为3的路径数：2 (ABA,ACA)。
我正在努力制定一个优雅的解决方案。目前，我编写了一个生成所有可能路径的解决方案，但对于较大的长度，程序太慢了。我知道必须有一个很好的动态规划解决方案，可以重复使用我们先前计算过的序列，但我无法完全弄清楚。非常感谢任何帮助。
我的愚蠢代码:
def paths(n,sequence):
    t = ['A','B','C']
    if len(sequence) < n:
        for node in set(t) - set(sequence[-1]):
            paths(n,sequence+node)
    else:
        if sequence[0] == 'A' and sequence[-1] == 'A':
            print sequence
抱歉，我不是很理解。如果我在三角形上再加一个点，那不就会变成另一个4个点的圆形图吗？我现在会尝试解决这个问题。 - Simple Learner
我并不是指4个点 - 只要你需要做一些事情来展示一个稍微“更长的长度”，就可以了。 - גלעד ברקן
有，看我的答案并尝试n = 21，它会输出349526。 - shole
我明白了 - 之前我没理解。A B C保持不变，只有n会改变？ - גלעד ברקן
@SimpleLearner 如果有任何不清楚的地方，请告诉我 :) 我会进行编辑并使事情更加清晰...另外，如果路径长度（即：n）很大，则您可能需要更改数组的大小并使用long long（64位int）。 - shole
显示剩余2条评论
6个回答
3

让PA(n)表示从点A出发，在恰好n步内返回A的路径数量。 让P!A(n)表示从点B（或C）出发，在恰好n步内到达A的路径数量。

因此：

PA(1) = 1
PA(n) = 2 * P!A(n - 1)

P!A(1) = 0
P!A(2) = 1
P!A(n) = P!A(n - 1) + PA(n - 1)
       = P!A(n - 1) + 2 * P!A(n - 2) (for n > 2) (substituting for PA(n-1))

我们可以像求解Fibonacci数列一样，通过注意到(-1)^n和2^n都是差分方程的解，并找到系数a、b来解析地解决P!A的差分方程。然后，我们得到了方程式P!A(n) = a*2^n + b*(-1)^n。
我们最终得到方程式P!A(n) = 2^n/6 + (-1)^n/3，PA(n)为2^(n-1)/3 - 2(-1)^n/3。
这给我们提供了代码：
def PA(n):
    return (pow(2, n-1) + 2*pow(-1, n-1)) / 3

for n in xrange(1, 30):
    print n, PA(n)

这将输出:

1 1
2 0
3 2
4 2
5 6
6 10
7 22
8 42
9 86
10 170
11 342
12 682
13 1366
14 2730
15 5462
16 10922
17 21846
18 43690
19 87382
20 174762
21 349526
22 699050
23 1398102
24 2796202
25 5592406
26 11184810
27 22369622
28 44739242
29 89478486
我花了一些时间才理解递归关系，但我现在认为我懂了。P!A(n) = P!A(n - 1) + PA(n - 1) 计算从 B 到 A 的路径：1）P!A(n-1) 计数从 C 开始并以长度 n-1 结束但起源于 B 的路径到达 A。2）PA(n - 1) 计数从 A 到 A 的长度为 n-1 的路径，其起源于 B。 - Simple Learner
这对你来说是一个显而易见的解决方案吗？如果是，有没有什么问题解决书籍或问题帮助了你？ - Simple Learner
@SimpleLearner 看看斐波那契数列的维基百科页面，几乎有相同的理论（虽然这个序列因为二次方程的根是整数而运算得更好）。此外，Sedgewick和Flageolet的《算法分析导论》介绍了计数离散结构的一般技术。 - Paul Hankin
2
您可以比其他人发布的动态规划/递归解决方案更好地处理给定三角形和更一般的图形。每当您尝试计算（可能是有向）图中的行走次数时，您可以使用转移矩阵的幂项的条目来表示。让M是一个矩阵，其条目m [i] [j]是从顶点i到顶点j的长度为1的路径数量。对于三角形，传递矩阵为：
0 1 1
1 0 1.
1 1 0

然后M^n是一个矩阵，其i,j项是从顶点i到顶点j长度为n的路径数。如果A对应于顶点1，则您需要M^n的1,1项。
以动态规划和递归的方式计算长度为n的路径计数与以长度为n-1的路径计数为基础计算M^n等价，需要n次乘法，即M * M * M * ... * M，这可以足够快地完成。但是，如果您想计算M^100，而不是进行100次乘法，您可以使用重复平方法：计算M、M^2、M^4、M^8、M^16、M^32、M^64，然后计算M^64 * M^32 * M^4。对于更大的指数，乘法次数约为c log_2(exponent)。
与使用长度为n-1的路径和长度为1的步骤构成长度为n的路径不同，这里使用长度为k的路径和长度为n-k的路径构成长度为n的路径。
2

我的方法如下：

定义DP(l, end) = 以 end 结尾且长度为 l 的路径数量 然后 DP(l,'A') = DP(l-1, 'B') + DP(l-1,'C')，对于 DP(l,'B') 和 DP(l,'C') 同理。

对于基本情况，即 l = 1，如果结束点不是 'A'，则返回0，否则返回1，这样所有更大的状态只计算以 'A' 开头的路径。

答案就是调用 DP(n, 'A')，其中 n 是路径长度。

以下是 C++ 的示例代码，您可以使用 3 调用它，得到 2 作为答案；使用 5 调用它，得到 6 作为答案：ABCBA、ACBCA、ABABA、ACACA、ABACA、ACABA

#include <bits/stdc++.h>
using namespace std;

int dp[500][500], n;

int DP(int l, int end){
 if(l<=0) return 0;
 if(l==1){
  if(end != 'A') return 0;
  return 1;
 }
 if(dp[l][end] != -1) return dp[l][end];
 
 if(end == 'A') return dp[l][end] = DP(l-1, 'B') + DP(l-1, 'C');
 else if(end == 'B') return dp[l][end] = DP(l-1, 'A') + DP(l-1, 'C');
 else return dp[l][end] = DP(l-1, 'A') + DP(l-1, 'B');
}

int main() {
 memset(dp,-1,sizeof(dp));
 scanf("%d", &n);
 
 printf("%d\n", DP(n, 'A'));
 return 0;
}

已编辑 回答下面的评论:

首先，DP (动态规划) 总是涉及状态。

记住，这里我们的状态是 DP(l,end)，表示长度为l且以end结尾的路径数。因此，要使用编程实现状态，通常使用数组，因此 DP [500] [500] 只是用于存储所有可能的l和end的状态 DP(l,end) 的空间（这就是为什么我说如果你需要更长的长度，请更改数组大小）

但是然后你可能会问，我理解第一个维度，它是用于l，500 意味着l可以达到 500，但第二个维度怎么办？我只需要 'A'、'B'、'C'，为什么使用 500 呢？

这里是另一个技巧（C/C++），char 类型确实可以默认作为 int 类型使用，其值等于其 ASCII 数字。当然我不记得 ASCII 表格了，但我知道大约 300 就足以表示所有 ASCII 字符，包括A(65)、B(66)、C(67)

因此，我只需声明任何足够大的大小来表示第二个维度中的 'A'、'B'、'C' （这意味着实际上 100 已经足够了，但我没有考虑那么多，声明 500，因为它们在顺序上几乎相同）

所以你问 DP [3] [1] 是什么意思，这意味着当第二维度为 1 时，我不需要 / 计算第二维度。（或者可以认为状态 dp(3,1) 在我们的问题中没有任何物理含义）

事实上，我总是使用 65、66、67。 因此，DP [3] [65] 表示长度为 3 且以 char(65) = 'A' 结尾的路径数。

我认为我理解了这种方法：以A结尾的路径数等于以B或C结尾的长度为l-1的路径数，以此类推。但是dp[500][500]信息存储的是什么 - dp[3][1]代表什么意思？ - Simple Learner
明白了。那么只是为了理解，DP数组只使用dp[x][65]、dp[x][66]和dp[x][67]（其中0<=x<500）吗？有趣。 - Simple Learner
是的，你说得对。所以对于更大的x，你需要增加第一维的大小。当然，你可以始终将第二维改为尽可能小的3，并使用0、1、2来表示A、B、C。 - shole
由于问题的对称性，容易看出DP(n, 'B')= DP(n, 'C')。因此，公式可以简化为DP(n, 'A') = 2 * DP(n - 1, 'B'); DP(n, 'B') = DP(n - 1, 'A') + DP(n - 1, 'B');。 - salva
2
“诀窍在于不要尝试生成所有可能的序列，因为它们的数量呈指数级增长，所需的内存将会太大。”
“相反，让f(n)表示长度为n且以A开头和结尾的序列的数量，g(n)表示长度为n且以A开头但以B结尾的序列的数量。为了开始计算，显然f(1)=1，g(1)=0。对于n>1，我们有f(n)=2g(n-1)，因为倒数第二个字母将是B或C，而每种情况的数量相等。我们还有g(n)=f(n-1)+g(n-1)，因为如果一个序列以A开头且以B结尾，则倒数第二个字母是A或C。”
“这些规则允许您使用记忆化快速计算这些数字。”
我也想点赞这个答案，但我没有足够的声望，抱歉 :(. 这个解释非常简明扼要，帮助我理解了另一个答案。 - Simple Learner
@SimpleLearner 不用担心。我很高兴你找到了答案 :) 这个问题存在一个简单的公式。计算前六个数字的f(n)，将它们输入到整数序列在线百科全书中，就会出现一个公式。 - Paul Boddington
哇，那绝对是太棒了。显然方程式是(1-x)/(1 - x - 2*x^2)。而且列出来的是：“从三角形的同一顶点开始和结束的闭合行走”。现在要弄清楚他们是如何找到这个的！ - Simple Learner
1
@SimpleLearner，“该方程”是适当初始条件下，方程a_{n+2} = a_{n+1} + 2a_{n}的递推关系的生成函数。 - Paul Hankin
0

我们可以使用 for 循环来解决这个问题，尽管 Anonymous 描述了一个闭合形式。

function f(n){
  var as = 0, abcs = 1;

  for (n=n-3; n>0; n--){
    as = abcs - as;
    abcs *= 2;
  }

  return 2*(abcs - as);
}

这就是原因：
Look at one strand of the decision tree (the other one is symmetrical):

                                        A

                  B                                            C...
     A                        C
B         C               A        B
A    C    A    B          B   C    A   C
B C  A B  B C  A C        A C A B  B C A B


Num A's     Num ABC's (starting with first B on the left)
0            1
1 (1-0)      2
1 (2-1)      4
3 (4-1)      8
5 (8-3)      16
11 (16-5)    32

Cleary, we can't use the strands that end with the A's...
0
你可以编写一个递归的暴力解决方案，然后进行记忆化处理（即自顶向下的动态规划）。递归解决方案更直观且更容易想出。以下是我的版本：
# search space (we have triangle with nodes)
nodes = ["A", "B", "C"]

@cache  # memoize!
def recurse(length, steps):
    # if length of the path is n and the last node is "A", then it's 
    # a valid path and we can count it.
    if length == n and ((steps-1)%3 == 0 or (steps+1)%3 == 0):
        return 1
    
    # we don't want paths having len > n.
    if length > n:
        return 0
    
    # from each position, we have two possibilities, either go to next
    # node or previous node. Total paths will be sum of both the
    # possibilities. We do this recursively.
    return recurse(length+1, steps+1) + recurse(length+1, steps-1)
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接