在全连接图中寻找最佳路径
Finding best paths in a fully connected graph
我有一个具有 500 个顶点的完全连接图（无向）。这会产生一个包含 250,000 个条目的矩阵（只需要 125,000 个条目，因为它是无向的）。
每条边都有特定的权重。如果我只能访问 n < 500 的 n 个顶点，是否有可能找到哪个起始顶点和哪条路径会导致最高的总权重。
这是否可以在任何合理的时间内解决？
谢谢！
您描述的问题最终成为 NP-hard（通过 longest path problem 的缩减），因此除非 P = NP，否则不会有任何算法对所有输入都是正确的并且对所有输入都有效。您要么需要愿意接受并非总是正确的答案（但可能大致接近），要么需要考虑在某些情况下速度很快但在其他情况下却很慢的算法。
有一些算法可以很好地解决这个问题，只要路径不太长。 color-coding algorithm, for example, works well if the maximum path length isn't too long, but I'm concerned that length 500 is going to be way too large here. A quick Google search turned up this paper，其中包含用于在图中查找合理长路径的算法，可能适用于此处。但除此之外，您可能只需要进行一些随机抽样，并希望一切顺利。
如果您对图形了解更多 - 例如，如果边服从三角不等式或者如果边的值都在某个小的有限范围内 - 您也许可以使用其他方法。但除此之外，恐怕您不会有太多选择。
很抱歉，但希望这对您有所帮助！
我有一个具有 500 个顶点的完全连接图（无向）。这会产生一个包含 250,000 个条目的矩阵（只需要 125,000 个条目，因为它是无向的）。
每条边都有特定的权重。如果我只能访问 n < 500 的 n 个顶点，是否有可能找到哪个起始顶点和哪条路径会导致最高的总权重。
这是否可以在任何合理的时间内解决？
谢谢！
您描述的问题最终成为 NP-hard（通过 longest path problem 的缩减），因此除非 P = NP，否则不会有任何算法对所有输入都是正确的并且对所有输入都有效。您要么需要愿意接受并非总是正确的答案（但可能大致接近），要么需要考虑在某些情况下速度很快但在其他情况下却很慢的算法。
有一些算法可以很好地解决这个问题，只要路径不太长。 color-coding algorithm, for example, works well if the maximum path length isn't too long, but I'm concerned that length 500 is going to be way too large here. A quick Google search turned up this paper，其中包含用于在图中查找合理长路径的算法，可能适用于此处。但除此之外，您可能只需要进行一些随机抽样，并希望一切顺利。
如果您对图形了解更多 - 例如，如果边服从三角不等式或者如果边的值都在某个小的有限范围内 - 您也许可以使用其他方法。但除此之外，恐怕您不会有太多选择。
很抱歉，但希望这对您有所帮助！