需要帮助与算法找到DAG中的最大路径 [英] Need assistance with algorithm to find the maximum path in a DAG

问题描述

假设我有这个定向非循环图（DAG），其中存在有向边每个节点（底行中的节点除外）到其下的两个节点：

Suppose I had this Directed Acyclic Graph (DAG), where there is a directed edge from each node (other than the nodes in the bottom row) to the two nodes below it:

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

我需要找到一个通过这个DAG的路径，其中节点的权重的和被最大化。您只能从该树中的节点的左下角或右下角进行对角线移动。因此，例如，7,3,8,7,5将给出该树中的最大路径。

I need to find a path through this DAG where the sum of the nodes' weights is maximized. You can only move diagonally down-left or down-right from a node in this tree. So for example, 7, 3, 8, 7, 5, would give the maximum path in this tree.

输入文件包含以此方式格式化的DAG

The input file contains the DAG formatted in this way

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

我的问题是，什么算法最适合找到最大路径，以及这个树在C ++中如何表示？

My question is, what algorithm would be best to find maximum path and also how would this tree be represented in C++?

节点

推荐答案

我会用 int s。

从底部一行开始，比较每个被分配的数字对。取较大的一个，并将其添加到对上方的数字：

Start at the bottom row and compare each adjanced pair of numbers. Take the bigger one and add it to the number above the pair:

 5 3             13  3
  \
7 8 6  becomes  7  8  6
^ ^

                  13 3               13 11
                     /
Next iteration   7  8  6   becomes  7  8  6  etc.
                    ^  ^

以你的方式到顶部，当你完成后，将包含最大的金额。

Work your way to the top and when you're done, the tip of the triangle will contain the largest sum.

这篇关于需要帮助与算法找到DAG中的最大路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！