次の課題を解決するためにどのようなアルゴリズムを提案できますか? それ以外の既知の最適化タスクは類似していますか?債務整理アルゴリズム
あなたはN人(N> 2)です。一部の人々は、他の人にお金を借りている。あなたはそれらの間のマネーフローを最適化する必要があります。
例:
- P1を負っP2 30 USD
- P1を負っP3 10 USD
- P2を負っP3 20 USD
および最適化は次のようになります
- P1はP2を負う10 USD
- P1は負担ですP3 30 USD
次の課題を解決するためにどのようなアルゴリズムを提案できますか? それ以外の既知の最適化タスクは類似していますか?債務整理アルゴリズム
あなたはN人(N> 2)です。一部の人々は、他の人にお金を借りている。あなたはそれらの間のマネーフローを最適化する必要があります。
例:
および最適化は次のようになります
私は素晴らしい解決策を見つけたと思います。
各人の最終ステータス(別名グラフのノード)を計算します。これを行うには、すべての所得値をこの人/ノードに合計し、すべての結果を減算します。私の例で:
ステータス:
マッチ最小数(希望常に負である)、最も大きい数字(常に正である)、および最終像のリストを更新する。一致
:例では30 USD:は
ステータス:
繰り返し2全て一致した(ステータスリストが空である)まで。
が一致した:
をあなたはまだここに解決策を探している場合は、答えです他のStackOverflowの質問から、それはソリューションのすべての可能性について非常に詳細になります。リンク:Algorithm to simplify a weighted directed graph of debts
最初の答えはアルゴリズムのアイデアです。 しかし、2番目の回答には、この問題について深く掘り下げた学術論文へのリンクがあります。
ここでは、2つの異なる最適化が可能です。あなたの例は両方(3> 2と60-> 40)です。 – MSalters
私は、純ポジションの変化がないことを条件に総未払債務額を最小限に抑えることは、LP(線形計画問題)として定式化することができると考えています。債務の数を最小限にするには、いくつかのバイナリ変数が必要です(厳密なLPではなく、MIP-混合整数計画問題です)。 –