2

我正在寻找一种算法，它采用有向加权图（具有正整数权重）并在图中找到具有最小平均权重（而不是总权重）的循环。

基于类似的问题（但对于总权重），我考虑应用 Floyd-Warshall 算法的修改，但它会依赖以下不成立的属性（感谢 Ron Teller 提供了一个反例来说明这一点）： “对于顶点 U,V,W，如果有从 U 到 V 的路径 p1,p2 和从 V 到 W 的路径 p3,p4，那么从 U 到 W 的这些路径的最佳组合是 p1 更好， p2 之后是 p3、p4 中的更好者。”

我可能会考虑哪些其他算法不依赖此属性？

编辑：将以下不再相关的段落移到问题下方。

虽然这个属性看起来很直观，但在两条同样可取的路径的情况下似乎并不成立。例如，如果 p1 的总重量为 2 和长度为 2，而 p2 的总重量为 3 和长度为 3，则没有一个比另一个更好。但是，如果 p3 和 p4 的总权重大于长度，则 p2 比 p1 更可取。在我想要的应用程序中，每条边的权重都是正整数，所以这个属性是强制的，我想我可以假设，在平局的情况下，更长的路径更好。但是，我仍然无法证明这是可行的，因此我无法验证任何依赖它的算法的正确性。

4

3 回答 3

2

“虽然这个属性看起来很直观，但在两条同样可取的路径的情况下似乎并不成立。”

实际上，当您考虑 2 个参数（重量、长度）时，它在任何情况下都不成立，这是一个示例，当 P1 本身的平均值小于 P2 时，对于最终解决方案有时可能更好（示例 1）或更糟（示例 2），取决于 P3 和 P4。

示例 1：

L(P1) = 9, W(P1) = 10
L(P2) = 1, W(P2) = 1
L(P3) = 1, W(P3) = 1
L(P4) = 1, W(P4) = 1

示例 2：

L(P1) = 9, W(P1) = 10
L(P2) = 1, W(P2) = 1
L(P3) = 5, W(P3) = 10
L(P4) = 5, W(P4) = 10

这两个参数对您的目标函数有影响，无法在本地确定，因此任何修改的 Floyd-Warshall 算法都将不起作用。

由于您只考虑循环，因此您可能需要考虑一种蛮力算法来验证图中每个循环的平均权重。您可以在多项式时间内完成，请参阅： Finding all cycles in graph

于 2013-10-18T06:41:28.867 回答
1

我可以建议另一种算法。

让我们修正 C。现在从所有权重中减去 C。答案会如何变化？如果我们从所有权重中减去相同的数字，那么每个周期的平均权重在相同的数字 C 上减少。现在让我们检查是否有负平均权重的周期。平均权重为负的条件等于权重为负的条件。所以检查我们是否有负权重的循环就足够了。我们可以使用Bellman-Ford 算法来做到这一点。如果我们有这样的循环，那么答案小于 C。

所以现在我们可以通过二分搜索找到答案。由此产生的复杂性将是 O(VE log(MaxWeight))

于 2013-10-18T16:08:22.630 回答
0

您描述的问题称为最小平均周期问题，可以有效解决。此外，如果您有兴趣，可以查看一些非常好的优化理论（从标准参考 AMO93 开始）。

于 2013-10-18T19:29:50.747 回答