净订单的最佳算法

Question

我正在建立一个市场,我想为市场参与者订单建立一个匹配机制.

例如,我收到这些订单:

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

可以被表示为List<Orders>,其中Order是与一类Participant,BuySell和Amount

我想创建一个Match输出两件事的函数:

1. 一组不匹配的订单(List<Order>)
2. 一组匹配的订单(List<MatchedOrder>其中MatchOrder有Buyer,Seller,Amount

约束是最小化订单数量(不匹配和匹配),同时不留下任何可能的匹配(即,最终只能存在无法匹配的买入或卖出订单)

所以在上面的例子中,结果将是:

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

这似乎是一个相当复杂的编写算法,但在实践中很常见.任何指针在哪里看？

Answer 1

您可以将其建模为二分图中的流问题。每个销售节点将位于左侧，每个购买节点将位于右侧。像这样：

source然后你必须找到从到可以传递的最大流量sink。

您可以使用任何您想要的最大流量算法，例如Ford Fulkerson。要最小化订单数量，您可以使用最大流量/最小成本算法。有多种技术可以做到这一点，包括在找到正常的 MaxFlow 解决方案后应用循环取消。

运行算法后，您可能会得到如下所示的残差网络：