需要帮助设计一种算法来寻找有向无环图中的最大路径。

Question

假设我有一个有向无环图（DAG），其中每个节点（除了底层节点）都指向其下面的两个节点：

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

我需要找到一条路径，使得该有向无环图中节点权重之和最大。在这棵树中，你只能从一个节点斜向左下或右下移动。例如，7、3、8、7、5将给出这棵树的最大路径。

输入文件以以下方式格式化有向无环图：

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

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

节点权重为非负数。

- Steffan Harris

---

最大总和路径是什么？ - R. Martinho Fernandes

@HunterMcMillen 显然，这些数字相加得到最大值的路径。 - Seth Carnegie

我的意思是最大权重。7,3,8,7,5给出了最大的权重。我会把它改成权重。 - Steffan Harris

@HunterMcMillen 不，他的意思是 7, 3, 8, 7, 5 的总和比通过树的任何其他路径的数字的总和都要大。 - Seth Carnegie

就此图而言，它不是一棵树。树节点只有一个父节点。这种结构被称为有向无环图：有向是因为每条边都有方向，无环是因为没有回到一个节点的路径。 - kkm

Answer 1

我会使用一个 int 数组的向量来表示这个三角形。

从底部行开始，比较每一对相邻的数字。取其中较大的那个数字，并将其加到上面一行相应位置的数字中：

 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.
                    ^  ^

从底部开始向上逐层计算，当你完成时，三角形的顶端将包含最大的总和。

- jrok

---

这个动态规划解决方案简单而快速。这就是我如何解决欧拉计划＃18和＃67的问题。 - Blastfurnace

在第一个中间结果中，读取的应该是“3”而不是“11”，对吗？ - Alexandre Hamez

Answer 2

一个二维数组可以很好地解决这个问题。您可以通过使用广度优先遍历来处理，并使用每个节点的最大路径和标记每个访问过的节点。

例如：

• 只有从7开始才能到达7。
• 3被标记为10，8被标记为15。
• 8被标记为18（10+8），1被标记为11，然后替换为16，0被标记为15。

当叶节点被标记时，快速运行它们以查看哪个是最大的。然后，通过比较当前节点的权重、父节点的权重和边缘权重来开始回溯。

- user684934

Answer 3

剧透警告

如果你想自己解决这个问题，请不要阅读代码。

---

一种解决方法是将数据转换成树形结构（实际上是图），然后编写递归算法，通过将树缩小为更小的子树（直到只剩一个节点的树），并从那里开始向上移动，找到通过树的最大路径。

我非常喜欢递归算法和处理树形结构，所以我继续编写了一个程序来完成它：

#include <algorithm>
#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

struct node {
    node(int i, node* left = NULL, node* right = NULL) : data(i), left(left), right(right) { }

    node* left, *right;
    int data;
};

/*
      tree:

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

*/

std::vector<node*> maxpath(node* tree, int& sum) {
    if (!tree) {
        sum = -1;
        return std::vector<node*>();
    }

    std::vector<node*> path;

    path.push_back(tree);

    if (!tree->left && !tree->right) {
        sum = tree->data;
        return path;
    }

    int leftsum = 0, rightsum = 0;

    auto leftpath = maxpath(tree->left, leftsum);
    auto rightpath = maxpath(tree->right, rightsum);

    if (leftsum != -1 && leftsum > rightsum) {
        sum = leftsum + tree->data;
        copy(begin(leftpath), end(leftpath), back_inserter<vector<node*>>(path));
        return path;
    }

    sum = rightsum + tree->data;
    copy(begin(rightpath), end(rightpath), back_inserter<vector<node*>>(path));
    return path;
}

int main()
{
    // create the binary tree
    // yay for binary trees on the stack
    node b5[] = { node(4), node(5), node(2), node(6), node(5) };
    node b4[] = { node(2, &b5[0], &b5[1]), node(7, &b5[1], &b5[2]), node(4, &b5[2], &b5[3]), node(4, &b5[3], &b5[4]) };
    node b3[] = { node(8, &b4[0], &b4[1]), node(1, &b4[1], &b4[2]), node(0, &b4[2], &b4[3]) };
    node b2[] = { node(3, &b3[0], &b3[1]), node(8, &b3[1], &b3[2]) };

    node n(7, &b2[0], &b2[1]);

    int sum = 0;

    auto mpath = maxpath(&n, sum);

    for (int i = 0; i < mpath.size(); ++i) {
        cout << mpath[i]->data;
        
        if (i != mpath.size() - 1)
            cout << " -> ";
    }

    cout << endl << "path added up to " << sum << endl;
}

它打印出来了

7 -> 3 -> 8 -> 7 -> 5

路径加起来为30

- Seth Carnegie

---

那个解决方案效率太低了（指数复杂度与线性相比）。 - jpalecek

@jpalecek 哪一个是线性的？对我来说它并不太低效，也没有效率要求 :) 程序运行比我眨眼还快。我只是为了好玩而做，展示另一种方式，这个问题也只是为了好玩。 - Seth Carnegie

最高票答案（https://dev59.com/NGDVa4cB1Zd3GeqPZxaC#9154380）是线性的，以及Project Euler #18问题（https://dev59.com/DGsz5IYBdhLWcg3wR1zC）上的所有答案也是线性的。它是否比你眨眼间在高度为30的树上运行得更快？你可以随意编码，但这不是一个专业人士应该接受的事情。 - jpalecek

顺便说一句，稍加改动后，你的解决方案也将是线性的。这是反对接受指数解决方案的另一个观点。 - jpalecek

@jpalecek 我还没有在高度为30的树上测试过它，但我不需要这样做，因为这不适用于高度为30的树。请原谅我，我没有看到他是专业人士，而且解决他问题的方法是进入商业产品。我认为你的负评真的是多余的。你说“你可以随便编码”，但整个事情不就是为了好玩吗？我觉得你把这件事想得太严重了。 - Seth Carnegie

Seth，OP并没有说他“只是为了好玩”，也没有说他将使用高度<30的树，很可能他将使用更大的树。 OP还问道“哪种算法最好”，不幸的是，在大多数情况下，指数解决方案几乎无用，这就是为什么你的答案不是给出的问题的好答案。 - HexTree

Answer 4

最好的算法是

open the file,
set a counter to 0.
read each line in the file.
for every line you read,
   increment the counter.
close the file.
that counter is your answer.

表示树的最佳算法是什么都不做。因为你实际上并不需要树的表示。

- EvilTeach

---

最大负荷？那完全不同。 - EvilTeach