c++ - 有趣的问题(货币套利)

Question

套利是利用货币兑换值(value)的差异来赚取利润的过程。
考虑一个人，他从一定数量的货币 X 开始，经过一系列的交换，最后得到了更多的 X(比他最初拥有的)。
给定 n 种货币和一张 (nxn) 汇率表，设计一个算法，假设一个人不会多次进行一次兑换，他应该使用该算法来获得最大利润。

我想到了这样的解决方案:

1. 使用修改后的 Dijkstra 算法查找单源最长产品路径。
2. 这给出了从源货币到其他货币的最长产品路径。
3. 现在，遍历其他货币并乘以迄今为止的最大乘积，w(curr,source)(边到源的权重)。
4. 选择所有此类路径中的最大值。

虽然这看起来不错，但我仍然怀疑这个算法的正确性和问题的完整性。(即问题是 NP-Complete 吗？)因为它有点类似于旅行商问题。

寻找您对此问题的意见和更好的解决方案(如果有的话)。

谢谢。

编辑:
谷歌搜索这个话题把我带到了这个 here ，其中套利检测已经解决，但最大套利的交易所没有。这可以作为引用。

Answer 1

此处不能使用 Dijkstra，因为无法修改 Dijkstra 以返回最长路径，而不是最短路径。一般来说，longest path problem正如您所怀疑的那样，实际上是 NP 完全的，并且与您建议的旅行商问题有关。

您正在寻找的(如您所知)是一个边权重的乘积大于 1 的循环，即 w₁ * w₂ * w₃ * ... > 1. 如果我们取双方的对数，我们可以重新设想这个问题，把它变成一个总和而不是一个乘积:

log (w₁ * w₂ * w₃ ... ) > log(1)

=> log(w₁) + log(w₂) + log(w₃) ... > 0

如果我们取负数...

=> -log(w₁) - log(w₂) - log(w₃) ... < 0 (注意不等式翻转)

所以我们现在只是在图中寻找负循环，这可以使用 Bellman-Ford 算法(或者，如果您不需要知道路径，则使用 Floyd-Warshall 算法)来解决

首先，我们变换图形:

for (int i = 0; i < N; ++i)
  for (int j = 0; j < N; ++j)
    w[i][j] = -log(w[i][j]);

然后我们执行标准的 Bellman-Ford

double dis[N], pre[N];

for (int i = 0; i < N; ++i)
   dis[i] = INF, pre[i] = -1;

dis[source] = 0;

for (int k = 0; k < N; ++k)
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j)
      if (dis[i] + w[i][j] < dis[j])
        dis[j] = dis[i] + w[i][j], pre[j] = i;

现在我们检查负循环:

for (int i = 0; i < N; ++i)
  for (int j = 0; j < N; ++j)
    if (dis[i] + w[i][j] < dis[j])
      // Node j is part of a negative cycle

然后您可以使用 pre 数组来查找负循环。从 pre[source] 开始，然后返回。