最小化解决池中债务的交易成本
Minimize transaction costs for settling debts in a pool
假设一群朋友分摊了一个月的一些开支，最后需要还债。每个朋友都有一定数量的钱，他们应该give/receive（债务和应收金额之和为零），但一切都必须通过直接转帐来解决（没有中央资金池，只有钱从一个人到另一个人），并且每次传输都有成本。
例如，假设有3个人，A、B、C。
- A 必须支付 $100
- B 必须收到 50 美元
- C 必须收到 50 美元
每笔交易的成本可以用下面的矩阵来描述（行中的人支付给列中的人）。
考虑到这些成本，最佳解决方案是
- A 转账 100 美元给 B
- B 将 50 美元转给 C
这解决了交易成本为 2 的所有债务。我如何概括这一点？
我所能找到的搜索都是为了简化链式债务（A 欠 B 欠 C，所以 A 欠 C）。
我找到的最接近的是 this，但它没有交易费用。
背景故事（如果有人感兴趣的话）：
我们住在一个 8 人的房子里，每个月我们用自己的钱支付账单并在电子表格中对其进行注释，以便在月底我们公平地分摊费用。但是我们在不同的银行都有账户，其中一些需要转账到其他银行的费用，所以我们更愿意保持同一家银行的交易。
如果银行收取转账金额的一定百分比，您的任务是找到 min-cost max flow。
您的图表应该有 5 层。
(direction)
| Source layer: S
| / | \
| Exchange: A --- B --- C (complete graph)
| \ | /
V Sink : T
源连接到节点A，B，C ... S的容量-> A是A要付多少钱，如果A不拥有钱则为0。边缘的成本是 0.
在交换层A、B、C...都相互连接（完整图）。
A -> B 的容量是无限的，成本是从 A 转移 1 美元到 B 后需要支付的费用（所有对都相同）。
节点已连接到接收器。 A -> Sink 的容量是 A 会收到多少，如果 A 没有收到钱则为 0。边缘的成本是 0.
运行上图从根源到根汇的min-cost max flow算法，比如Edmonds-Karp + cycle-canceling。你最好找一个库（比如 C++ 的 Boost Graph Library），而不是自己实现算法。
我找到了另一个更简单的解决方案。我们仍在谈论与转账金额成正比的转账成本。您可以构建一个简单的图形，其节点数与人的数量和 运行 网络单纯形算法一样多。 Python 示例：
import networkx as nx
G = nx.DiGraph()
G.add_node('A', demand=-100) # A has to send 100
G.add_node('B', demand=50) # B will receive 50
G.add_node('C', demand=50) # C will receive 50
G.add_edge('A', 'B', weight=1)
G.add_edge('A', 'C', weight=5)
G.add_edge('B', 'A', weight=1)
G.add_edge('B', 'C', weight=1)
G.add_edge('C', 'A', weight=2)
G.add_edge('C', 'B', weight=2)
print nx.network_simplex(G)
输出(150, {'A': {'C': 0, 'B': 100}, 'C': {'A': 0, 'B': 0}, 'B': {'A': 0, 'C': 50}})
@j_random_hacker 在评论中解释了这个问题是 np-hard 之后，我对做出一个漂亮的解决方案失去了所有希望，并开始着手做一个可行的。
根据@user3386109 的建议，也在评论中，我基于 minpaths 解决了这个问题。所以我开始使用 [Floyd-Warshall 算法] 来找出每一对中从一个人到另一个人的最低成本。这会产生一个矩阵，其中包含将钱从行中的人转移到列中的人的最低成本。我还应用了修改（它在路径重建部分的维基百科文章中可用）以获得产生下一个节点的矩阵（下一跳，如果想要到达列中的人，你必须汇款的实际人行中的人向列中的人转账的成本最低。
初始化矩阵示例，以及运行算法后的结果（更改的重要元素用红点表示）：
然后我决定进行简单的分支定界递归。每次递归调用都会收到一份债务清单、迄今为止所有交易的矩阵以及达到该状态的成本。它必须 return TODO。我们为找到的最佳解决方案保留全局，并在递归调用开始时检查达到此状态的成本是否已经比全局最佳解决方案更差，如果是，我们 return 和 "infinite"表明这不是我们需要考虑的解决方案的成本。
然后我们select在债务列表中欠钱的人和每个必须收钱的人，我们创建债务列表和交易矩阵的副本，并模拟最大金额的交易这两个人之间（如果A必须支付100而C只需要收到50，则最大值为50）。通过将这两个人的 minpath 中的所有交易增加转移的金额来修改交易矩阵。如果我们增加一个以前为零的元素，成本就会增加。然后我们调用递归。如果债务列表达到 0，则找到解决方案，更新全局最小成本并且成本 returned 为 0。
在以前的版本中，我为每对 owing/receiving 人生成了一个递归。这产生了可怕的性能，并证明是不必要的，因为交易的顺序无关紧要，任何尚未清算的债务我们都会在较低的递归级别处理。
这个算法看似正确，但是还是有问题！
在下面的例子中：
- A 必须支付 40 美元
- B 必须支付 40 美元
- C 必须支付 20 美元
- D 必须收到 100 美元
现在的算法，让A、B、C各自转账给D。实际最好的办法是A、B、C三者中选一个，把所有的钱都转给D。付款。
在这个例子中，A、B、C三人转账到D的成本都是一样的极高，他们所有人要想把钱转到D的下一跳就是直接去D。但是，最佳解决方案是让每个人都将所有钱都转移给一个人，然后将其全部转移给 D。该算法无法识别，因为有人已经向 D 转账，所以这笔交易的成本为 0，因此我们应该使用这条新路径。为了解决这个问题，我在递归中包含了一个成本矩阵和一个路径矩阵，在递归开始时，我们将这个递归分支中已经进行的所有传输成本设置为 0，并且 运行又是 Floyd-Warshall 算法。递归使用这些矩阵而不是全局矩阵并将它们传递下去。当然，这意味着将复杂性乘以 V^3，但这是我找到的解决此问题的唯一方法。
该算法现在似乎可以正常工作，但我可能会继续努力改进它，尤其是在代码可读性方面。完整代码可在：
My gitlab project, inside the calculations folder
很抱歉回答太长而延迟发布，但我发现彻底记录我的工作很重要。
假设一群朋友分摊了一个月的一些开支，最后需要还债。每个朋友都有一定数量的钱，他们应该give/receive（债务和应收金额之和为零），但一切都必须通过直接转帐来解决（没有中央资金池，只有钱从一个人到另一个人），并且每次传输都有成本。
例如，假设有3个人，A、B、C。
- A 必须支付 $100
- B 必须收到 50 美元
- C 必须收到 50 美元
每笔交易的成本可以用下面的矩阵来描述（行中的人支付给列中的人）。
考虑到这些成本，最佳解决方案是
- A 转账 100 美元给 B
- B 将 50 美元转给 C
这解决了交易成本为 2 的所有债务。我如何概括这一点？
我所能找到的搜索都是为了简化链式债务（A 欠 B 欠 C，所以 A 欠 C）。
我找到的最接近的是 this，但它没有交易费用。
背景故事（如果有人感兴趣的话）：
我们住在一个 8 人的房子里，每个月我们用自己的钱支付账单并在电子表格中对其进行注释，以便在月底我们公平地分摊费用。但是我们在不同的银行都有账户，其中一些需要转账到其他银行的费用，所以我们更愿意保持同一家银行的交易。
如果银行收取转账金额的一定百分比，您的任务是找到 min-cost max flow。
您的图表应该有 5 层。
(direction)
| Source layer: S
| / | \
| Exchange: A --- B --- C (complete graph)
| \ | /
V Sink : T
源连接到节点A，B，C ... S的容量-> A是A要付多少钱，如果A不拥有钱则为0。边缘的成本是 0.
在交换层A、B、C...都相互连接（完整图）。
A -> B 的容量是无限的，成本是从 A 转移 1 美元到 B 后需要支付的费用（所有对都相同）。
节点已连接到接收器。 A -> Sink 的容量是 A 会收到多少，如果 A 没有收到钱则为 0。边缘的成本是 0.
运行上图从根源到根汇的min-cost max flow算法，比如Edmonds-Karp + cycle-canceling。你最好找一个库（比如 C++ 的 Boost Graph Library），而不是自己实现算法。
我找到了另一个更简单的解决方案。我们仍在谈论与转账金额成正比的转账成本。您可以构建一个简单的图形，其节点数与人的数量和 运行 网络单纯形算法一样多。 Python 示例：
import networkx as nx
G = nx.DiGraph()
G.add_node('A', demand=-100) # A has to send 100
G.add_node('B', demand=50) # B will receive 50
G.add_node('C', demand=50) # C will receive 50
G.add_edge('A', 'B', weight=1)
G.add_edge('A', 'C', weight=5)
G.add_edge('B', 'A', weight=1)
G.add_edge('B', 'C', weight=1)
G.add_edge('C', 'A', weight=2)
G.add_edge('C', 'B', weight=2)
print nx.network_simplex(G)
输出(150, {'A': {'C': 0, 'B': 100}, 'C': {'A': 0, 'B': 0}, 'B': {'A': 0, 'C': 50}})
@j_random_hacker 在评论中解释了这个问题是 np-hard 之后，我对做出一个漂亮的解决方案失去了所有希望，并开始着手做一个可行的。
根据@user3386109 的建议，也在评论中，我基于 minpaths 解决了这个问题。所以我开始使用 [Floyd-Warshall 算法] 来找出每一对中从一个人到另一个人的最低成本。这会产生一个矩阵，其中包含将钱从行中的人转移到列中的人的最低成本。我还应用了修改（它在路径重建部分的维基百科文章中可用）以获得产生下一个节点的矩阵（下一跳，如果想要到达列中的人，你必须汇款的实际人行中的人向列中的人转账的成本最低。
初始化矩阵示例，以及运行算法后的结果（更改的重要元素用红点表示）：
然后我决定进行简单的分支定界递归。每次递归调用都会收到一份债务清单、迄今为止所有交易的矩阵以及达到该状态的成本。它必须 return TODO。我们为找到的最佳解决方案保留全局，并在递归调用开始时检查达到此状态的成本是否已经比全局最佳解决方案更差，如果是，我们 return 和 "infinite"表明这不是我们需要考虑的解决方案的成本。
然后我们select在债务列表中欠钱的人和每个必须收钱的人，我们创建债务列表和交易矩阵的副本，并模拟最大金额的交易这两个人之间（如果A必须支付100而C只需要收到50，则最大值为50）。通过将这两个人的 minpath 中的所有交易增加转移的金额来修改交易矩阵。如果我们增加一个以前为零的元素，成本就会增加。然后我们调用递归。如果债务列表达到 0，则找到解决方案，更新全局最小成本并且成本 returned 为 0。
在以前的版本中，我为每对 owing/receiving 人生成了一个递归。这产生了可怕的性能，并证明是不必要的，因为交易的顺序无关紧要，任何尚未清算的债务我们都会在较低的递归级别处理。
这个算法看似正确，但是还是有问题！
在下面的例子中：
- A 必须支付 40 美元
- B 必须支付 40 美元
- C 必须支付 20 美元
- D 必须收到 100 美元
现在的算法，让A、B、C各自转账给D。实际最好的办法是A、B、C三者中选一个，把所有的钱都转给D。付款。
在这个例子中，A、B、C三人转账到D的成本都是一样的极高，他们所有人要想把钱转到D的下一跳就是直接去D。但是，最佳解决方案是让每个人都将所有钱都转移给一个人，然后将其全部转移给 D。该算法无法识别，因为有人已经向 D 转账，所以这笔交易的成本为 0，因此我们应该使用这条新路径。为了解决这个问题，我在递归中包含了一个成本矩阵和一个路径矩阵，在递归开始时，我们将这个递归分支中已经进行的所有传输成本设置为 0，并且 运行又是 Floyd-Warshall 算法。递归使用这些矩阵而不是全局矩阵并将它们传递下去。当然，这意味着将复杂性乘以 V^3，但这是我找到的解决此问题的唯一方法。
该算法现在似乎可以正常工作，但我可能会继续努力改进它，尤其是在代码可读性方面。完整代码可在： My gitlab project, inside the calculations folder
很抱歉回答太长而延迟发布，但我发现彻底记录我的工作很重要。