Арбитражная торговля (Алгоритм Беллмана — Форда)

[@shapovalex]

В реальности все немного сложнее и арбитраж не является безрисковой сделкой.
Так в вашем примере доллары за евро вы купили, а вот евро за доллары по той цене на которую вы рассчитывали уже нет — их кто-то уже купил. Например, такой же арбитражник.
Размеры лотов, на самом деле не безлимитны и текущая цена может поменять за то время, пока вы принимали решение.
А это время включает в себя период обновления стакана на бирже, сетевая задержка к вам, расчет алгоритмами, сетевая задержка обратно.
В лучшем случае это сотни миллисекунд, в худшем — несколько секунд (например, когда стакан отдается не чаще чем раз в 3 секунды, хоть ты тресни).

[@dmitrievanthony]

Всё верно. Чтобы применить эту стратегию на практике нужно будет разобраться ещё со многими вещами и их учитывать. Однако базовый принцип сохраняется. И, как мне кажется, он достаточно интересен с алгоритмической точки зрения.

[@Sergey_Kovalenko]

Даже самый скромный вклад в популяризацию применения математики к реальным задачам может дать неожиданно большие результаты. Ваша статья — хорошая попытка это сделать. Побольше бы таких.

[@bellerofonte]

Пару поправок:

Прибыльной последовательность сделок становится, если это произведение принимает значение меньше нуля.

наверное, меньше 1

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

наверное, под логарифмом произведение

[@dmitrievanthony]

Спасибо, поправил!

[@robomakerr]

классические алгоритмы позволяют решать реальные проблемы бизнеса

Реальные проблемы этого бизнеса совсем другие) но за статью спасибо)

[@brecurse]

А если надо искать кратчайший путь много раз, можно запускать ФБ только один раз, а потом использовать Дейкстру.

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

Идея — использовать потенциалы Джонсона, то-есть изменить веса ребер таким образом, что бы они стали положительными. Сделать это достаточно просто.

Давайте, просто возьмем и присвоим вершинам графа числа p(v) = кратчайшее расстояние от s к v И будем решать задачу для графа с измененными весами ребер: С'(uv) = C(uv)+p(u)-p(v).

Доказательство состоит из двух лемм:
Л1. Веса всех ребер неотрицательны.
Док-во: пусть существует ребро (uv) вес которого отрицателен, тогда C(uv)+p(u)-p(v)<0, а значит C(uv)+p(u)<p(v), но тогда мы должны были пойти из u в v, и это было бы выгоднее. Противоречие.

Л2. Для любой пары вершин кратчайший пути сохранился.
В самом деле, давайте распишем новую стоимость пути из s в t: C'(s,a1)+C'(a1,a2)+...+C'(ax,t) = C(s,a1)+...+C(ax,t)+(p(s)+...p(ax))-(p(a1)+...+p(t))=oldpath + p(s)-p(t) = oldpath + const.

Называется это все, алгоритмом Джонсона.