確定匯率的算法

給定各種貨幣對的數據集，如何有效計算數據集中未提供的對的隱含fx匯率？確定匯率的算法

例如，說我的數據庫/表看起來是這樣的（這個數據是捏造）：

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

注意（英鎊，美元）= 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中工作，但它比實現更像是一個練習，所以僞代碼是「足夠好」的。

來源

2010-07-30 TrevorB

這是ProLog中的一項非常簡單的任務:)。程序算法需要更多的思考。我的猜測是，你必須形成一個轉換樹，頂部節點是源貨幣，葉子 - 最後一個可能的貨幣，條件是每個貨幣只能出現一次。該算法然後將選擇獲得的最小合成匯率。遞歸方法。 – AlexanderMP 2010-07-30 14:28:12

您正在尋找有向圖中的最短路徑，其中貨幣是頂點並且給定的匯率是邊緣。如果匯率只給出一個方向，您可以添加一個相反方向的成本較高。

來源

2010-07-30 14:28:03 Henrik

哦，我忘了所有關於圖。答對了！你給了他答案:) – AlexanderMP 2010-07-30 14:29:30

確定匯率的算法

回答

相關問題