15

这个标题可能没有意义。假设如下：

  • A 欠 B 5 美元
  • 欠债 10 美元
  • 欠 D $15

在这种基本情况下，有三个事务，但可以简化为两个事务：

  • A 给 D 5 美元
  • C 给 D 10 美元

给定一个更复杂的图，存在哪些算法来最小化事务总数？

4

3 回答 3

8

在我看来，在所有交易发生后，您首先必须弄清楚每个人的涨/跌。对于您的示例，这将是：

A :  -5
B :   0
C : -10
D : +15

一旦你有了它，你只需要把它们都设为零。获得最高收益，然后开始增加损失。在这一点上，它基本上是一个装箱问题。

于 2013-09-12T19:08:56.250 回答
0

它可能效率低下，但您可以使用整数编程。

预先计算流入/流出节点 i 的净流量，即 Fi = 总债务 + 总信用

设 M 是一个大数。

令 Yij 为决策变量，表示节点 i 支付给节点 j 的金额（有序对）。

令 Xij 为二进制变量，表示 i 和 j 之间发生了交易（无序对）

优化以下内容：

min sum_{i,j} Xij

sum_{j!=i} Yij = Fi

Yij + Yji= <= M*Xij

于 2013-09-12T19:09:29.733 回答
0

你可以试试贪心的方法。所以

如果 A 欠 B 钱，而 B 欠 C，则 A 欠 C 的最小值（A->B，B->C）。并且 A->B -= min(A->B, B->C)。如果在此操作之后 A->B 变为zero然后您将其删除。循环直到您无法执行任何进一步的操作，即cycles图中没有：

do{
    bool stop = true;
    G.init() // initialize some sort of edge iterator
    while(edge = G.nextedge()){  //assuming nextedge will terminate after going through all edges once

        foreach(outedge in edge.Dest.Outedges){ //If there's any node to 'move' the cost
            minowed = min(edge.value, outedge.value)
            G.edge(edge.Src, outedge.Dest).value += minowed
            edge.value -= minowed
            outedge.value -= minowed
            if(edge.value == 0) G.remove(edge)
            if(outedge.value == 0) G.remove(outedge)
            stop = false
        }
    }
}while(!stop)

这基本上等于从图中删除任何循环以使其成为DAG.

于 2013-09-12T19:40:33.053 回答