Интересная проблема (валютный арбитраж)

Ответ 1

Dijkstra нельзя использовать здесь, потому что нет возможности изменить Dijkstra, чтобы вернуть самый длинный путь, а не самый короткий. В общем случае проблема самая длинная проблема на самом деле NP-полная, как вы подозревали, и связана с проблемой Traveling Salesman, как вы предположили.

То, что вы ищете (как вы знаете), представляет собой цикл, произведение веса которого больше 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 (заметим, что неравенство перевернуто)

Итак, теперь мы просто ищем отрицательный цикл на графике, который можно решить с помощью алгоритма Беллмана-Форда (или, если вам не нужен путь, алгоритм 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] и вернитесь назад.

Ответ 2

Тот факт, что это NP-трудная проблема, не имеет большого значения, когда в настоящий момент существует только около 150 валют, и я предположим, что ваш FX-брокер позволит вам торговать не более 20 пар в любом случае. Таким образом, мой алгоритм для валют n:

• Сделайте дерево глубины n и коэффициент ветвления n. Узлами дерева являются валюты, а корень дерева - это ваша начальная валюта X. Каждая связь между двумя узлами (валюты) имеет вес w, где w - коэффициент FX между двумя валютами.
• В каждом node вы также должны сохранить кумулятивную ставку fx (рассчитанную путем умножения всех курсов FX выше этого в дереве вместе). Это курс FX между корнем (валюта X) и валютой этого node.
• Итерации через все узлы в дереве, которые представляют валюту X (возможно, вы должны сохранить список указателей на эти узлы, чтобы ускорить этот этап алгоритма). Их будет только n^n (очень неэффективен с точки зрения обозначения большой O, но помните, что ваш n составляет около 20). Тот, у кого наибольшая совокупная валютная ставка - ваша лучшая валютная ставка, и (если она положительная), путь через дерево между этими узлами представляет собой цикл арбитража, начинающийся и заканчивающийся в валюте X.
• Обратите внимание, что вы можете обрезать дерево (и, следовательно, уменьшите сложность от O(n^n) до O(n), выполнив следующие правила при генерации дерева на шаге 1:
  • Если вы перейдете к node для валюты X, не создавайте дочерние узлы.
  • Чтобы уменьшить коэффициент ветвления от n до 1, в каждом node сгенерируйте все дочерние узлы n и добавьте только дочерний элемент node с наибольшей суммарной валютной ставкой (при преобразовании обратно в валюту X).

Ответ 3

Imho, есть простая математическая структура этой проблемы, которая поддается очень простому алгоритму O (N ^ 3). Учитывая таблицу валютных пар NxN, уменьшенная форма эшелона строки таблицы должна давать только одну линейно независимую строку (т.е. Все остальные строки являются кратными/линейные комбинации первой строки), если арбитраж невозможен.

Мы можем просто выполнить гауссово исключение и проверить, получим ли мы только одну линейно независимую строку. Если нет, дополнительные линейно независимые строки будут предоставлять информацию о количестве пар валюты, доступных для арбитража.

Ответ 4

Возьмите журнал коэффициентов конверсии. Затем вы пытаетесь найти цикл, начинающийся с X с наибольшей суммой в графе с положительными, отрицательными или нулевыми взвешенными ребрами. Это проблема NP-hard, так как более простая проблема нахождения наибольшего цикла в невзвешенном графике NP-hard.

Ответ 5

Если я полностью не испортил это, я считаю, что моя реализация работает с использованием алгоритма Беллмана-Форда:

#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();
}