确定汇率的算法

Question

给定各种货币对的数据集,如何有效计算数据集中未提供的货币对的隐含汇率？

例如,假设我的数据库/表看起来像这样(这个数据是捏造的):

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

请注意(GBP,USD)!= 1 /(美元,英镑).

我希望得到以下结果:

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

这些是简单的案例,它变得更有趣:

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

或者更复杂的例子是使用3对或更多对来找到最有效的翻译:

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

我认为详细说明了这个问题的编程相关方面.我想可以在这里完成一个有效或聪明的递归.唯一的要求是使用最少数量的对来到达要求对(这是为了减少错误).如果没有给出明确的反转,那么反转一对就不需要任何成本.

动机
在理想的金融世界中,货币市场是有效的.实际上,这是99%的真实.通常情况下,奇数货币对不会被引用,或者它们很少被引用.如果存在显式引用,我们必须在任意计算中使用它.如果没有,我们必须暗示最准确的一对,尽可能多的小数位.此外,它们并不总是乘以1(实际上,它们从不乘以1); 这反映了市场上的买/卖差价.因此,我们在两个方向上尽可能多地保持对,但是希望能够对所有货币进行一般编码.

我想我已经实施了一个体面的蛮力解决方案.它有效,但我认为这个问题很有趣,并且想知道是否有其他人认为它有趣/具有挑战性.我个人在Python工作,但它更像是一个练习而不是一个实现,所以psuedo代码"足够好".

Answer 1

您正在寻找有向图中的最短路径,其中货币是顶点,给定的汇率是边缘.如果仅针对一个方向给出汇率,则可以以相反的方向添加一个具有更高成本的汇率.