マッチングのロジックについて

Question

実際の業務の内容を簡略化していますが、以下のようなケースについて、ロジックを考えています。
皆さんならどのようにロジックを考えますか。
ロジック（アルゴリズム）なので、言語は問いません。

４人の子供がおやつを選んでいます。
おやつは「ケーキ」「プリン」「いちご」「メロン」の４つで、それぞれ１つしかありません。
子どもたちは自分の欲しいおやつを第１希望～第３希望まで決められます。

ここでおやつと子どものマッチングロジックについて、以下の２つのロジックで考えます。

１．１位に選んだおやつを優先的に獲得できるロジック
２．おやつをなるべく希望に沿うように選択するロジック
※第１～３位のおやつ以外がなるべく行き渡らないようにするロジック

１、２のロジックの考え方について教えてください。

なお、１位で被った場合は、再び選択させるのではなく、ランダム（乱数）で良いです。
（子供たちは結果に対してケンカしないものとします）

■6/24 12:35 追記

こちらの質問が他のユーザから「やってほしいことだけを記載した丸投げの質問」という指摘を受けました 「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

すみません、丸投げのつもりはなかったのですが、この手の質問の仕方はteratailではNGなのですね。
勉強になりました。

私の考えです。

１．１位に選んだおやつを優先的に獲得できるロジック

• １つ目のおやつを選択する
• １つ目のおやつを第１位に選んだ人を検索する
• 第１位に選んだ人が複数人いる場合は、乱数により決定する（１つ目のおやつと子どもをマッチングする）
• 第１位に選んだ人がいなかった場合はマッチングをスキップする
• 次のおやつに進む
• すべてのおやつに対して上記操作を行う
• おやつと子どものマッチングがすべて完了していたらマッチング終了
• マッチングが完了していなければ、検索対象を第２として１つ目のおやつから検索する
• マッチングが完了するまで、第３位、選択なしの順に検索対象をずらしていく

２．おやつをなるべく希望に沿うように選択するロジック
※第１～３位のおやつ以外がなるべく行き渡らないようにするロジック

• １つ目から４つ目までのおやつに対して、おやつの選択の数を検索する
• おやつの選択の数が１つのおやつについてループする
• おやつを選択した子どもとおやつをマッチングする
• おやつの選択の数が１つのおやつについてのループが完了した後に、マッチング済みのおやつと子どもを除いて、再度おやつの選択の数を検索する
• おやつの選択の数が１つのおやつについてループして、おやつと子どもをマッチングする
• このループを繰り返し、選択の数が１つのおやつが無くなったら次に進む
• １つ目のおやつを選択し、複数選択されているはずなので、順位の高い人とマッチングする。順位が同位で複数人いた場合は乱数による決定とする。
• ２つ目のおやつでも同じように順位の高い人とマッチングする
• この操作をすべてのマッチングが完了していないおやつと子どもに対して実施する
• 最後に、全く選択されていないおやつがあれば、おやつと最後に残った人をマッチングする

１も２もキレイなロジックではないと思いますが、いまいち良いロジックが思い浮かびません。

Comments

[gentaro]

回答者に対して問題を出すのは「やってほしいことだけを記載した丸投げの質問」という理由で低評価が付きやすいです。自分ならどう考えるのか、その解決策にどのような問題があると認識しているのかを書きましょう。

[OtaMasato]

ご指摘ありがとうございます。「自分ならどう考えるのか」と「どのような問題点があるのか」について追記しました。

Answer 1

2部グラフを作成して、マッチング問題として解けばよいかと思います。

• 頂点集合

V1 = {'Aさん', 'Bさん', 'Cさん', 'Dさん'}
V2 = {'メロン', 'いちご', 'プリン', 'ケーキ'}

• 辺集合

Aさんがメロンを第1希望としていた場合、(Aさん、メロン) という辺を作成する。
辺の重みを 第1希望 > 第2希望 > 第3希望となるようにつける。

• アルゴリズム

2部グラフの最大重みマッチング

Maximum Matching in General Graphs
最大重みマッチング問題

できる限り各個人の希望を反映したマッチング ==> 最大重みマッチングです。

Python のサンプルコード

Python だと networkx というグラフライブラリの max_weight_matching() という関数で実装されています。

networkx.algorithms.matching.max_weight_matching — NetworkX 2.4rc1.dev20190623123601 documentation

import networkx as nx

