Валютный алгоритм обмена (Android / Java / Псевдокод)

У меня проблема с поиском хорошего решения проблемы обмена валюты. Я весь день думал об этом, предлагая какое-нибудь элегантное и быстрое решение для всех случаев.

Заявление:

У нас есть курсы обмена, например ...

  • Из евро в доллары -> 1,37
  • Доллар в австралийский доллар -> 0,7
  • MEX в CAD -> 1,8
  • LIB в YEN -> 2.3
  • (.....)

Эти ставки не являются реальными и могут меняться раз в день. Количество ставок может быть таким же большим, как и валюты в мире (около 150).

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

В лучшем случае, если вы обменяетесь напрямую (отображается в списке), в худшем случае вы должны МНОГО раз прыгать в промежуточных обменных курсах.

Примечание: если перевести евро в доллары, вы можете предположить, что доллар США к евро является обратным.

Надеюсь, проблема ясна.

Любые идеи??


android java algorithm currency pseudocode
person Sotti    schedule 15.12.2013    source источник
comment
Зависит ли окончательная ставка от конкретного маршрута, по которому идет ваш алгоритм?   -  person PM 77-1    schedule 16.12.2013
comment
Нет, не должно. Ставки соответствуют.   -  person Sotti    schedule 16.12.2013

Ответы (2)


arrow_upward
2
arrow_downward

Постройте взвешенный ориентированный граф с каждой вершиной, помеченной названием валюты. Если у вас есть курс для валюты от A до B, добавьте преимущество (A, B) с обменным курсом в качестве веса.

Если у вас есть ребро (A, B), но нет ребра (B, A), добавьте ребро (B, A) с весом 1, разделенным на вес (A, B).

Чтобы преобразовать валюту C в D, примените алгоритм кратчайшего пути, чтобы найти путь с наименьшим весом от вершины C к вершине D. Если такого пути нет, преобразование не может быть выполнено. См. ориентированный граф с неотрицательными весами.

=======================================================================================

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

Чтобы найти путь обмена с наименьшим количеством обменов, присвойте каждому ребру, соответствующему прямому обмену, вес 1.

person Patricia Shanahan    schedule 16.12.2013
comment
Ставки не настоящие и могут быть любыми. Все время меняется. Таким образом, вы не можете использовать промежуточную валюту. - person Sotti; 17.12.2013
comment
Отвечая на вопрос Патрисии, моя проблема в том, какой алгоритм кратчайшего пути мне следует использовать. Вот почему я спросил здесь. Я тоже хотел бы знать, как люди будут наращивать захват. Другой вопрос ... Может ли алгоритм Дикйстры найти кратчайший путь между любыми двумя точками ?? Могу я использовать здесь? - person Sotti; 17.12.2013
comment
Вы можете использовать алгоритм кратчайшего пути Дикжстры, если веса ребер неотрицательны. Если вы минимизируете количество обменов, дайте каждому ребру вес 1, и вы можете использовать Dikjstra. Если вы хотите минимизировать обменный курс, используя логарифмические ставки, у вас будут отрицательные крайние затраты, и Dikjstra не применяется. - person Patricia Shanahan; 17.12.2013
comment
Но алгоритм Дейкстры из заданного источника или для любой пары точек? Согласно Википедии (en.wikipedia.org/wiki/Shortest_path_problem): алгоритм Дейкстры решает единственный - источник проблем кратчайшего пути. Алгоритм поиска * решает кратчайший путь из одной пары с помощью эвристики, чтобы попытаться ускорить поиск. Я не ищу единый источник, потому что для каждого звонка источник может быть разным. - person Sotti; 17.12.2013
comment
@Sotti Вы намереваетесь предварительно рассчитать 150 * 150 возможных преобразований или запустить алгоритм кратчайшего пути для конкретной пары валют для каждого запроса? - person Patricia Shanahan; 17.12.2013
comment
Расчет находится во времени выполнения. Вы загружаете JSON с определенными курсами обмена валют (может быть, 2, может быть 10, может быть 80, может быть 150 ...) Когда я получаю JSON, я строю график со всеми переходами, которые дал мне JSON. Затем меня просят как можно быстрее обменять валюту. Это более ясно? - person Sotti; 17.12.2013
comment
Примерно сколько обменов вы ожидаете сделать при загрузке по обменному курсу? Это определяет, лучше ли использовать кратчайший путь из одной пары для каждого обмена или предварительно рассчитать кратчайшие пути для всех пар. - person Patricia Shanahan; 17.12.2013

arrow_upward
1
arrow_downward

Я во многом согласен с Патрицией. Но эта проблема, безусловно, связана и с избежанием арбитража. Итак, все сводится к «кратчайшему пути» (наименьшая стоимость) от валюты A к валюте B. Алгоритмы кратчайшего пути хорошо изучены и задокументированы. Найдите их в карнизах и расклепайте.

person pbhowmick    schedule 16.12.2013
comment
Это оно. По сути, я должен найти кратчайший путь. - person Sotti; 16.12.2013
comment
Я бы выбрал треугольный арбитраж, возможно, в будущем, но сейчас я хочу только знать, как построить график (я сделал это, но хотел бы услышать мнение других) и какой алгоритм кратчайшего пути использовать и как !! Действует ли здесь Dijsktra? Я думаю, что здесь применяется A *. - person Sotti; 17.12.2013