Алторитъм за обмен на валута (Android / Java / псевдокод)

Имам проблем с намирането на добро решение на проблема с обменната валута. Цял ден съм мислил за това с всяко елегантно и бързо решение за всички случаи.

Изявление:

Имаме някои валутни курсове като...

  • EUR към USD -> 1,37
  • USD към AUD -> 0,7
  • MEX към CAD -> 1.8
  • LIB към YEN -> 2.3
  • (.....)

Тези курсове не са реални и могат да се променят веднъж на ден. Броят на курсовете може да бъде толкова голям, колкото са валутите в света (около 150).

От нас се иска да конвертираме сума пари от която и да е валута в друга и ние трябва да дадем отговор (ако можем) предвид валутните курсове.

Най-добрият случай е, ако обменът е директен (показва се в списъка), в по-лошия случай трябва да скочите МНОГО пъти в междинните обменни курсове.

Забележка: Като се има предвид EUR към USD, можете да приемете, че uSD към EUR е обратното.

Надявам се проблема да е ясен.

Някакви идеи??


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
Отговаряйки на Патриша, проблемът ми е какъв и как алгоритъм за най-кратък път трябва да използвам. Затова попитах тук. Бих искал също да знам как хората биха изградили хватката. Друг въпрос е.. Може ли алгоритъмът на Dikjstra да намери най-краткия път между всеки две точки?? Мога ли да използвам тук? - person Sotti; 17.12.2013
comment
Можете да използвате алгоритъма за най-краткия път на Dikjstra, ако теглата на ръбовете са неотрицателни. Ако минимизирате броя на обмените, дайте тегло на всеки край 1 и можете да използвате Dikjstra. Ако искате да минимизирате обменния курс, като използвате логаритмични курсове, ще имате отрицателни разходи за предимство и Dikjstra не се прилага. - person Patricia Shanahan; 17.12.2013
comment
Но Dijkstra algo е от даден източник или за всяка двойка точки? Според Wikipedia (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

До голяма степен бих се съгласил с Патриша. Но този проблем със сигурност е свързан и с избягването на арбитраж. И така, всичко се свежда до „най-кратък път“ (най-ниска цена) от валута А до валута Б. Алгоритмите за най-кратък път са добре проучени и документирани. Потърсете ги в кормен и нитове.

person pbhowmick    schedule 16.12.2013
comment
Това е то. По принцип трябва да намеря най-краткия път. - person Sotti; 16.12.2013
comment
Може би в бъдеще бих използвал триъгълен арбитраж, но сега искам само да знам как да построя графиката (направих я, но бих искал да чуя мненията на другите) и кой алгоритъм за най-кратък път да използвам и как!! Валиден ли е Dijsktra тук? Мисля, че A* е този, който се прилага тук. - person Sotti; 17.12.2013