最长路径三角形

Question

我有一个有两百行的三角形，需要找到从三角形顶部到底部的最大距离。

   5
  9 8
 5 4 6
9 7 3 4

在这里，最短的距离将是5+8+4+3=20。最长的距离将是5+9+5+9=28。

我对要实现的算法有一个很好的想法，但我正在努力将其转化为代码。

我的计划是：从倒数第二行开始，添加自底部行可能路径的最大值，并向上迭代。

例如，上述三角形将变为：

   28
  23 19
 14 11 10
9 7 3 4

这比暴力破解要高效得多，但我有两个普遍的问题：

1. Using brute-force, how do I list all the possible paths from top to bottom (can only move to adjacent points)? I tried using this (triangle is the list of lists containing the triangle):

   points=list(itertools.product(*triangle))  
   

   but this contains all possible combinations from each row, not just adjacent members. Project Euler #18 - how to brute force all possible paths in tree-like structure using Python? This somewhat explains a possible approach, but I'd like to use itertools and any other modules (as pythonic as possible)

2. How would I go about iterating the strategy of adding each maximum from the previous row and iterating to the top? I know I have to implement a nested loop:

   for x in triangle:
       for i in x:
           i+=? #<-Not sure if this would even increment it
   
   edit:
   what I was thinking was:
   triangle[y][x] = max([triangle[y+1][x],triangle[y+1][x+1]])
   

- Noob Coder

Answer 1

回答你的第一个问题（如何强制迭代所有路径）：如果您从三角形的顶部开始沿着某条随机路径向下移动，您必须决定每一级向左还是向右前进。因此，不同路径的数量为2^(nrows-1)。对于您的200行问题，有8e59种不同的路径，太多了，无法用暴力方法检查。

对于小三角形，您仍然可以以暴力方式迭代所有可能的路径，例如像这样：

In [10]: from itertools import product
In [11]: triangle = [[5], [9,8], [5,4,6], [9,7,3,4]]
In [12]: for decisions in product((0,1), repeat = len(triangle)-1):
    ...:     pos = 0
    ...:     path = [triangle[0][0]]
    ...:     for lr, row in zip(decisions, triangle[1:]):
    ...:         pos += lr # cumulative sum of left-right decisions
    ...:         path.append(row[pos])
    ...:     print path

[5, 9, 5, 9]
[5, 9, 5, 7]
[5, 9, 4, 7]
[5, 9, 4, 3]
[5, 8, 4, 7]
[5, 8, 4, 3]
[5, 8, 6, 3]
[5, 8, 6, 4]

这个方法的实现是使用 itertools.product 来遍历所有可能的 nrows-1 左/右决策的组合，其中 0 表示向左走，1 表示向右走（因此你更或多少生成了所有二进制数字的位数达到 2^(nrows-1)）。如果你将三角形存储为一个列表的列表，则向左走意味着在下一行保持相同索引，而向右走则意味着加 1。为了跟踪行中的位置，因此您只需计算所有左/右决策的累积总和。

回答您的第二个问题：首先，您的算法似乎相当不错，只需要反向迭代所有行一次，并且您不需要像暴力解决方案那样检查指数数量的情况。我唯一要添加的是建立一个新的三角形，在每个步骤中指示最大值是在左侧还是右侧找到的。这对于之后重构最优路径很有用。所有这些都可以这样实现：

mx = triangle[-1] # maximum distances so far, start with last row
directions = [] # upside down triangle with left/right direction towards max
for row in reversed(triangle[:-1]): # iterate from penultimate row backwards
    directions.append([l < r for l, r in zip(mx[:-1], mx[1:])])
    mx = [x + max(l, r) for x, l, r in zip(row, mx[:-1], mx[1:])]
    print 'Maximum so far:', mx
print 'The maximum distance is', mx[0]
directions.reverse()
pos = 0
path = [triangle[0][0]]
for direction, row in zip(directions, triangle[1:]):
    pos += direction[pos]
    path.append(row[pos])
print 'The optimal path is', path

与之前一样，我使用了技巧False = 0和True = 1来表示向左和向右。 使用与之前相同的三角形，结果如下：

Maximum so far: [14, 11, 10]
Maximum so far: [23, 19]
Maximum so far: [28]
The maximum distance is 28
The optimal path is [5, 9, 5, 9]

- Bas Swinckels

Answer 2

它没有使用itertools，而是使用递归，但我会记忆化结果，所以它仍然很快...

def memoize(function):
    memo = {}
    def wrapper(*args):
      if args in memo:
        return memo[args]
      else:
        rv = function(*args)
        memo[args] = rv
        return rv
    return wrapper



@memoize
def getmaxofsub(x, y):
    if y  == len(triangle) or x>y: return 0
    #print x, y
    return triangle[y][x] + max(getmaxofsub(x, y+1), getmaxofsub(x+1, y+1))


getmaxofsub(0,0)

我读了你的算法建议几遍，你的“累积三角形”存储在memoized装饰器的memo中，所以最终两者非常相似。如果你想防止递归“向下调用”过程中出现大堆栈，可以通过自下而上地调用getmaxofsub()来填充memoize的缓存。

for i in reversed(range(len(triangle))):
    getmaxofsub(0, i), getmaxofsub(i//2, i), getmaxofsub(i, i)

print getmaxofsub(0,0)

编辑：

编辑

getmaxofsub: 这个函数如何工作？首先，你需要知道，你不能把你的三角形分成子三角形。我以你的三角形为例：

   5
  9 8
 5 4 6
9 7 3 4

这是完整的内容。峰值的“坐标”为x=0，y=0。

现在我提取峰值x=0，y=1的子三角形：

  9
 5 4
9 7 3

或者 x=1，y=2。

 4
7 3

这是我的算法如何工作的：整个三角形的顶点（x=0，y=0）询问其子三角形（x=0，y=1）和（x=1，y=1），“你们距离地面的最大距离是多少？”每个子三角形都会询问其子三角形，依此类推...直到函数到达地面/y==len(triangle)为止：地面条目想要询问其子三角形，但由于没有这些，它们得到答案0。在每个三角形调用其子三角形之后，它决定哪一个更大，加上它们自己的值并返回这个总和。

现在您看到了这种算法的原理。这些算法称为递归算法。您可以看到，函数调用自身是相当标准的...而且它起作用...

所以，如果你考虑整个算法，你会发现许多子三角形被多次调用并询问它们的子三角形等等...但每次它们返回相同的值。这就是我使用 memorize 装饰器的原因：如果一个函数使用相同的参数 x 和 y 被调用，装饰器会返回这些参数的上次计算值，并防止耗时的计算... 这是一个简单的缓存机制...

这就是为什么这个函数像递归算法一样容易实现，像迭代算法一样快速...

- koffein