# 子供の希望
wishes = {
    # "名前": [第1希望, 第2希望, 第3希望]
    "Aさん": ["プリン", "ケーキ", "メロン"],
    "Bさん": ["ケーキ", "いちご", "メロン"],
    "Cさん": ["いちご", "プリン", "ケーキ"],
    "Dさん": ["プリン", "いちご", "メロン"],
}

# グラフを作成する。
G = nx.Graph()
for person, wish in wishes.items():
    for snack, weight in zip(wish, range(3, 0, -1)):
        # (人, 希望するお菓子) という辺を追加する。
        # 重みは第1希望: 3, 第2希望: 2, 第3希望: 1 になる。
        G.add_edge(person, snack, weight=weight)

# 「重み最大となるマッチング」を探す。
matches = nx.max_weight_matching(G)
print(matches)
# {('ケーキ', 'Bさん'), ('プリン', 'Dさん'), ('いちご', 'Cさん'), ('Aさん', 'メロン')}

y = sum([G.edges[e1, e2]["weight"] for e1, e2 in matches])
print(f"y = {y}")

追記 整数計画問題として解く方法

次のように変数を定義することで整数計画問題としても定式化できます。

PuLP という線形ソルバーで説いたところ、networkx の最大重みマッチングの結果と一致することが確認できました。

from pulp import *

# お菓子の一覧
snacks = ["いちご", "キャラメル", "ケーキ", "プリン", "メロン"]

# 子供の希望
wishes = {
    # "名前": [第1希望, 第2希望, 第3希望]
    "Aさん": ["プリン", "ケーキ", "メロン"],
    "Bさん": ["ケーキ", "いちご", "メロン"],
    "Cさん": ["いちご", "プリン", "キャラメル"],
    "Dさん": ["プリン", "いちご", "メロン"],
}

# モデルを作成する。
model = LpProblem(name="max weight matching", sense=LpMaximize)

# # 変数を作成する。
X = [
    [LpVariable(f"{person}_{snack}", cat=LpBinary) for snack in snacks]
    for person in wishes
]

# 目的関数を設定する。
weights = range(3, 0, -1)  # 重み: 第1希望:3、第2希望:2、第3希望:1
snack_to_idx = {name: i for i, name in enumerate(snacks)}  # お菓子の名前がキー、インデックスが値の辞書

y = 0
for i, wish in enumerate(wishes.values()):
    for snack, w in zip(wish, weights):
        j = snack_to_idx[snack]
        y += X[i][j] * w
model += y

# 制約を設定する。

# (1) 一人1つしかお菓子を選べない。
for i in range(len(wishes)):
    model += lpSum(X[i]) == 1

# (2) 二人以上が同じお菓子を選べない。
for j in range(len(snacks)):
    s = 0
    for i in range(len(wishes)):
        s += X[i][j]
    model += s <= 1

# モデルを表示する。
print(model)

# 解く。
ret = model.solve()
print("status", LpStatus[ret])  # status Optimal

# 解けた場合は結果を表示する。
if ret == 1:
    print(f"y = {model.objective.value()}")
    for i, person in enumerate(wishes):
        select_idx = np.argmax([x.value() for x in X[i]])  # 選択したお菓子のインデックス
        print(f"{person}: {snacks[select_idx]}")

max weight matching:
MAXIMIZE
2*Aさん_ケーキ + 3*Aさん_プリン + 1*Aさん_メロン + 2*Bさん_いちご + 3*Bさん_ケーキ + 1*Bさん_メロン + 3*Cさん_いちご + 1*Cさん_キャラメル + 2*Cさん_プリン + 2*Dさん_いちご + 3*Dさん_プリン + 1*Dさん_メロン + 0
SUBJECT TO
_C1: Aさん_いちご + Aさん_キャラメル + Aさん_ケーキ + Aさん_プリン + Aさん_メロン = 1

_C2: Bさん_いちご + Bさん_キャラメル + Bさん_ケーキ + Bさん_プリン + Bさん_メロン = 1

_C3: Cさん_いちご + Cさん_キャラメル + Cさん_ケーキ + Cさん_プリン + Cさん_メロン = 1

_C4: Dさん_いちご + Dさん_キャラメル + Dさん_ケーキ + Dさん_プリン + Dさん_メロン = 1

_C5: Aさん_いちご + Bさん_いちご + Cさん_いちご + Dさん_いちご <= 1

_C6: Aさん_キャラメル + Bさん_キャラメル + Cさん_キャラメル + Dさん_キャラメル <= 1

