algorithm - 采用权重最大的路径遍历图的复杂度

Question

我有一个图表，我想遍历图表（不必遍历所有顶点），总是走有重量的路径。我不能两次通过同一个顶点，如果我不能再做任何动作，我就会停下来。复杂性是什么？我假设它是“n”（其中 n 是顶点数），但我不确定。

Answer 1

如果您不能两次通过同一顶点，则边缘遍历的上限为 n。很容易想到紧密绑定的示例（例如连接的单个顶点链）。

但是，请记住，复杂性是针对给定算法的，而不是一般任务，您还没有描述您的算法或图表的组织方式，所以这个问题没有任何意义。

例如，如果图是一个集团，也许为每次遍历选择权重最高的边本身需要 n 个计算步骤（如果边保存在每个顶点中保存的未排序列表中），使得朴素算法 O(n^2)在这种情况下。其他表示可能具有不同的复杂性，但需要不同的算法。

编辑

如果您要查找总权重最大的路径（这可能需要您在某些遍历中选择没有最高权重的边），那么问题是 NP 难的。如果它有一个多项式算法，那么您可以采用未加权图并找到最长的路径（jimifiki 指出的已知 NP 难题），并用该算法解决它。

Answer 2

从最长路径问题

这个问题称为最长路径问题，是 NP 完全问题。