Bester Algorithmus zum Aufrechnen von Aufträgen

Question

Ich baue einen Marktplatz, und ich möchte einen passenden Mechanismus für die Aufträge der Marktteilnehmer aufbauen.

So erhalte ich diese Aufträge:

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

, die als List<Orders> dargestellt werden kann, wo Order ist eine Klasse mit Participant, BuySell und Amount

ich eine Match Funktion erstellen möchten, das gibt 2 Dinge aus:

1. Eine Reihe von unmatche d Aufträge (List<Order>)
2. Eine Reihe von matched orders (List<MatchedOrder> wo MatchOrder hat Buyer, Seller, Amount

Die constrain ist die Anzahl der Aufträge (nicht angepasste und aufeinander abgestimmt) zu minimieren, während keine mögliche Übereinstimmung rückgängig gemacht verlassen (dh am Ende kann es nur sein, entweder kaufen oder Verkaufsaufträge, die nicht angepasst sind)

So in dem obigen Beispiel das Ergebnis wäre:

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

Dies scheint ein ziemlich komplexer Algorithmus zum Schreiben zu sein, aber in der Praxis sehr verbreitet. Irgendwelche Hinweise, wo man hinschauen kann?

Answer 1

Sie können dies als Strömungsproblem in einem zweiteiligen Diagramm modellieren. Jeder verkaufende Knoten wird auf der linken Seite sein, und jeder kaufende Knoten wird auf der rechten Seite sein. Wie folgt aus:

Dann müssen Sie die maximale Durchflussmenge finden Sie von source zu sink passieren kann.

Sie können beliebige maximale Flussalgorithmen verwenden, z. Ford Fulkerson. Um die Anzahl der Aufträge zu minimieren, können Sie einen Algorithmus für maximalen Durchfluss/minimale Kosten verwenden. Es gibt eine Reihe von Techniken, um dies zu tun, einschließlich der Anwendung von Cycle Cancelling nach dem Auffinden einer normalen MaxFlow-Lösung.

Nach dem Algorithmus ausgeführt wird, werden Sie wahrscheinlich ein Rest Netzwerk wie die folgenden haben:

Answer 2

1. erstellen WithRemainingQuantity Struktur mit zwei Mitgliedern: a pointeur o zu einem Auftrag und eine ganze Zahl zu Speichern Sie die unübertroffene Menge
2. Betrachten 2 List<WithRemainingQuantity>, 1 für kauft Bq, 1 für verkauft Sq, beide nach absteigenden Mengen der enthaltenen Reihenfolge sortiert.
3. die Algo dem Kopf jeder Warteschlange entsprechen, bis einer von ihnen ist leer

Algo (Mischung aus meta- und 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() 
} 

die nicht ausgeglichene Aufträge sind die verbleibenden Aufträge in Bq oder Sq (einer von ihnen, wenn er tödlich leer ist, gemäß der while Klausel).