C++ 有趣的问题（货币套利）

Interesting Problem (Currency arbitrage)

提问by sud03r

Arbitrage is the process of using discrepancies in currency exchange values to earn profit.
Consider a person who starts with some amount of currency X, goes through a series of exchanges and finally ends up with more amount of X(than he initially had).
Given n currencies and a table (nxn) of exchange rates, devise an algorithm that a person should use to avail maximum profit assuming that he doesn't perform one exchange more than once.

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

I have thought of a solution like this:

我想到了一个这样的解决方案：

1. Use modified Dijkstra's algorithm to find single source longest product path.
2. This gives longest product path from source currency to each other currency.
3. Now, iterate over each other currency and multiply to the maximum product so far, w(curr,source)(weight of edge to source).
4. Select the maximum of all such paths.

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

While this appears good, i still doubt of correctness of this algorithm and the completeness of the problem.(i.e Is the problem NP-Complete?) as it somewhat resembles the traveling salesman problem.

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

Looking for your comments and better solutions(if any) for this problem.

为这个问题寻找您的意见和更好的解决方案（如果有的话）。

Thanks.

谢谢。

EDIT:
Google search for this topic took me to this here, where arbitrage detection has been addressed but the exchanges for maximum arbitrage is not.This may serve a reference.

编辑：
谷歌搜索这个话题把我带到这里，这里已经解决了套利检测，但没有解决最大套利的交换。这可以作为参考。

回答by Peter Alexander

Dijkstra's cannot be used here because there is no way to modify Dijkstra's to return the longest path, rather than the shortest. In general, the longest path problemis in fact NP-complete as you suspected, and is related to the Travelling Salesman Problem as you suggested.

Dijkstra 不能在这里使用，因为无法修改 Dijkstra 以返回最长路径，而不是最短路径。一般来说，最长路径问题实际上是您怀疑的 NP 完全问题，并且与您建议的旅行商问题有关。

What you are looking for (as you know) is a cycle whose product of edge weights is greater than 1, i.e. w₁* w₂* w₃* ... > 1. We can reimagine this problem to change it to a sum instead of a product if we take the logs of both sides:

您正在寻找的（如您所知）是一个循环，其边权重的乘积大于 1，即 w ₁* w ₂* w ₃* ... > 1。我们可以重新想象这个问题，将其更改为总和如果我们取双方的日志，而不是产品：

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

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

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

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

And if we take the negative log...

如果我们取负对数......

=> -log(w₁) - log(w₂) - log(w₃) ... < 0 (note the inequality flipped)

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

