我有这个 DAG（它类似于二叉树，但它是一个图。有这个指定的名称吗？）：
（每个数字是一个节点，节点中的数字例如，程序应该以随机数运行）
它表示为列表列表：
[[1],[2,3],[4,5,6]]
我必须尽可能以更实用的方式找到最大化节点总和的路径：
[1,3,6]
我已经搜索过，这与 projecteuler #18 非常相似，但是 project euler 询问路径的孔总和，在我的作业中，我不仅要找到总和，还要找到所有节点。我试图为我的问题调整一些非常好的解决方案，但我没有成功。一些忠告？
看起来像是最长路径问题的变体。您需要将节点值视为边权重。
据我了解您的问题，该级别的深度为 n 和等级为 r 的节点将连接到等级为 r 和 r+1 的等级为 n+1 的节点。
直接路径当然是使用一些搜索功能来寻找一些递归关系，该搜索功能将您的一个 dag 作为输入。您当然可以从寻找最大权重开始，当这可行时，构建节点列表也不应该是一个大问题。
我让它按照这条路径工作，我使用的代码和测试集如下......但我删除了最有趣的部分以避免破坏主题。如有必要，我可以给你更多提示。那只是为了让你开始。
import unittest
def weight(tdag, path):
return sum([level[p] for p, level in zip(path,tdag)])
def search_max(tdag):
if len(tdag) == 1:
return (0,)
if len(tdag) > 1:
# recursive call to search_max with some new tdag
# when choosing first node at depth 2
path1 = (0,) + search_max(...)
# recursive call to search_max with some new tdag
# when choosing second node at depth 2
# the result path should also be slightly changed
# to get the expected result in path2
path2 = (0,) + ...
if weigth(tdag, path1) > weigth(tdag, path2):
return path1
else:
return path2
class Testweight(unittest.TestCase):
def test1(self):
self.assertEquals(1, weight([[1]],(0,)))
def test2(self):
self.assertEquals(3, weight([[1], [2, 3]],(0, 0)))
def test3(self):
self.assertEquals(4, weight([[1], [2, 3]],(0, 1)))
class TestSearchMax(unittest.TestCase):
def test_max_one_node(self):
self.assertEquals((0,), search_max([[1]]))
def test_max_two_nodes(self):
self.assertEquals((0, 1), search_max([[1], [2, 3]]))
def test_max_two_nodes_alternative(self):
self.assertEquals((0, 0), search_max([[1], [3, 2]]))
def test_max_3_nodes_1(self):
self.assertEquals((0, 0, 0), search_max([[1], [3, 2], [6, 4, 5]]))
def test_max_3_nodes_2(self):
self.assertEquals((0, 0, 1), search_max([[1], [3, 2], [4, 6, 5]]))
def test_max_3_nodes_3(self):
self.assertEquals((0, 1, 1), search_max([[1], [2, 3], [4, 6, 5]]))
def test_max_3_nodes_4(self):
self.assertEquals((0, 1, 2), search_max([[1], [2, 3], [4, 5, 6]]))
if __name__ == '__main__':
unittest.main()
我不知道这是否算作“尽可能实用的方式”，但它是一个很好、干净、可行的解决方案。希望能帮助到你！
import random
class Tree(object):
def __init__(self, depth=5, rng=None, data=None):
super(Tree,self).__init__()
if data is None: # generate a random tree
if rng is None:
_ri = random.randint
rng = lambda:_ri(1,20)
self.tree = [[rng() for i in range(d+1)] for d in range(depth)]
else: # copy provided data
self.tree = [row[:] for row in data]
def copy(self):
"Return a shallow copy"
return Tree(data=self.tree)
def maxsum(self):
"Find the maximum achievable sum to each point in the tree"
t = self.tree
for row in range(1,len(t)):
t[row][0] += t[row-1][0]
for i in range(1,row):
t[row][i] += max(t[row-1][i-1], t[row-1][i])
t[row][row] += t[row-1][row-1]
return self
def maxpath(self):
"""Find the path (list of per-level indices)
which leads to the greatest sum at the bottom of the tree.
Note: only makes sense when applied to a summed tree.
"""
t = self.tree
maxval = max(t[-1]) # find highest value in last row
maxi = t[-1].index(maxval)
path = [maxi]
for row in range(len(t)-2, -1, -1): # work backwards to discover how it was accumulated
if maxi==0:
maxi = 0
elif maxi==row+1:
maxi = row
elif t[row][maxi-1] > t[row][maxi]:
maxi -= 1
path.append(maxi)
path.reverse()
return path
def pathvalues(self, path):
"Return the values following the given path"
return [row[i] for row,i in zip(self.tree,path)]
def __str__(self, width=2):
fmt = '{0:>'+str(width)+'}'
return '\n'.join(' '.join(fmt.format(i) for i in row) for row in self.tree)
def solve(self, debug=False):
copy = self.copy()
maxpath = copy.maxsum().maxpath()
origvalues = self.pathvalues(maxpath)
sumvalues = copy.pathvalues(maxpath)
if debug:
print 'Original:'
print self, ' ->', origvalues
print 'Tree sum:'
print copy, ' ->', sumvalues
return origvalues
def main():
tree = Tree(data=[[1],[2,3],[4,5,6]])
solution = tree.solve(debug=True)
if __name__=="__main__":
main()
结果是
Original:
1
2 3
4 5 6 -> [1, 3, 6]
Tree sum:
1
3 4
7 9 10 -> [1, 4, 10]
返回的解决方案是 [1,3,6]。