我有一个DAG(它类似于二叉树,但它是一个图。。是否有指定的名称?):
(每个数字是一个节点,节点中的数字是例如,程序应该以随机数运行)
它表示为列表列表:
[[1],[2,3],[4,5,6]]
我必须尽可能以更实用的方式找到使节点总数最大化的路径:
^{pr2}$
我已经搜索过了,这与projecteuler#18非常相似,但是projecteuler要求路径的洞和,在我的作业中,我不仅要找到求和,而且要找到所有节点。
我试着用一些非常好的方法来解决我的问题,但没能成功。
有什么建议吗?在
Tags:
我不知道这是一个更好的解决方案,但我知道这是一个更好的解决方案。希望有帮助!在
结果
^{pr2}$返回的解为[1,3,6]。在
看起来像是longest path problem上的变体。需要将节点值视为边权重。在
正如我所理解的问题,深度n和秩r在该级别的节点将连接到级别为r和r+1的n+1节点。在
直接的方法当然是使用某种搜索函数来寻找一些递归关系,这个函数将把你的一个dag作为输入。当然,您可以从查找最大权重开始,这样做的时候,构建节点列表应该不是什么大问题。在
我让它沿着这条路径工作,代码和我使用的测试集如下。。。但我去掉了最有趣的部分以避免破坏主题。如果需要的话,我可以再给你一些提示。那只是为了让你开始。在
相关问题 更多 >
编程相关推荐