给定一个具有各种货币对的数据集，如何为该数据集中未提供的货币对有效地计算隐含的汇率？
例如，假设我的数据库/表如下所示(此数据被伪造):
GBP x USD = 1.5
USD x GBP = 0.64
GBP x EUR = 1.19
AUD x USD = 1.1
注意(GBP，USD)!= 1/(USD，GBP)。
我希望得到以下结果:
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)。这反射(reflect)了市场中的买卖差价。因此，我们在两个方向上都保持尽可能多的货币对，但希望能够对所有货币进行通用编码。
我认为我已经实现了一个体面的暴力解决方案。它可行，但是我认为问题很有趣，并且想知道是否有人认为这很有趣/具有挑战性。我个人使用Python进行工作，但它不是实现而是一种练习，因此伪代码“足够好”。
最佳答案
您正在寻找有向图中的最短路径，其中货币是顶点，给定的汇率是边。
如果只为一个方向提供汇率，则可以向相反方向添加一个汇率，其成本更高。
关于python - 确定汇率的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3372375/