循環有向グラフまたはほとんどのトーナメントの辺を削除し、辺の数が最小のツリー型の構造を出力するアルゴリズムが必要でした。
単純な実世界の例として以下で説明するように、除去は辺の重みに基づく必要があります。
A、B、Cの友達が3人いる場合。お互いの間でお金を借りたり返したりするシナリオを考えてみましょう。
人物Aは人物Bを転送する必要があります-$10。人物Bは人物Cを転送する必要があります-$20。人物Cは人物Aを転送する必要があります-$20。
相互の送金回数を最小限に抑えるための最終決済では、上記を「BさんがAさんを転送します-$ 10」のように並べ替えると、すべてが決済されます。
各辺と方向の重みが与えられたときに、任意の数のノードで機能するアルゴリズムを探しています。
グラフを再配置でき、グラフが「トーナメント」であり、各ノードがグラフ内のすべてのノードに接続されている可能性が高いことを考えると、私が従う最善のアプローチは何でしょうか。