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

Question

Арбитраж - это процесс использования расхождений в значениях обмена валюты для получения прибыли.
Представьте себе человека, который начинает с некоторого количества валюты X, проходит серию обменов и, наконец, получает большее количество X (чем он изначально имел).
Учитывая n валют и таблицу (nxn) курсов валют, разработайте алгоритм, который человек должен использовать, чтобы получить максимальную прибыль, при условии, что он не выполняет один обмен более одного раза.

Я думал о таком решении:

1. Используйте модифицированный алгоритм Дейкстры, чтобы найти самый длинный путь продукта из одного источника.
2. Это дает самый длинный путь продукта из исходной валюты в другую валюту.
3. Теперь перебираем каждую другую валюту и умножаем до максимального продукта на данный момент, w(curr,source) (вес от края до источника).
4. Выберите максимум всех таких путей.

Хотя это кажется хорошим, я все еще сомневаюсь в правильности этого алгоритма и полноте проблемы (т. Е. Является ли проблема NP-Complete?), Поскольку она несколько напоминает проблему коммивояжера.

Ищем ваши комментарии и лучшие решения (если таковые имеются) для этой проблемы.

Спасибо.

EDIT:
Поиск в Google по этой теме привел меня к этому здесь , где было решено арбитражное обнаружение, но обмены на максимальный арбитраж - нет. Это может служить ссылкой.

Answer 1

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

Итак, мы сейчас просто ищем отрицательный цикл на графике, который можно решить с помощью алгоритма Беллмана-Форда (или, если вам не требуется знать путь, алгоритм Флойд-Варшалла)

Сначала мы преобразуем график:

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

Затем мы выполняем стандарт Беллмана-Форда

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

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

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

Answer 3

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

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

Answer 4

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

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