So we are now just looking for a negative cycle in the graph, which can be solved using the Bellman-Ford algorithm (or, if you don't need the know the path, the Floyd-Warshall algorihtm)

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

First, we transform the graph:

首先，我们变换图：

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

Then we perform a standard Bellman-Ford

然后我们执行标准的 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;

Now we check for negative cycles:

现在我们检查负循环：

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

You can then use the prearray to find the negative cycles. Start with pre[source]and work your way back.

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

回答by Nicholas White

The fact that it is an NP-hard problem doesn't really matter when there are only about 150 currencies currently in existence, and I suspect your FX broker will only let you trade at most 20 pairs anyway. My algorithm for ncurrencies is therefore:

当目前只有大约 150种货币存在时，这是一个 NP 难题这一事实并不重要，而且我怀疑您的外汇经纪商无论如何只会让您交易最多 20 对。n因此，我的货币算法是：

1. Make a tree of depth nand branching factor n. The nodes of the tree are currencies and the root of the tree is your starting currency X. Each link between two nodes (currencies) has weight w, where wis the FX rate between the two currencies.
2. At each node you should also store the cumulative fx rate (calculated by multiplying all the FX rates above it in the tree together). This is the FX rate between the root (currency X) and the currency of this node.
3. Iterate through all the nodes in the tree that represent currency X(maybe you should keep a list of pointers to these nodes to speed up this stage of the algorithm). There will only be n^nof these (very inefficient in terms of big-O notation, but remember your nis about 20). The one with the highest cumulative FX rate is your best FX rate and (if it is positive) the path through the tree between these nodes represents an arbitrage cycle starting and ending at currency X.
4. Note that you can prune the tree (and so reduce the complexity from O(n^n)to O(n)by following these rules when generating the tree in step 1:
   1. If you get to a node for currency X, don't generate any child nodes.
   2. To reduce the branching factor from nto 1, at each node generate all nchild nodes and only add the child node with the greatest cumulative FX rate (when converted back to currency X).

1. 制作一个深度n和分支因子的树n。树的节点是货币，树的根是您的起始货币X。两个节点（货币）之间的每个链接都有权重w，其中w是两种货币之间的汇率。
2. 在每个节点，您还应该存储累积外汇汇率（通过将树中高于它的所有外汇汇率相乘计算得出）。这是根节点（货币X）与该节点货币之间的汇率。
3. 遍历树中代表货币的所有节点X（也许您应该保留指向这些节点的指针列表以加快算法的这一阶段）。只有n^n这些（就大 O 表示法而言效率非常低，但请记住您的n数量约为 20）。累积外汇汇率最高的那个是您的最佳外汇汇率，并且（如果它是正的）通过这些节点之间的树的路径代表一个以货币开始和结束的套利周期X。
4. 请注意，您可以修剪树（从而在步骤 1 中生成树时遵循以下规则O(n^n)来降低从到的复杂性O(n)：
   1. 如果您到达货币节点X，请不要生成任何子节点。
   2. 为了将分支因子从n1减少到 1，在每个节点生成所有n子节点，并且只添加具有最大累积外汇汇率（当转换回货币时X）的子节点。

回答by JP_smasher

Imho, there is a simple mathematical structure to this problem that lends itself to a very simple O(N^3) Algorithm. Given a NxN table of currency pairs, the reduced row echelon formof the table should yield just 1 linearly independent row (i.e. all the other rows are multiples/linear combinations of the first row) if no arbitrage is possible.

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

We can just perform gaussian eliminationand check if we get just 1 linearly independent row. If not, the extra linearly independent rows will give information about the number of pairs of currency available for arbitrage.

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

回答by amit

Take the log of the conversion rates. Then you are trying to find the cycle starting at X with the largest sum in a graph with positive, negative or zero-weighted edges. This is an NP-hard problem, as the simpler problem of finding the largest cycle in an unweighted graph is NP-hard.

记录转换率。然后，您尝试在具有正、负或零加权边的图中找到从 X 开始且总和最大的循环。这是一个 NP-hard 问题，因为在未加权图中找到最大环的更简单的问题是 NP-hard。

回答by Wolfy

Unless I totally messed this up, I believe my implementation works using Bellman-Ford algorithm:

除非我完全搞砸了，否则我相信我的实现可以使用 Bellman-Ford 算法：

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>


std::vector<std::vector<double>> transform_matrix(std::vector<std::vector<double>>& matrix)
{
    int n = matrix.size();
    int m = matrix[0].size();
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            matrix[i][j] = log(matrix[i][j]);
        }
    }
    return matrix;
}

bool is_arbitrage(std::vector<std::vector<double>>& currencies)
{

    std::vector<std::vector<double>> tm = transform_matrix(currencies);

    // Bellman-ford algorithm
    int src = 0;
    int n = tm.size(); 
    std::vector<double> min_dist(n, INFINITY);

    min_dist[src] = 0.0;

    for (int i = 0; i < n - 1; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            for (int k = 0; k < n; ++k)
            {
                if (min_dist[k] > min_dist[j] + tm[j][k])
                    min_dist[k] = min_dist[j] + tm[j][k];
            }
        }
    }

    for (int j = 0; j < n; ++j)
    {
        for (int k = 0; k < n; ++k)
        {
            if (min_dist[k] > min_dist[j] + tm[j][k])
                return true;
        }
    }
    return false;
}


int main()
{
    std::vector<std::vector<double>> currencies = { {1, 1.30, 1.6}, {.68, 1, 1.1}, {.6, .9, 1} };
    if (is_arbitrage(currencies))
        std::cout << "There exists an arbitrage!" << "\n";
    else
        std::cout << "There does not exist an arbitrage!" << "\n";



    std::cin.get();
}