48

これは一種のより一般的な質問であり、言語固有ではありません。使用するアイデアとアルゴリズムの詳細。

システムは次のとおりです。

友人のグループ間の少額のローンを登録します。ビルのカードが機能していないので、アリスが食事代 10 ドルを支払いますAlice。 翌日、鉄道の駅で会ったチャレスは切符を買うお金がなかったので、5ドルで切符を買いました。その日遅く、友人から 5 ドルと 1ドルを借りて、友人にプレゼントを買いました。Bill
BillCharlesBillAliceCharlesBill

ここで、すべてのトランザクションがシステムに登録されていると仮定すると、次のようになります。

Alice -> Bill $10
Bill -> Alice $1
Bill -> Charles $5
Charles -> Alice $5

ですから、あとは$4Billを渡すだけでAlice(彼は彼女に $1 を渡し、Charlie 彼の $5 をAlicealredy に送金しました)、これで初期状態になりました。

複数のトランザクションを持つ多くの異なる人々にそれをスケーリングする場合、トランザクションをできるだけ少なくするための最良のアルゴリズムは何でしょうか?

4

10 に答える 10

34

これは実際、複式簿記の概念が役立つ仕事のように見えます。

トランザクションは、次のように簿記エントリとして構造化できます。

                          Alice  Bill  Charles  Balance
Alice   -> Bill    $10      10    10-       0        0
Bill    -> Alice    $1       9     9-       0        0
Bill    -> Charles  $5       9     4-       5-       0
Charles -> Alice    $5       4     4-       0        0

そして、あなたはそれを持っています。各取引で、残高が常にゼロになるように、1 つの元帳口座に入金し、別の口座から引き落とします。最後に、各アカウントに適用されるトランザクションの最小数を計算して、アカウントをゼロに戻します。

この単純なケースでは、Bill から Alice への単純な $4 の送金です。あなたがする必要があるのは、追加されたトランザクションごとに、少なくとも 1 つのアカウント (できれば 2 つ) をゼロに減らすことです。より複雑な場合を考えてみましょう:

                          Alice  Bill  Charles  Balance
Alice   -> Bill    $10      10    10-       0        0
Bill    -> Alice    $1       9     9-       0        0
Bill    -> Charles  $5       9     4-       5-       0
Charles -> Alice    $5       4     4-       0        0
Charles -> Bill     $1       4     5-       1        0

次に、必要なトランザクションは次のようになります。

Bill     -> Alice   $4       0     1-       1        0
Bill     -> Charles $1       0     0        0        0

残念ながら、この単純な貪欲な戦略が最善の解決策を生み出さない州がいくつかあります (j_random_hackerこれを指摘してくれたことに感謝します)。一例は次のとおりです。

                 Alan  Bill  Chas  Doug  Edie  Fred  Bal
Bill->Alan   $5    5-    5     0     0     0     0    0
Bill->Chas  $20    5-   25    20-    0     0     0    0
Doug->Edie   $2    5-   25    20-    2     2-    0    0
Doug->Fred   $1    5-   25    20-    3     2-    1-   0

明らかに、これは 4 つの手で逆転する可能性があります (そこに到達するのに必要な手数は 4 つだけなので) が、賢明に最初の手を選択しない場合(Edie->Bill $2)、5 つが最小限で済みます。

この特定の問題は、次のルールで解決できます。

  • (1) 2 つの残高を消去できる場合は、それを実行します。
  • (2) それ以外の場合は、1 つのバランスを一掃し、次の動きで 2 つを一掃する準備ができている場合は、それを実行します。
  • (3) それ以外の場合は、いずれか 1 つの残高を消去します。

その結果、次のシーケンスになります。

  • (a) [1] 該当なし、[2] は で達成できますAlan->Bill $5。
  • (b) [1] でできますChas->Bill $20。
  • (c) と (d)、Doug、Edie、Fred と同様の推論で、合計 4 回の移動。

ただし、可能性の数が少ないため、これは単純に機能します。人数が増え、グループの相互関係がより複雑になると、必要な最小手数を見つけるために徹底的な検索が必要になる可能性が高くなります (基本的には上記のルール 1、2、および 3 ですが、より深く処理するために拡張されます)。 .

それが、あらゆる状況で最小数のトランザクションを提供するために必要なことだと思います. ただし、それは最良の回答には必要ない場合があります (この場合の最良の回答は、最大の「1 ドルあたりの価値」を意味します)。基本的な 1/2/3 ルール セットでさえ、目的に対して十分な答えが得られるかもしれません。

于 2009-05-18T13:43:07.667 に答える
15

