結算訂單的最佳算法

我正在建立一個市場，並且我想爲市場參與者訂單建立一個匹配機制。結算訂單的最佳算法

比如我收到這些命令：

A buys 50 
B buys 100 
C sells 50 
D sells 20

可以表示爲List<Orders>，其中Order是Participant，BuySell一類，並Amount

我想創建一個Match功能，輸出2件東西：

一套unmatche d訂單（List<Order>）
一組匹配的訂單（List<MatchedOrder>其中MatchOrder具有Buyer，Seller，Amount

的約束的是最小化的訂單數（不匹配和匹配），而不會留下任何可能的匹配而復（即，最終只能有購買或出售所無法比擬的訂單）

所以在結果上面的例子是：

A buys 50 from C 
B buys 20 from D 
B buys 80 (outstanding)

這似乎是一個相當複雜的算法，但在實踐中很常見。任何指向哪裏看？

來源

2016-02-26 d--b

你可能想考慮網絡流算法 – Mox

@Mox：謝謝我來看看。乍看之下，雖然流程算法似乎正在解決我試圖解決的一個非常普遍的問題。 –

您是否被要求遵守先入先出的原則？如果不是，那麼這意味着另一個到達的訂單可以任意地改變先前買入和賣出訂單的匹配，例如，以前與賣單相匹配的買單現在恢復爲未平倉。 –

您可以將此模型作爲二部圖中的流動問題進行建模。每個銷售節點都在左側，每個購買節點都在右側。就像這樣：

graphviz]

然後，你必須找到你可以通過從source到sink流量的最高金額。

您可以使用任何您想要的最大流量算法，例如， Ford Fulkerson。爲了最大限度地減少訂單數量，您可以使用最大流量/最小成本算法。有許多技術可以做到這一點，包括在找到正常的MaxFlow解決方案後應用循環取消。

算法運行後，你可能有殘留的網絡類似如下：

來源

2016-02-26 12:46:34

但我不認爲這是最小化數量流量，它只是找到一個有效的答案。我對嗎？ –

@ d - b你是對的，沒有注意到這一點。但是你仍然可以用這個建模來解決它，你只需要使用MaxFlow/MinCost算法。 –

創建WithRemainingQuantity結構，2個成員：一個pointeur o到訂單和整數存儲不匹配的數量
考慮2 List<WithRemainingQuantity>,1爲買Bq，1爲賣Sq，二者都按照包含訂單的降序排序。
的ALGO每個隊列的頭部匹配直到它們中的一個是空的

ALGO（間位和C++的混合）：

struct WithRemainingQuantity 
{ 
    Order * o; 
    int remainingQty; // initialised with o->getQty 
} 


struct MatchedOrder 
{ 
    Order * orderBuy; 
    Order * orderSell; 
    int matchedQty=0; 
} 

List<WithRemainingQuantity> Bq; 
List<WithRemainingQuantity> Sq; 

/* 
populate Bq and Sq and sort by quantities descending, 
this is what guarantees the minimum of matched. 
*/  

List<MatchedOrder> l; 
while(! Bq.empty && !Sq.empty) 
{ 
    int matchedQty = std::min(Bq.front().remainingQty, Sq.front().remainingQty) 

    l.push_back(MatchedOrder(orderBuy=Bq.front(), sellOrder=Sq.front(), qtyMatched=matchedQty)) 

    Bq.remainingQty -= matchedQty 
    Sq.remainingQty -= matchedQty 

    if(Bq.remainingQty==0) 
     Bq.pop_front() 

    if(Sq.remainingQty==0) 
     Sq.pop_front() 
}

不匹配的訂單在貝或平方剩餘訂單（根據while條款，其中一個如果致命地爲空）。

來源

2016-02-26 13:08:38 norisknofun

我不認爲這是正確的，這個問題比僅僅匹配堆棧更復雜。你不能保證你在這裏得到最佳答案。 –

是的，這是因爲該列表按數量排序。你的客觀函數（約束）不清楚，但你可以調整排序標準（賣家升序，買家降例如）。我在後臺的貿易公司使用這種方法...... – norisknofun

你能否提供有關約束的細節？ – norisknofun

結算訂單的最佳算法

回答

相關問題