algorithm - 通过采用最大权重的路径遍历图形的复杂性

Question

我有一个图，我想遍历该图(不必遍历所有顶点)，始终采用权重最大的路径。我不能两次通过同一个顶点，如果我不能再移动了，我就会停下来。什么是复杂性？我假设它是“n”(其中 n 是顶点数)但我不确定。

Answer 1

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

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

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

编辑

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