_C7: Aさん_ケーキ + Bさん_ケーキ + Cさん_ケーキ + Dさん_ケーキ <= 1

_C8: Aさん_プリン + Bさん_プリン + Cさん_プリン + Dさん_プリン <= 1

_C9: Aさん_メロン + Bさん_メロン + Cさん_メロン + Dさん_メロン <= 1

VARIABLES
0 <= Aさん_いちご <= 1 Integer
0 <= Aさん_キャラメル <= 1 Integer
0 <= Aさん_ケーキ <= 1 Integer
0 <= Aさん_プリン <= 1 Integer
0 <= Aさん_メロン <= 1 Integer
0 <= Bさん_いちご <= 1 Integer
0 <= Bさん_キャラメル <= 1 Integer
0 <= Bさん_ケーキ <= 1 Integer
0 <= Bさん_プリン <= 1 Integer
0 <= Bさん_メロン <= 1 Integer
0 <= Cさん_いちご <= 1 Integer
0 <= Cさん_キャラメル <= 1 Integer
0 <= Cさん_ケーキ <= 1 Integer
0 <= Cさん_プリン <= 1 Integer
0 <= Cさん_メロン <= 1 Integer
0 <= Dさん_いちご <= 1 Integer
0 <= Dさん_キャラメル <= 1 Integer
0 <= Dさん_ケーキ <= 1 Integer
0 <= Dさん_プリン <= 1 Integer
0 <= Dさん_メロン <= 1 Integer

status Optimal
y = 10.0
Aさん: メロン
Bさん: ケーキ
Cさん: いちご
Dさん: プリン

Comments

[OtaMasato]

ご回答ありがとうございます。「2部グラフの最大重みマッチング」なんてロジックがあるんですね。
まだ内容理解できてませんが、言葉の意味からするとドンピシャのように思えます。
また、Pythonのコードご提示ありがとうございます。
今回のロジックをコードに落とし込む際に大変参考になります。

[tiitoi]

整数計画問題として解く方法も思いついたので追記しました。
今回の問題は次のいずれかで解くのがいいと思います。

グラフ理論で解く:
第1希望 > 第2希望 > 第3希望となるような重み付けをした2部グラフ作成 → 最大重みマッチング

整数計画問題として解く:
追記のように定式化

> まだ内容理解できてませんが

問題の定式化が理解できれば、アルゴリズム自体は理解できなくても問題ないです。
実際は自分で1から実装するより、ライブラリを使って解くことをおすすめします。
Python の場合、グラフ問題 → networkx、整数計画問題 → Pulp というライブラリで解けますが、
もし他の言語をお使いの場合でも同様にライブラリがあるので、それを使うといいかと思います。

[OtaMasato]

追加のご提案ありがとうございます。
整数計画問題についても見てみます。
また、pythonのコードについても環境作ってみたので、実際に動かしてみます。

[OtaMasato]

「2部グラフの最大重みマッチング」を試してみたところ、いい感じに結果を得ることができました！ご協力いただきありがとうございます。
整数計画問題の方は、貼り付けの仕方が悪かったのか、途中でエラーになっていました。ちょっと見てみようと思います。

Answer 2

1のロジックは、

1.一人しか1位に選んでいないおやつを探して確定する。
2.残りの人達が2位に選んでいるおやつが、1のおやつでもなく他に選んでいる人がいない場合は確定する。
3.まだ残っている場合は、ランダムで確定する。

Comments

[OtaMasato]

１のロジックはご提案の内容がきれいですね。
（私の複数人だったら乱数で決定する→複数人いなければ決定する、にされていますね）
ありがとうございます。

Answer 3

