具有节点和边权重的图中的最佳路径
Optimal Path in a Graph with Node and Edge Weights
考虑以下具有节点和边权重的有向图。
是否有非NP-Hard算法找出最大分数的路径，其中
score = sum(node weights) - sum(edge weights)
对于示例图，最大分数路径是沿着路径 A -> B -> C -> D。最大分数为 164 ((77 + 27 + 32 + 84) - (44 + 12 + 0)) .
我认为没有任何算法可以在多项式时间内找到解决方案，我试图证明这个问题是 NP-Hard 因为我们可以将它减少到 the longest path problem 并且最长路径问题可以简化为它。
这是我的尝试（假设边和节点权重均为正）：
- 从本题还原为最长路径问题：
通过将每个节点 A 拆分为两个节点 A-IN 和 A-OUT，可以将此问题简化为最长路径问题，这样这些节点就没有任何权重，我们 link 到 A 的入边到 A-IN，从 A 到 A-OUT 的出边，并在 A-IN 和 A-OUT 之间添加一条边，其权重等于节点 A 的 -1 倍原始重量。现在要找到问题的解决方案，您必须在此图中找到最长的路径。
- 从最长路径问题还原到本题（这里我也不确定自己有没有做错）：
最长路径问题可以通过取两个节点A和B之间的每条负权重边E并在其中间创建一个虚拟节点AB来简化为这个问题，我们从图中删除E然后添加一条边从 A 到 AB 的权重为 0，从 AB 到 B 的边的权重为 0，并赋予节点 AB 权重等于 -1 乘以原始 E 的权重。
因此，这有望证明您可以通过将最长路径问题简化为您的问题来解决最长路径问题，因此如果您的问题有多项式时间解决方案，那么 P = NP。
考虑以下具有节点和边权重的有向图。
是否有非NP-Hard算法找出最大分数的路径，其中
score = sum(node weights) - sum(edge weights)
对于示例图，最大分数路径是沿着路径 A -> B -> C -> D。最大分数为 164 ((77 + 27 + 32 + 84) - (44 + 12 + 0)) .
我认为没有任何算法可以在多项式时间内找到解决方案，我试图证明这个问题是 NP-Hard 因为我们可以将它减少到 the longest path problem 并且最长路径问题可以简化为它。
这是我的尝试（假设边和节点权重均为正）：
- 从本题还原为最长路径问题：
通过将每个节点 A 拆分为两个节点 A-IN 和 A-OUT，可以将此问题简化为最长路径问题，这样这些节点就没有任何权重，我们 link 到 A 的入边到 A-IN，从 A 到 A-OUT 的出边，并在 A-IN 和 A-OUT 之间添加一条边，其权重等于节点 A 的 -1 倍原始重量。现在要找到问题的解决方案，您必须在此图中找到最长的路径。
- 从最长路径问题还原到本题（这里我也不确定自己有没有做错）：
最长路径问题可以通过取两个节点A和B之间的每条负权重边E并在其中间创建一个虚拟节点AB来简化为这个问题，我们从图中删除E然后添加一条边从 A 到 AB 的权重为 0，从 AB 到 B 的边的权重为 0，并赋予节点 AB 权重等于 -1 乘以原始 E 的权重。
因此，这有望证明您可以通过将最长路径问题简化为您的问题来解决最长路径问题，因此如果您的问题有多项式时间解决方案，那么 P = NP。