Интересная проблема (Арбитраж валюты)
Арбитраж является процессом использования несоответствий в значениях обмена валюты для приобретения прибыли.
Рассмотрите человека, который запускается с некоторой суммы X валют, проходит ряд обменов и наконец заканчивает с большей суммой X (чем он первоначально имел).
Данные n валюты и таблица (nxn) обменных курсов, разработайте алгоритм, который человек должен использовать для помощи максимальной прибыли, предполагающей, что он не выполняет один обмен несколько раз.
Я думал о решении как это:
- Используйте изменил алгоритм Dijkstra для нахождения единственного источника самым длинным путем продукта.
- Это дает самый длинный путь продукта от исходной валюты друг до друга валюта.
- Теперь, выполните итерации друг по другу валюты и умножьтесь к максимальному продукту до сих пор,
w(curr,source)(вес края к источнику). - Выберите максимум всех таких путей.
В то время как это кажется хорошим, я все еще сомнение в правильности этого алгоритма и полноте проблемы. (т.е. действительно ли проблема Полна NP?), поскольку это несколько напоминает проблему коммивояжера.
Поиск комментариев и лучших решений (если таковые имеются) для этой проблемы.
Спасибо.
Править:
Поиск Google этой темы взял меня к этому здесь, где арбитражное обнаружение было обращено, но обмены для максимального арбитража не. Это может служить ссылке.
2 ответа
Здесь нельзя использовать Дейкстры, потому что нет способа изменить Дейкстру на вернуть самый длинный путь, а не самый короткий. В общем, проблема самого длинного пути на самом деле является NP-полной, как вы и подозревали, и, как вы предположили, связана с проблемой коммивояжера.
То, что вы ищете (как вы знаете), - это цикл, произведение весов ребер которого больше 1, то есть w 1 * w 2 * w 3 * ...> 1. Мы можем переосмыслить эту задачу, изменив ее на сумму, а не на произведение, если мы возьмем бревна обеих сторон:
log (w 1 * w 2 * w 3 ...)> log (1)
=> log (w 1 ) + log (w 2 ]) + log (w 3 ) ...> 0
И если мы возьмем отрицательное значение log ...
=> -log (w 1 ) - log (w 2 ) - log (w 3 ) ... <0 (обратите внимание на перевернутое неравенство)
Итак, теперь мы просто ищем отрицательный цикл на графике , который может быть решен с помощью алгоритма Беллмана-Форда (или, если вам не нужно знать путь, алгоритма Флойда-Уоршалла)
Сначала преобразуем граф:
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
w[i][j] = -log(w[i][j]);
Затем мы выполняем стандартный алгоритм Беллмана -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] и вернитесь назад.
Возьмите лог коэффициентов преобразования. Затем вы пытаетесь найти цикл, начинающийся в X, с наибольшей суммой в графе с положительно, отрицательно или нуль-взвешенными ребрами. Это NP-трудная задача, так как более простая задача нахождения наибольшего цикла в невзвешенном графе является NP-трудной.