有趣的问题(货币套利)

Question

套利是利用货币兑换价值的差异来赚取利润的过程.
考虑一个以一定数量的货币X开头的人,经历一系列交易,最后得到更多的X(比他最初的那样).
给定n种货币和汇率表(nxn),设计一个人应该用来获得最大利润的算法,假设他没有多次执行一次交换.

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

1. 使用修改后的Dijkstra算法查找单源最长产品路径.
2. 这提供了从源货币到其他货币的最长产品路径.
3. 现在,迭代每个其他货币并乘以到目前为止的最大乘积w(curr,source)(边缘到源的权重).
4. 选择所有此类路径的最大值.

虽然这似乎很好,但我仍然怀疑这个算法的正确性和问题的完整性.(问题是NP-Complete？)因为它有点类似于旅行商问题.

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

谢谢.

编辑:
谷歌搜索这个主题带我到这里,在那里套利检测已经解决,但最大套利的交换不是.这可以作为参考.

Answer 1

Dijkstra不能在这里使用,因为没有办法修改Dijkstra来返回最长路径,而不是最短路径.一般来说,最长的路径问题实际上是您所怀疑的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 algorihtm)

首先,我们转换图表:

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]工作.

Answer 2

当目前只有大约150 种货币存在时,这是一个NP难问题的事实并不重要,我怀疑你的外汇经纪人最多只能让你交易20对.n因此,我的货币算法是:

1. 制作深度n和分支因子的树n.树的节点是货币,树的根是您的起始货币X.两个节点(货币)之间的每个链接都有权重w,即w两种货币之间的外汇汇率.
2. 在每个节点,您还应该存储累积的外汇汇率(通过将树中高于它的所有外汇汇率计算在一起来计算).这是根(货币X)与此节点的货币之间的外汇汇率.
3. 迭代表示货币的树中的所有节点X(也许您应该保留指向这些节点的指针列表以加速算法的这个阶段).只有n^n这些(在大O符号方面非常低效,但记住你n的大概是20).具有最高累积外汇汇率的汇率是您的最佳汇率和(如果是正值),这些节点之间通过树的路径表示以货币开始和结束的套利周期X.
4. 请注意,您可以修剪树(并因此从降低复杂性O(n^n),以O(n)通过以下步骤1生成的树时,这些规则:
   1. 如果到达货币节点X,请不要生成任何子节点.
   2. 要将分支因子从n1 减少到1,在每个节点处生成所有n子节点,并仅添加具有最大累积外汇率的子节点(当转换回货币时X).

Answer 3

恕我直言，这个问题有一个简单的数学结构，它适用于一个非常简单的 O(N^3) 算法。给定一个 NxN 的货币对表，如果不可能进行套利，该表的缩减行梯形形式应该只产生 1 个线性独立的行（即所有其他行都是第一行的倍数/线性组合）。

我们可以执行高斯消元并检查我们是否只得到 1 个线性独立的行。如果不是，额外的线性独立行将提供有关可用于套利的货币对数量的信息。