Algorithme de détermination du taux de change

Question

Étant donné un ensemble de données de différentes paires de devises, comment calculer efficacement le taux de change implicite pour une paire non fournie dans l'ensemble de données?

Par exemple, supposons que ma base de données/tableau ressemble à ceci (ces données sont truqués):

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

Notez que (GBP, USD) = 1/(USD, GBP)!.

j'attendre les résultats suivants:

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 

Ce sont les cas simples, il devient plus intéressant:

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

Ou un exemple encore plus compliqué est de trouver la traduction la plus efficace en utilisant 3 ou plus de paires:

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

Je pense que cela détaille la programmation re aspects de ce problème. J'imagine qu'il y a une récursion efficace ou intelligente qui peut être faite ici. La seule exigence est que le plus petit nombre de paires soit utilisé pour arriver à la paire demandée (ceci est pour réduire l'erreur). Si aucun inverse explicite n'est donné, inverser une paire ne vous coûte rien.

Motivation
Dans le monde financier idéal, les marchés monétaires sont efficaces. En réalité, c'est 99% vrai. Souvent, les paires de devises impaires ne sont pas citées ou sont rarement citées. Si une citation explicite existe, nous devons l'utiliser dans nos calculs arbitraires. Sinon, nous devons impliquer la paire la plus précise, à autant de décimales que possible. De plus, ils ne se multiplient pas toujours à 1 (en réalité, ils ne se multiplient jamais à 1); Cela reflète l'écart entre les cours acheteur et vendeur sur le marché. Nous gardons donc autant de paires que nous pouvons dans les deux sens, mais nous aimerions pouvoir coder en général pour toutes les devises. Je pense que j'ai une solution de force brute décent implémentée. Cela fonctionne, mais je pensais que le problème était intéressant et je me demandais si quelqu'un d'autre pensait que c'était intéressant/stimulant. Je travaille personnellement en Python mais c'est plus un exercice qu'une implémentation, donc le code de psuedo est "assez bon".

Answer 1

Vous recherchez le chemin le plus court dans un graphique orienté, où les devises sont les sommets et les taux de change donnés sont les arêtes. Si un taux de change n'est donné que pour une direction, vous pouvez en ajouter un pour la direction opposée avec un coût plus élevé.