この問題を解決する Android アプリを作成しました。旅行中の費用を入力でき、「次に誰が支払うべきか」を提案してくれます。最後に「誰が誰にいくら送るべきか」を計算します。私のアルゴリズムは必要最小限のトランザクション数を計算し、トランザクションをさらに減らすことができる「トランザクション許容度」を設定できます (1 ドルのトランザクションは気にしません) 試してみてください。

https://market.android.com/details?id=cz.destil.settleup

私のアルゴリズムの説明:

n-1 トランザクションの問題を解決する基本的なアルゴリズムがありますが、最適ではありません。これは次のように機能します: 支払いから、各メンバーの残高を計算します。残高は、彼が支払った金額から支払うべき金額を差し引いたものです。ますますバランスに応じてメンバーを振り分けます。それから私はいつも最も貧しい人と最も裕福な人を取り、取引が行われます. それらの少なくとも 1 つは残高がゼロになり、以降の計算から除外されます。これにより、トランザクション数が n-1 より悪くなることはありません。また、取引の金額を最小限に抑えます。しかし、内部で解決できるサブグループが検出されないため、最適ではありません。

内部で解決できるサブグループを見つけるのは困難です。メンバーのすべての組み合わせを生成し、サブグループの残高の合計がゼロに等しいかどうかを確認することで解決します。2 ペアから始めて、次に 3 ペア ... (n-1) ペアです。組み合わせジェネレーターの実装が利用可能です。サブグループが見つかったら、上記の基本的なアルゴリズムを使用してサブグループ内のトランザクションを計算します。見つかったサブグループごとに、1 つのトランザクションが節約されます。

解は最適ですが、複雑さが O(n!) に増加します。これはひどいように見えますが、実際には少数のメンバーしかいないことがトリックです。Nexus One (1 Ghz プロセッサ) でテストした結果は、10 メンバーまで: <100 ミリ秒、15 メンバー: 1 秒、18 メンバー: 8 秒、20 メンバー: 55 秒です。というわけで18人までは実行時間は大丈夫です。メンバーが 15 人を超える場合の回避策は、基本アルゴリズムのみを使用することです (高速で正確ですが、最適ではありません)。

ソースコード：

ソースコードは、チェコ語で書かれたアルゴリズムに関するレポート内で入手できます。ソースコードは最後にあり、英語です。

http://www.settleup.info/files/master-thesis-david-vavra.pdf

于 2011-05-03T09:05:53.670 に答える
6

Excelで実装した実用的な解決策を見つけました：

  • 誰が最も多くを持っているかを調べる

  • その人に、彼が負うべき全額を、最も多く得るべき人に支払わせてください

  • それは一人称をゼロにする

  • （n-1）人のうちの1人が金額を変更したことを考慮して、このプロセスを繰り返します

最大で (n-1) 回の送金が行われるはずであり、その優れた点は、複数回の支払いを行う人がいないことです。jrandomhacker の (変更された) 例を見てみましょう。

a=-5 b=25 c=-20 d=3 e=-2 f=-1 (合計はゼロでなければなりません!)

  1. c -> b 20. 結果: a=-5 b=5 c=0 d=3 e=-2 f=-1

  2. a -> b 5 結果: a=0 b=0 c=0 d=3 e=-2 f=-1

  3. e -> d 2 結果 a=0 b=0 c=0 d=1 e=0 f=-1

  4. f -> d 1

今では、誰もが満足しており、2 回以上の支払いに悩まされることはありません。ご覧のとおり、1 人の人が複数の支払いを受け取る可能性があります (この例では人 d)。

于 2009-11-23T23:24:52.490 に答える
1

誰かが 2 人以上に借りがあり、同じセットにも借りがある場合にのみ、単純なセットからトランザクション数を減らすことができます。

つまり、単純なセットは、それぞれの残高を見つけて返済するだけです。それはNにすぎません！トランザクション。

A が B と C に借りがあり、BC のサブセットが互いに借りている場合、B は C に借りがあるため、代わりに、A -> B、A -> C (3 トランザクション) になります。A -> B、B -> C (2 トランザクション) を使用します。

つまり、有向グラフを作成していて、パスの長さを最大化し、エッジの合計を最小化するために頂点をトリミングしたいということです。

申し訳ありませんが、私はあなたのためのアルゴリズムを持っていません.

于 2009-05-18T13:40:33.710 に答える
-1

状態をグラフのノードとして使用すると、最短経路アルゴリズムを使用して答えを知ることができます。

于 2009-05-18T13:34:28.480 に答える