algorithm - 寻找 "positive cycle"

Question

假设我们 E 是一个 nxn 矩阵，其中 E[i,j] 表示从货币 i 到货币 j 的汇率。 (1个货币i可以得到多少货币j)。 (注意，E[i,j]*E[j,i] 不一定为 1)。

想出一个算法来找到一个正循环(如果存在的话)，其中正循环定义为:如果你从第 i 种货币开始，你可以继续交换货币，这样最终你可以回来并拥有超过1 种货币 i.

---

这个问题我想了好久，但好像想不通。我唯一能想到的就是将所有内容表示为一个有向图，其中矩阵 E 作为邻接矩阵，其中 log(E[i,j]) 是顶点 i 和 j 之间的权重。然后你会寻找一个带有负面路径或其他东西的循环。这有意义吗？有没有更有效/更简单的方法来思考这个问题？

Answer 1

首先，记录汇率(这不是绝对必要的，但这意味着我们可以像往常一样谈论“增加长度”)。然后您可以对 Floyd-Warshall algorithm 进行轻微修改。找到每对顶点之间至少与最长的顶点一样长的可能不简单路径的长度(即可能在不同位置多次循环自身的路径)它们之间的简单路径。唯一需要的改变是翻转比较的符号，这样我们总是寻找最长路径(更多细节见下文)。最后，您可以查看所有 O(n^2) 对顶点 u 和 v，取每个方向(从 u 到 v，以及从 v 到 u)的 2 条路径的长度之和。如果其中任何一个大于 0，那么您已经找到了一个(可能是非简单的)循环，其总汇率 > 1。总体而言，算法的 FW 部分占主导地位，使得这个 O(n^3) -时间。

一般来说，尝试使用像 FW 这样的算法来寻找最大权重路径的问题在于，它可能会将共享一个或多个顶点的 2 个子路径连接在一起，而我们通常不会这样做想要这个。 (在没有负环的图中寻找最小长度路径时永远不会发生这种情况，因为这样的路径必然包含可以删除的正权重环，所以它永远不会被选为最优。)如果我们正在寻找最大-权重简单循环，这将是一个问题；在那种情况下，为了解决这个问题，我们需要为顶点的每个子集考虑一个单独的子问题，这会将时间和空间复杂度推高至 O(2^n)。然而，幸运的是，我们只关心找到一些正权重循环，并且很容易看出如果 FW 找到的路径碰巧多次使用某个顶点，那么它必须包含一个非负权重循环——它可以被删除(如果它的权重为 0)，或者(如果它的权重 > 0)本身就是一个“正确答案”!

如果您关心找到一个简单的循环，这很容易在最后一步中完成，该步骤与 FW 报告的路径长度成线性关系(顺便说一句，可能是 O(2^|V|) -- 如果所有路径都具有正长度，那么所有“最佳”长度将随着每次最外层迭代而加倍——但这不太可能发生在这里)。取 FW 结果隐含的最优路径对(每条路径可以用通常的方式计算，通过为每个顶点对 (i, j) 保留一个 k 的“最优前驱”值表)，然后简单地沿着它走，分配给您访问的每个顶点到目前为止的运行总长度，直到您遇到您已经访问过的顶点。此时，要么currentTotal - totalAtAlreadyVisitedVertex > 0，在这种情况下你刚刚找到的循环具有正权重并且你已经完成，或者这个差异为0，在这种情况下你可以删除对应的边从路径到这个循环并照常继续。