我有一个包含500个顶点的全连通图（无向）。这将导致一个矩阵，其中包含250,000个条目（只有125,000个是必要的，因为它是无向的）。
每条边都有特定的权重。如果我只能访问n个顶点，其中n < 500，是否可以找到哪个起始顶点和哪条路径会产生最高的总权重。
在合理的时间内解决这个问题是否可能？
谢谢！
每条边都有特定的权重。如果我只能访问n个顶点，其中n < 500，是否可以找到哪个起始顶点和哪条路径会产生最高的总权重。
在合理的时间内解决这个问题是否可能？
谢谢！
1个回答
3
您所描述的问题最终会变成NP难问题（通过从最长路径问题进行约简），因此除非P = NP，否则不会有任何算法对所有输入都正确且高效。 您要么需要愿意接受并非总是正确（但可能近似接近）的答案，要么需要考虑在某些情况下快速但在其他情况下相当缓慢的算法。
有一些算法可以很好地解决这个问题，只要路径不太长。例如，颜色编码算法在最大路径长度不太长的情况下效果很好，但我担心长度为500在这里会太大。一个快速的谷歌搜索找到了这篇论文，其中包含一种在图中找到相当长路径的算法，可能适用于这里。 但是，除此之外，您可能需要进行一些随机采样，并希望一切顺利。
如果你对图有更多了解，例如边遵循三角不等式或者边的值都在某个小有限范围内，那么你可能能够使用其他方法。但是除此之外，恐怕你没有太多可选项。
抱歉，希望这可以帮到你！
有一些算法可以很好地解决这个问题，只要路径不太长。例如，颜色编码算法在最大路径长度不太长的情况下效果很好，但我担心长度为500在这里会太大。一个快速的谷歌搜索找到了这篇论文，其中包含一种在图中找到相当长路径的算法，可能适用于这里。 但是，除此之外，您可能需要进行一些随机采样，并希望一切顺利。
如果你对图有更多了解，例如边遵循三角不等式或者边的值都在某个小有限范围内，那么你可能能够使用其他方法。但是除此之外，恐怕你没有太多可选项。
抱歉，希望这可以帮到你！
- templatetypedef
1
谢谢！我就是这么想的。链接很棒！ - Zojirushi
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接