Algoritmo per determinare il tasso di cambio

Question

Dato un insieme di dati di varie coppie di valute, come faccio a calcolare in modo efficiente la velocità fx implicita per una coppia non fornita nel set di dati?

Ad esempio, dire il mio database/tabella assomiglia a questo (questi dati sono eluso):

GBP x USD = 1.5 
USD x GBP = 0.64 
GBP x EUR = 1.19 
AUD x USD = 1.1 

noti che (GBP, USD) = 1/(USD, GBP)!.

mi aspetterei i seguenti risultati:

print rate('GBP','USD') 
> 1.5 

print rate('USD','GBP') 
> 0.64 

print rate('GBP','EUR') 
> 1.19 

#now in the absence of an explicit pair, we imply one using the inverse 
print rate('EUR','GBP') 
> 0.84 

Questi sono i casi semplici, diventa più interessante:

#this is the implied rate from (GBP,EUR) and (GBP,USD) 
print rate('EUR','USD') 
> 1.26 

O un esempio ancora più complicato è trovare la traduzione più efficace utilizzando 3 o più coppie:

print rate('EUR','AUD') 
> 1.38 

Penso che dettagli la programmazione re aspetti di questo problema. Immagino che ci sia una ricorsione efficiente o intelligente che può essere fatta qui. L'unico requisito è che venga utilizzato il minor numero di coppie per arrivare alla coppia richiesta (questo è per ridurre l'errore). Se non viene indicato un inverso esplicito, invertire una coppia non ti costa nulla.

motivazione
Nel mondo finanziario ideale, i mercati valutari sono efficienti. In realtà, è vero al 99%. Spesso, le coppie di valute strane non sono quotate o sono quotate di rado. Se esiste una citazione esplicita, dobbiamo usarla nei nostri calcoli arbitrari. In caso contrario, dobbiamo implicare la coppia più precisa, con tutte le cifre decimali possibili. Inoltre, non sempre si moltiplicano a 1 (in realtà non si moltiplicano mai a 1); questo riflette lo spread denaro/lettera nel mercato. Quindi manteniamo il maggior numero di coppie possibile in entrambe le direzioni, ma vorremmo poter codificare in generale per tutte le valute.

Penso di avere implementato una soluzione di forza bruta. Funziona, ma ho pensato che il problema fosse interessante e mi chiedevo se qualcun altro lo ritenesse interessante/stimolante. Lavoro personalmente in Python ma è più un esercizio che un'implementazione, quindi il codice di psuedo è "abbastanza buono".

Answer 1

Stai cercando il percorso più breve in un grafico diretto, in cui le valute sono i vertici e i tassi di cambio dati sono i bordi. Se un tasso di cambio è dato solo per una direzione, è possibile aggiungerne uno per la direzione opposta con un costo maggiore.