複雑な割り勘の計算方法

よく友人多くで旅行に行きますが、旅費の清算の方法が面倒なので、なにか行列などをつかったエレガントな計算方法が無いかお知恵をお借りしたく思います。

イメージはこんな感じです。

A, B, Cの3人が旅行に行き、
Aさんが、A，Bの新幹線代金　20000 円を支払ったのに加え、AとCのガソリン代 8000 円を支払う
BさんがA, B, Cの食事代　6000 円をまとめて支払い
Cさんはまったく支払っていない
といった場合のときに、

うまく、A, B, Cさんの間での清算のための最終的なお金のやり取りをできるだけ、回数が少なくなるようにする分け方を考えたいと思っています。(
たとえば、振込みで清算するとすると振込み手数料がもっともかからない方法）（これは解がひとつになりそうも無いので、うまくできないかも知れません。）

3人で3つの支払いなら、まだ手計算で簡単ですが、これを一般的にM人でN取引があった場合の一般的な解法などはあるのでしょうか？行列などを使ってエレガントに説く方法はありますか？

すこし考えて見ましたが、
それぞれの行を各支払い（新幹線、ガソリン、食事の３行）にとって、それぞれの列を人にとって考えると（A, B, Cさんの３人）

行列　F = (20000, 8000, 6000) が支払金額の行列 （縦の行列ですが、横に書いています。）
G =　
1,0,0
1,0,0
0,1,0
が支払った人を示す行列で、負担すべき人を示す行列は
H =
1,1,0
1,0,1
1,1,1
とすると、
I = G F がそれぞれの支払った金額で、J(i) = ( F(i) / Σj H(i,j) )としたときに
K = H J はそれぞれの使った（負担すべき）金額になり、
L = I - K としたときに、M(j) = Σi L(i,j) がそれぞれの人のネット支払・受取額となるところまでは考えてみたのですが、そこからが難しいです。（もっと簡単な計算やわかりやすい見せ方があるかもしれませんし、間違っているかもしれません。）ちなみに上の例では M=(12000, -6000, -6000)

そこから、３人以上の人数になったときの一般的に一番支払い回数が少なくする受け渡しのやり方をする方法が思いつきません。

よろしくお願いいたします。

No.1 回答者： stomachman 回答日時： 2010/03/19 17:57

　折角一緒に旅行するのに、なんで振り込みなんて面倒なことを？

　N人全員がそれぞれ同じ金額を負担するという割り勘ルールなら、とても便利な方法があります。
　出発時に全員が1万円ずつ出して、「共用財布」に入れる。旅行中の支払いは全て共用財布から行う。（もちろん、個人都合の支出は自分で払って貰いますが。）途中で共用財布が空になったらまた全員が1万円ずつ補充する。で、解散する前に、共用財布の中身を全員均等に分ける。これなら幾ら払ったかの記録すら必要ありません。
　というのはさておきです。

> 振込み手数料がもっともかからない方法

　振り込んでもらう側は手数料が要らない。どうしても振り込みをしなければならないのは払い足りない人全員で、一人で何人にも振り込みをするとなると、それだけ手数料が掛かる。手数料は一定だとしますと、振り込みの回数を最小にしろ、ということですね。こりゃどうやら組み合わせ論の問題であって、具体的な数値によって答が違ってくる。振込み手数料も割り勘しなきゃならんでしょう。うわーめんどくさいですね。人数が少し増えただけでも、プログラムを書いて総当たり的な探索をしないと解けないんじゃないかな。
　基本的にはどう考えるかというと：
精算の必要な人（払いすぎの人と払い足りない人）がN人いるとする。N人中のあるM人(M＜N)を選んでグループを作り、彼らの精算額の合計が0になるようにできたとします。(従って、残りのN-M人から成るグループについても彼らの精算額の合計は0です。）すると元の問題は、M人の中での精算の問題と、N-M人の中での精算の問題に分割して考えることができます。このような問題の分割を徹底的にやって、なるべく多くのグループに分けるんです。N人がK個のグループに分けられたとする。
　各グループの中では、以下のように精算することにします。払い足りない人を先頭に、メンバーJ人を一列に並べる。で、先頭の人が自分の払うべき額を2番目の人に振り込む。2番目のひとは、それに自分の払うべき額を足して（あるいは自分の受け取るべき額を差し引いて）3番目の人に振り込む。すると（末尾の人は振り込みをしないので）J-1回の振り込みを行うことになります。途中で振り込み額が0円になることはない。なぜなら、もしそうできるのなら、このグループはさらに分割できるからです。
　従って、振り込みの回数はN-K回です。最良2人ずつのグループに分けられた場合にはN/2回、最悪ならN人が1グループのまんまでN-1回。

この回答への補足

ご返答ありがとうございます。ちょっとよくわからないところがあるので、追加でお教えいただけると助かります。

＞　折角一緒に旅行するのに、なんで振り込みなんて面倒なことを？

振込みは実際は手数料無料だったりする場合があるなど、問題ないときが多いのですが、面倒を減らすということから、「振り込みの回数を最小にしろ」という趣旨にして、振込み手数料の割り勘などは無視して考えていただけますか。

＞払い足りない人を先頭に、メンバーJ人を一列に並べる。で、先頭の人が....

のところは、金額順にマイナスから並べていくということですか？そうすると、途中で振込み額がゼロになるということはどんな場合でもないような気がするのですが。それとも、並び方は考えなくてもいいのでしょうか？


＞振り込みの回数はN-K回です。最良2人ずつのグループに分けられた場合にはN/2回

Kグループに分けられたとして、M(K)をそれぞれのグループの構成員の数とすると ΣM(K)=Nという考え方でよろしいのでしょうか？そうすると、Σ(M(K)-1)=N-Kということですね。そこまではわかるのですが、

＞精算の必要な人（払いすぎの人と払い足りない人）がN人いるとする。N人中のあるM人(M＜N)を選んでグループを作り、彼らの精算額の合計が0になるようにできたとします。

の分け方がわかりません。どのような方法で分割していけばいいのでしょうか？これを総当り的な探索しかすることができないということでしょうか？


いろいろ、質問攻めですいません。

補足日時：2010/03/23 15:05

No.2 ベストアンサー 回答者： stomachman 回答日時： 2010/03/24 05:00

ANo.1のコメントについてです。

> 振込み手数料の割り勘などは無視

　了解です。
　精算が必要な人の中から誰か一人を決めて(kさんとしましょう)、払い足りない人全員がkさんに振り込み、次にkさんが払いすぎの人それぞれに振り込めば、「振り込みをしなくてはいけない人の数」が最小にできる。現実的にはこの手だろうと思いますが、それはさておき、（人数ではなく）振り込みの回数を最小にするという問題を考える。

> 金額順にマイナスから並べていくということですか？

いいえ違います。たとえば
A: 10000円払い足りない
B: 10000円払い過ぎ
C: 5000円払い足りない
D: 5000円払いすぎ
のとき、ABCDの順に並べば、BはCに0円振り込むことになるので、(AB)と(CD)の2グループに分ければ2回の振り込みで済む。ご質問を、「そういう旨い並べ方を見つけなさい」という問題に焼き直したのです。

> の分け方がわかりません。どのような方法で分割していけばいいのでしょうか？

　総当たりで調べたのでは人数が増えると計算が膨大になるんで、もっとましな方法はないか。いろいろ工夫できそうですが、一発で答が出る綺麗な方法はどうも思いつきません。

　まずは「とにかく２グループに分けてから、それぞれのグループをさらに細分化していく」という方針が考えられます。さて、払いすぎの人の額を正の値、払い足りない人の額を負の値で表して、たとえば
X[1]=(1,3,-4), X[2]=(2,2,-1,-3)
とグループを作ったとすると、グループX[1]もグループX[2]もこれ以上細分化できない。けれども、別の分け方
Y[1]=(1,-1), Y[2]=(3,-3), Y[3]=(2,2,-4)
が存在する。なので、上記の方針で一直線に答にたどり着くという風には行かず、行ったり来たり(back tracking)の探索が必要だろうと思われます。したがって、人数が増えると計算の手間はもの凄い勢いで増えるでしょう。（どっかで類似のアルゴリズムを見たことあるような気がするんですが、思い出せないなー。）

　ともあれ幾つか、探索効率を上げるのに利用できそうな性質を考えてみると：
● どのグループにも払い足りない人と払い過ぎの人が、それぞれ少なくとも1人入る。なので、払いすぎの人の人数をn、払い足りない人の人数をmとすると、グループの数Mは M≦(n, mの小さい方）を満たす。
● 「ある人pが入って出来るグループは、全員で作るグループ以外には1通りのグループGしかない」ような人pが居た場合、そのグループGは確定。以後、Gのメンバーは除外して考えて良い。（言い換えると、あるグループGに「ある人pの精算額xについて、-xはGの他の全員の精算額の和以外では表せない」ような人pがもし一人でも居たら、グループGはそれ以上分割できない。）
● 2人だけのグループGが作れる場合、そのグループGは確定。以後、その二人は除外して考えて良い。たとえばX[1]=(1,-1), X[2]=(r) （rは残りの人全部の列を表す）にグループ分けしたとすると、あとはX[2]を細分化していけば良い。
　なぜなら、もし全員(1,-1,r)をY[1]=(1,x) , Y[2] = (-1, y) (x, yはそれぞれ何人かの集まり）, Y[3]=(s) (sは残りの人全部）とも分けられたとすると、 X[2]=(r)=(x, y, s) だから、X[2]は(x,y)と(s)とに分けられることになる。XでもYでも、いずれにせよ「3つグループができて、さらに(s)が分けられるかも知れない」という状況は同じ。なので、分け方Yを採用しても、分け方Xに比べてグループ数がより多くなることはない。
（● しかし、3人だけのグループが出来ても確定とは言えない。たとえば、
X[1]=(1,2,-3), X[2]=(5,11,23,-6,-13,-20)
と分けたときX[1], X[2]はこれ以上分けられないけれども、
Y[1]=(1,5,-6), Y[2]=X[2]=(2,11,-13), Y[3}=(-3,-20,23)
とできる。）
● 2人で出来るグループを全部除いてしまった残りをN人とすると、このN人をどう分けてもどのグループも最低3人入るから、残りの人たちN人を分けたグループの数MはM≦N/3である。

　以上を応用するだけでも、探索の手間が総当たりよりはずっと少なくできるでしょう。だけどもっと旨い手はないかなあ。

この回答へのお礼

ありがとうございます。考え方がよくわかりました。でも、なかなか、すっきりした回答はないものですね。

ただし、考えましたが、たぶん実際のケースでは、２番目の「ある人pの精算額xについて、....グループGはそれ以上分割できない。」の部分が制限になって、ほとんど分割ができなくなるような気がしました。なぜなら、実際の旅費の清算だと、金額が十円や一円単位になるのに対して、清算する人数はせいぜい１０名以内の場合が多いでしょうから、この２番目の条件が引っかかって、分割ができないか、できたとしても一回分割できるのがせいぜいの気がします。

そうすると、ご提案いただいた規則で、ほとんど絞り込みはできますね。
当然、一般化をして、定式化するのとは違いますし、それはなかなか難しそうです。

2人だけのグループが作れる場合、そのグループは確定という点や、対照的に３人のグループができても確定ではないというのは面白いポイントだとおもいました。

ありがとうございます。

お礼日時：2010/03/24 18:00