2のロジックですが組み合わせ数が少ないなら以下のようにできますね。(te2jiさんと同じ）

• 第一希望のおやつがきた => 3
• 第二希望のおやつがきた => 2
• 第三希望のおやつがきた => 1
• 希望していないものがきた => 0

例：全員第一希望のおやつが来た => 3 x 4 = 12

というふうに配点をして、4!(=24)通りの組み合わせについて点数を付けてみればいいです。
最高点で同点のものがあればランダムで一つ組み合わせを決定すれば良いと思います。

---

2019-06-25 追記

少年Ａと少年Ｂがケーキを第１希望とし、少年Ｃ、少年Ｄがケーキを第２希望とした場合、３＋３＋２＋２で１０になると思いますが、

いや、問題設定に従うと全員違うおやつになるはずですよね？
もし少年Aが「ケーキ」だったときには3点としてカウントし、他の少年も同様に配られたおやつで採点するだけです。
もし ["プリン", "ケーキ", "いちご", "メロン"] という配り方をした場合、この組み合わせの評価は何点か？を計算しているだけですよ。

以下、採点までを行うRubyのコードです。

# ["ケーキ","プリン","いちご","メロン"]を並べ替えたすべての組み合わせ（24個）
PERMIRATIONS = ["ケーキ","プリン","いちご","メロン"].permutation(4).to_a

# 4人がそれぞれ欲しい順
wants = Array.new(4) { PERMIRATIONS.sample }
#[
#  ["いちご", "メロン", "ケーキ", "プリン"],
#  ["いちご", "ケーキ", "メロン", "プリン"],
#  ["プリン", "ケーキ", "いちご", "メロン"],
#  ["いちご", "メロン", "ケーキ", "プリン"]
#]

# すべての組み合わせについて採点
result = {}
PERMIRATIONS.each { |a|
  total = 0
  a.each_with_index { |b, i|
    total += 3 - wants[i].index(b)
  }
  result[a] = total
}

# 結果
result
#{["ケーキ", "プリン", "いちご", "メロン"]=>4,
# ["ケーキ", "プリン", "メロン", "いちご"]=>4,
# ["ケーキ", "いちご", "プリン", "メロン"]=>9,
# ["ケーキ", "いちご", "メロン", "プリン"]=>4,
# ["ケーキ", "メロン", "プリン", "いちご"]=>8,
# ["ケーキ", "メロン", "いちご", "プリン"]=>3,
# ["プリン", "ケーキ", "いちご", "メロン"]=>5,
# ["プリン", "ケーキ", "メロン", "いちご"]=>5,
# ["プリン", "いちご", "ケーキ", "メロン"]=>7,
# ["プリン", "いちご", "メロン", "ケーキ"]=>4,
# ["プリン", "メロン", "ケーキ", "いちご"]=>6,
# ["プリン", "メロン", "いちご", "ケーキ"]=>3,
# ["いちご", "ケーキ", "プリン", "メロン"]=>10,
# ["いちご", "ケーキ", "メロン", "プリン"]=>5,
# ["いちご", "プリン", "ケーキ", "メロン"]=>7,
# ["いちご", "プリン", "メロン", "ケーキ"]=>4,
# ["いちご", "メロン", "ケーキ", "プリン"]=>6,
# ["いちご", "メロン", "プリン", "ケーキ"]=>8,
# ["メロン", "ケーキ", "プリン", "いちご"]=>10,
# ["メロン", "ケーキ", "いちご", "プリン"]=>5,
# ["メロン", "プリン", "ケーキ", "いちご"]=>7,
# ["メロン", "プリン", "いちご", "ケーキ"]=>4,
# ["メロン", "いちご", "ケーキ", "プリン"]=>7,
# ["メロン", "いちご", "プリン", "ケーキ"]=>9}

Comments

[kasa0]

２の場合は、0点の人がいないという条件で絞り込めますね。

[mather]

いえ、そうは行かないと思います。
ワーストケースとして希望しないおやつが全員同じということがありえます。

[kasa0]

はい、必ずではありませんが、絞り込み条件として使用できるということです。
同じ得点なら0点の人がいない方を選択とか。

[mather]

う〜ん。絞り込みっていう言い方がおかしいと思います。
「希望しないおやつが全員同じ」というケースが発生した時点で、どんな組み合わせを使っても0点の人がいますし、目的は「おやつをなるべく希望に沿うように選択する」なので絞り込みも何もなくて組み合わせの中で最高点のものが選ばれるだけだと思います。

[kasa0]

最高点が[3,2,2,0],[3,2,1,1]の2パターンの場合はどうですか？

[mather]

そういう意味の絞り込みなのですね。
配点に関しては「なるべく希望に沿うように」のバイアス次第だと思います。
例えば配点を[100, 10, 1, 0] （なるべく高い希望にフィットさせる）としてもいいですし、[10. 9. 8. 0]（希望していないおやつをなるべく選ばない）とするのもいいでしょう。

[OtaMasato]

ご回答ありがとうございます。
すみません、理解が追い付いていないのですが、「全員第一希望のおやつが来た => 3 x 4 = 12」はどのように求められているのでしょうか。
少年Ａと少年Ｂがケーキを第１希望とし、少年Ｃ、少年Ｄがケーキを第２希望とした場合、３＋３＋２＋２で１０になると思いますが、この１０という数字と、少年Ａ、Ｂの乱数対決がどのように紐づくのかがわかりませんでした。
理解が追い付いていなく、申し訳ありません。

[OtaMasato]

> いや、問題設定に従うと全員違うおやつになるはずですよね？
> もし少年Aが「ケーキ」だったときには3点としてカウントし、他の少年も同様に配られたおやつで採点するだけです。

ご指摘ありがとうございます。
考え違いしていました。
希望に対して点数をつけるのではなく、配布した場合について点数をつけるということですね。
ちょっと計算してみます。

Answer 4

組み合わせは高々24通りなので、今見えてる3つのルールに対してスコアを付け、最大となる組み合わせを提示すればよいかと。

Comments

[OtaMasato]

スコアは私も最初考えていたのですが、具体的にどのようにロジックに落とし込めばよいのかわかりませんでした。自分の選択（１～３位）だけでなく、他の子どもたちの選択も考慮してスコアを付ければいい感じにできそうですね。（人気のないおやつを選択している場合は高スコアのように）
ご回答ありがとうございます。

Answer 5

子供Ａが「ケーキ」「プリン」「いちご」の順（ケーキが第一希望）で希望しており
他全員が「いちご」を(第一～第三までに)希望していないとしたら，
Aにケーキを割り当てる（すると，他の誰かに「いちご」が行く）ことと，
他の者に「いちご」を割り当てないようにすることと，
一体どちらを優先するのでしょう？

後者側の事柄を優先するならば，
不人気な物から順に割り振っていけば良いように思います．
（最も総合的に選ばれていないおやつを，それを最もマシに捉えている子供に割り当てる）

Comments

[OtaMasato]

> 子供Ａが「ケーキ」「プリン」「いちご」の順（ケーキが第一希望）で希望しており
> 他全員が「いちご」を(第一～第三までに)希望していないとしたら，
> Aにケーキを割り当てる（すると，他の誰かに「いちご」が行く）ことと，
> 他の者に「いちご」を割り当てないようにすることと，
> 一体どちらを優先するのでしょう？

２のロジックでは、Aにケーキを割り当てるのではなく、「いちご」を割り当てたいと考えています。

> 後者側の事柄を優先するならば，
> 不人気な物から順に割り振っていけば良いように思います．
> （最も総合的に選ばれていないおやつを，それを最もマシに捉えている子供に割り当てる）

やっぱりそうなりますよね。
後から追記しましたが、私のロジックはご指摘の内容になっていると思います。
不格好に見えるのですが・・・。

Answer 6

１．１位に選んだおやつを優先的に獲得できるロジック

普通に１位を選ばせるだけなのでロジックも何もありません

２．おやつをなるべく希望に沿うように選択するロジック

※第１～３位のおやつ以外がなるべく行き渡らないようにするロジック

たとえば全員が同じ順番でおやつを選んだ場合
かならず誰かが第４希望を得るしかありません、

１位で被った場合は、再び選択させるのではなく、ランダム（乱数）で良い

ちょっと意味がわからない。
１位でかぶったら話し合いをしないでどちらかがランダムでヒットして
もう一方は２位以降の希望にまわるという意味でしょうか？

基本的にはプロ野球のドラフト１位指名とおなじ方式だと考えればよいでしょう

Comments

[OtaMasato]

ご回答ありがとうございます。
分かりづらくて申し訳ありません。

> 引用テキスト普通に１位を選ばせるだけなのでロジックも何もありません

実装するにはロジックは必要と思うのですが・・・
私のイメージについて追記させていただきました。

> たとえば全員が同じ順番でおやつを選んだ場合
> かならず誰かが第４希望を得るしかありません、

はい、この場合はやむを得ないかと思います。
ただ、例えば、ケーキを全員が第１希望として、メロンの希望が第２希望１人だけだったとしたら、メロンの第２希望の人がケーキを取ると、メロンは希望しない人にわたってしまうことになるので、２のロジックはこの点を考慮したいといった意図になります。（１のロジックはこの点を考慮しないことになります）

> ちょっと意味がわからない。
> １位でかぶったら話し合いをしないでどちらかがランダムでヒットして
> もう一方は２位以降の希望にまわるという意味でしょうか？

その認識であっています。