0

我被算法优化困住了。

目标是找出您可以使用多少种不同的方式从棋盘中的 A 点到 B 点，其中：

  • A是左下角的正方形。
  • B是右上角的正方形。
  • 棋子每转只能向上或向右移动一个。

这是一个虚拟解决方案：

# -*- conding: utf-8 -*-
import time

def solution(n, m, x, y):
   ret = 0
   if x < n-1:
      ret += solution(n, m, x+1, y)
   if y < m-1:
      ret += solution(n, m, x, y+1)
   if x == n-1 and  y == m-1:
     ret = 1
   return ret

def wrapper(n, m):
    start = time.time()
    reponse = solution(n, m, 0, 0)
    stop = time.time()
    print "Response: %dx%d = %d\nTime : %f\n" % (n, m, reponse, stop-start)



if __name__ == "__main__":
    for i in range(10):
        wrapper(i+1,i+1)
    #wrapper(7,7)
    #wrapper(10,10)
    #wrapper(100,100)
    #wrapper(1000,1000)
    #wrapper(10000,10000) <- way too slow

虽然我留在小棋盘上，但它工作得很好并且结果是相关的。但我的目标是为 10000x10000 板找到解决方案。

有什么男孩有想法吗？

4

4 回答 4

4

可以这样想：由于你的点 A 和 B 在同一个地方，你必须移动相同数量的 UP 和 RIGHT，但顺序会有所不同。所以你需要找到不同组合的数量。

于 2013-03-16T16:10:07.800 回答
2

动态规划：O(N)

它已经提到，该问题通过使用帕斯卡三角形及其与二项式系数的关系有一个解决方案。Catalan number的条目也很好地说明了n × n的情况。

n × n例

通过利用上述资源，您可以得出结论，对于大小为n × n的网格，您需要计算 C(2n - 2, n - 1)。您可以通过将网格旋转 45 度并映射帕斯卡三角形来仔细检查它。

实际上，直接计算这个数字需要以一种幼稚的方式计算最多 3 个不同的阶乘，这是一项非常昂贵的任务。如果你可以预先计算它们，那么这里就没有讨论了，你可以说这个问题的复杂度为 O(1)。如果您对预先计算的方式不感兴趣，那么您可以继续阅读。

您可以使用动态规划 (DP) 来计算这样的不祥数字。这里的诀窍是以更小的步骤执行操作，这根本不需要您计算大的阶乘数。

也就是说，要计算 C(n, k)，您可以先将自己置于 C(n, 1) 处，然后步行到 C(n, k)。让我们首先根据 C(n, k - 1) 定义 C(n, k)。

C(n, k) = n! / k! * ( n - k )!                            ; k! = (k - 1)! * k
        = n! / (k - 1)! * k * (n - k)!                    ; (n - k)! = (n - k + 1)! / (n - k + 1)
        = n! * (n - k + 1) / (k - 1)! * k * (n - k + 1)!  ; C(n, k - 1) = n! / (k - 1)! * ( n - k + 1 )!
        = C(n, k - 1) * (n - k + 1) / k

基于此，您可以在 Python 中定义一个计算 C(n, k) 的函数，如下所示：

def C(n, k):
    """
    Calculate C(n, k) using Dynamic Programming.
    C(n, k) = C(n, k - 1) * (n - k + 1) / k
    """
    C = 1
    for ki in range(1, k + 1):
        C = C * (n - ki + 1) / ki
    return C

它以线性时间运行，O(N)。

对于n × n情况，您需要计算 C(2n - 2, n - 1)。

>> print "Response: %dx%d = %d" % (n, n, C(2 * n - 2, n - 1),)
Response: 10000x10000 = 5...

n × m情况

对于一般的n × m情况，您只需要计算 C(n + m - 2, m - 1)。

>> print "Response: %dx%d = %d" % (n, m, C(n + m - 2, m - 1),)
Response: 10000x10000 = 5...

最后但并非最不重要的一点是，您可以在此处查看 Ideone 的实时示例。

计时

我针对以下网格大小运行了算法。

      N x N      | Response's Length |   Time
-----------------+-------------------+-----------
      1 x 1      |           1 chars |  0.000001
     10 x 10     |           5 chars |  0.000004
    100 x 100    |          59 chars |  0.000068
   1000 x 1000   |         600 chars |  0.002207
  10000 x 10000  |        6018 chars |  0.163647
 100000 x 100000 |       60203 chars | 40.853971

由于涉及的数量非常多，似乎超过 100 000 x 100 000 网格大小的操作变得异常昂贵。不过没什么好惊讶的。

于 2013-03-16T23:36:48.103 回答
1

您不需要为此使用算法。只是数学。这是需要考虑的事情：当您在右上角时，您没有任何不同的选择。让我们把它算为零。当你在右上角时，你唯一的选择就是向右走（一个选项），因为你不能回溯。当您位于右上角的下方时，您唯一的选择就是向上。让我们把它映射出来

... 1 0
..... 1

目标角向左/向下的角呢？从那里，有两条路到拐角处（到达邻居的选项总和）：您可以向右走：

... 1 0
....2 1

扩展我们总是用边缘扩展的边缘：一旦你在顶部，只有一种方法可以到达右上角：

...1 1 1 0
...... 2 1
........ 1
........=1

但是每个非边缘选择都是北部和东部邻居的数字之和：

...1 1 1 0
.....3 2 1
.......3 1
........ 1

等等。希望这能让您开始解决问题。

对此也有不同的思考方式。给定一个 NxN 棋盘，您必须进行 2N 次移动才能从一个角移动到另一个角。这些移动中的 N 个是向北移动，N 个是向东移动。问题是：在一个 2N 长的字符串中，可以有多少种不同的 N 东移和 N 北移组合。

于 2013-03-16T16:11:42.723 回答
0

您正在寻找帕斯卡三角形。维基百科链接甚至提到了你的确切问题

于 2013-03-16T16:52:49.703 回答