Комментарии 8
В реальности все немного сложнее и арбитраж не является безрисковой сделкой.
Так в вашем примере доллары за евро вы купили, а вот евро за доллары по той цене на которую вы рассчитывали уже нет — их кто-то уже купил. Например, такой же арбитражник.
Размеры лотов, на самом деле не безлимитны и текущая цена может поменять за то время, пока вы принимали решение.
А это время включает в себя период обновления стакана на бирже, сетевая задержка к вам, расчет алгоритмами, сетевая задержка обратно.
В лучшем случае это сотни миллисекунд, в худшем — несколько секунд (например, когда стакан отдается не чаще чем раз в 3 секунды, хоть ты тресни).
Так в вашем примере доллары за евро вы купили, а вот евро за доллары по той цене на которую вы рассчитывали уже нет — их кто-то уже купил. Например, такой же арбитражник.
Размеры лотов, на самом деле не безлимитны и текущая цена может поменять за то время, пока вы принимали решение.
А это время включает в себя период обновления стакана на бирже, сетевая задержка к вам, расчет алгоритмами, сетевая задержка обратно.
В лучшем случае это сотни миллисекунд, в худшем — несколько секунд (например, когда стакан отдается не чаще чем раз в 3 секунды, хоть ты тресни).
Даже самый скромный вклад в популяризацию применения математики к реальным задачам может дать неожиданно большие результаты. Ваша статья — хорошая попытка это сделать. Побольше бы таких.
Пару поправок:
наверное, меньше 1
наверное, под логарифмом произведение
Прибыльной последовательность сделок становится, если это произведение принимает значение меньше нуля.
наверное, меньше 1
Если под логарифмом оказывается сумма, то такой логарифм может быть преобразован в сумму логарифмов.
наверное, под логарифмом произведение
классические алгоритмы позволяют решать реальные проблемы бизнеса
Реальные проблемы этого бизнеса совсем другие) но за статью спасибо)
НЛО прилетело и опубликовало эту надпись здесь
А если надо искать кратчайший путь много раз, можно запускать ФБ только один раз, а потом использовать Дейкстру.
Можна модифицировать алгоритм Дейкстры, таким образом, чтобы он корректно работал с рёбрами отрицательного веса. Сложность алгоритма не поменяется.
Идея — использовать потенциалы Джонсона, то-есть изменить веса ребер таким образом, что бы они стали положительными. Сделать это достаточно просто.
Давайте, просто возьмем и присвоим вершинам графа числа 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.
Называется это все, алгоритмом Джонсона.
Можна модифицировать алгоритм Дейкстры, таким образом, чтобы он корректно работал с рёбрами отрицательного веса. Сложность алгоритма не поменяется.
Идея — использовать потенциалы Джонсона, то-есть изменить веса ребер таким образом, что бы они стали положительными. Сделать это достаточно просто.
Давайте, просто возьмем и присвоим вершинам графа числа 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.
Называется это все, алгоритмом Джонсона.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Арбитражная торговля (Алгоритм Беллмана — Форда)