回答編集履歴
3
d
answer
CHANGED
|
@@ -17,6 +17,7 @@
|
|
|
17
17
|
2部グラフの最大重みマッチング
|
|
18
18
|
|
|
19
19
|
[Maximum Matching in General Graphs](https://www.slideshare.net/akhayyat/maximum-matching-in-general-graphs)
|
|
20
|
+
[最大重みマッチング問題](http://www.ocw.titech.ac.jp/index.php?module=General&action=DownLoad&file=201702129-632-0-12.pdf&type=cal&JWC=201702129)
|
|
20
21
|
|
|
21
22
|
できる限り各個人の希望を反映したマッチング ==> 最大重みマッチングです。
|
|
22
23
|
|
|
@@ -41,13 +42,140 @@
|
|
|
41
42
|
# グラフを作成する。
|
|
42
43
|
G = nx.Graph()
|
|
43
44
|
for person, wish in wishes.items():
|
|
44
|
-
for
|
|
45
|
+
for snack, weight in zip(wish, range(3, 0, -1)):
|
|
45
46
|
# (人, 希望するお菓子) という辺を追加する。
|
|
46
|
-
# 重みは第1希望:
|
|
47
|
+
# 重みは第1希望: 3, 第2希望: 2, 第3希望: 1 になる。
|
|
47
|
-
G.add_edge(person, snack, weight=
|
|
48
|
+
G.add_edge(person, snack, weight=weight)
|
|
48
49
|
|
|
49
|
-
# 「
|
|
50
|
+
# 「重み最大となるマッチング」を探す。
|
|
50
|
-
matches = nx.max_weight_matching(G
|
|
51
|
+
matches = nx.max_weight_matching(G)
|
|
52
|
+
print(matches)
|
|
51
|
-
# {('ケーキ', 'Bさん'), ('
|
|
53
|
+
# {('ケーキ', 'Bさん'), ('プリン', 'Dさん'), ('いちご', 'Cさん'), ('Aさん', 'メロン')}
|
|
54
|
+
|
|
55
|
+
y = sum([G.edges[e1, e2]["weight"] for e1, e2 in matches])
|
|
56
|
+
print(f"y = {y}")
|
|
57
|
+
```
|
|
58
|
+
|
|
59
|
+
## 追記 整数計画問題として解く方法
|
|
60
|
+
|
|
61
|
+
次のように変数を定義することで整数計画問題としても定式化できます。
|
|
62
|
+
|
|
63
|
+
|
|
64
|
+
|
|
65
|
+
[PuLP](https://pythonhosted.org/PuLP/) という線形ソルバーで説いたところ、networkx の最大重みマッチングの結果と一致することが確認できました。
|
|
66
|
+
|
|
67
|
+
```python
|
|
68
|
+
from pulp import *
|
|
69
|
+
|
|
70
|
+
# お菓子の一覧
|
|
71
|
+
snacks = ["いちご", "キャラメル", "ケーキ", "プリン", "メロン"]
|
|
72
|
+
|
|
73
|
+
# 子供の希望
|
|
74
|
+
wishes = {
|
|
75
|
+
# "名前": [第1希望, 第2希望, 第3希望]
|
|
76
|
+
"Aさん": ["プリン", "ケーキ", "メロン"],
|
|
77
|
+
"Bさん": ["ケーキ", "いちご", "メロン"],
|
|
52
|
-
|
|
78
|
+
"Cさん": ["いちご", "プリン", "キャラメル"],
|
|
79
|
+
"Dさん": ["プリン", "いちご", "メロン"],
|
|
80
|
+
}
|
|
81
|
+
|
|
82
|
+
# モデルを作成する。
|
|
83
|
+
model = LpProblem(name="max weight matching", sense=LpMaximize)
|
|
84
|
+
|
|
85
|
+
# # 変数を作成する。
|
|
86
|
+
X = [
|
|
87
|
+
[LpVariable(f"{person}_{snack}", cat=LpBinary) for snack in snacks]
|
|
88
|
+
for person in wishes
|
|
89
|
+
]
|
|
90
|
+
|
|
91
|
+
# 目的関数を設定する。
|
|
92
|
+
weights = range(3, 0, -1) # 重み: 第1希望:3、第2希望:2、第3希望:1
|
|
93
|
+
snack_to_idx = {name: i for i, name in enumerate(snacks)} # お菓子の名前がキー、インデックスが値の辞書
|
|
94
|
+
|
|
95
|
+
y = 0
|
|
96
|
+
for i, wish in enumerate(wishes.values()):
|
|
97
|
+
for snack, w in zip(wish, weights):
|
|
98
|
+
j = snack_to_idx[snack]
|
|
99
|
+
y += X[i][j] * w
|
|
100
|
+
model += y
|
|
101
|
+
|
|
102
|
+
# 制約を設定する。
|
|
103
|
+
|
|
104
|
+
# (1) 一人1つしかお菓子を選べない。
|
|
105
|
+
for i in range(len(wishes)):
|
|
106
|
+
model += lpSum(X[i]) == 1
|
|
107
|
+
|
|
108
|
+
# (2) 二人以上が同じお菓子を選べない。
|
|
109
|
+
for j in range(len(snacks)):
|
|
110
|
+
s = 0
|
|
111
|
+
for i in range(len(wishes)):
|
|
112
|
+
s += X[i][j]
|
|
113
|
+
model += s <= 1
|
|
114
|
+
|
|
115
|
+
# モデルを表示する。
|
|
116
|
+
print(model)
|
|
117
|
+
|
|
118
|
+
# 解く。
|
|
119
|
+
ret = model.solve()
|
|
120
|
+
print("status", LpStatus[ret]) # status Optimal
|
|
121
|
+
|
|
122
|
+
# 解けた場合は結果を表示する。
|
|
123
|
+
if ret == 1:
|
|
124
|
+
print(f"y = {model.objective.value()}")
|
|
125
|
+
for i, person in enumerate(wishes):
|
|
126
|
+
select_idx = np.argmax([x.value() for x in X[i]]) # 選択したお菓子のインデックス
|
|
127
|
+
print(f"{person}: {snacks[select_idx]}")
|
|
128
|
+
```
|
|
129
|
+
|
|
130
|
+
```output
|
|
131
|
+
max weight matching:
|
|
132
|
+
MAXIMIZE
|
|
133
|
+
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
|
|
134
|
+
SUBJECT TO
|
|
135
|
+
_C1: Aさん_いちご + Aさん_キャラメル + Aさん_ケーキ + Aさん_プリン + Aさん_メロン = 1
|
|
136
|
+
|
|
137
|
+
_C2: Bさん_いちご + Bさん_キャラメル + Bさん_ケーキ + Bさん_プリン + Bさん_メロン = 1
|
|
138
|
+
|
|
139
|
+
_C3: Cさん_いちご + Cさん_キャラメル + Cさん_ケーキ + Cさん_プリン + Cさん_メロン = 1
|
|
140
|
+
|
|
141
|
+
_C4: Dさん_いちご + Dさん_キャラメル + Dさん_ケーキ + Dさん_プリン + Dさん_メロン = 1
|
|
142
|
+
|
|
143
|
+
_C5: Aさん_いちご + Bさん_いちご + Cさん_いちご + Dさん_いちご <= 1
|
|
144
|
+
|
|
145
|
+
_C6: Aさん_キャラメル + Bさん_キャラメル + Cさん_キャラメル + Dさん_キャラメル <= 1
|
|
146
|
+
|
|
147
|
+
_C7: Aさん_ケーキ + Bさん_ケーキ + Cさん_ケーキ + Dさん_ケーキ <= 1
|
|
148
|
+
|
|
149
|
+
_C8: Aさん_プリン + Bさん_プリン + Cさん_プリン + Dさん_プリン <= 1
|
|
150
|
+
|
|
151
|
+
_C9: Aさん_メロン + Bさん_メロン + Cさん_メロン + Dさん_メロン <= 1
|
|
152
|
+
|
|
153
|
+
VARIABLES
|
|
154
|
+
0 <= Aさん_いちご <= 1 Integer
|
|
155
|
+
0 <= Aさん_キャラメル <= 1 Integer
|
|
156
|
+
0 <= Aさん_ケーキ <= 1 Integer
|
|
157
|
+
0 <= Aさん_プリン <= 1 Integer
|
|
158
|
+
0 <= Aさん_メロン <= 1 Integer
|
|
159
|
+
0 <= Bさん_いちご <= 1 Integer
|
|
160
|
+
0 <= Bさん_キャラメル <= 1 Integer
|
|
161
|
+
0 <= Bさん_ケーキ <= 1 Integer
|
|
162
|
+
0 <= Bさん_プリン <= 1 Integer
|
|
163
|
+
0 <= Bさん_メロン <= 1 Integer
|
|
164
|
+
0 <= Cさん_いちご <= 1 Integer
|
|
165
|
+
0 <= Cさん_キャラメル <= 1 Integer
|
|
166
|
+
0 <= Cさん_ケーキ <= 1 Integer
|
|
167
|
+
0 <= Cさん_プリン <= 1 Integer
|
|
168
|
+
0 <= Cさん_メロン <= 1 Integer
|
|
169
|
+
0 <= Dさん_いちご <= 1 Integer
|
|
170
|
+
0 <= Dさん_キャラメル <= 1 Integer
|
|
171
|
+
0 <= Dさん_ケーキ <= 1 Integer
|
|
172
|
+
0 <= Dさん_プリン <= 1 Integer
|
|
173
|
+
0 <= Dさん_メロン <= 1 Integer
|
|
174
|
+
|
|
175
|
+
status Optimal
|
|
176
|
+
y = 10.0
|
|
177
|
+
Aさん: メロン
|
|
178
|
+
Bさん: ケーキ
|
|
179
|
+
Cさん: いちご
|
|
180
|
+
Dさん: プリン
|
|
53
181
|
```
|
2
d
answer
CHANGED
|
@@ -18,6 +18,8 @@
|
|
|
18
18
|
|
|
19
19
|
[Maximum Matching in General Graphs](https://www.slideshare.net/akhayyat/maximum-matching-in-general-graphs)
|
|
20
20
|
|
|
21
|
+
できる限り各個人の希望を反映したマッチング ==> 最大重みマッチングです。
|
|
22
|
+
|
|
21
23
|
## Python のサンプルコード
|
|
22
24
|
|
|
23
25
|
Python だと networkx というグラフライブラリの max_weight_matching() という関数で実装されています。
|
1
d
answer
CHANGED
|
@@ -29,6 +29,7 @@
|
|
|
29
29
|
|
|
30
30
|
# 子供の希望
|
|
31
31
|
wishes = {
|
|
32
|
+
# "名前": [第1希望, 第2希望, 第3希望]
|
|
32
33
|
"Aさん": ["プリン", "ケーキ", "メロン"],
|
|
33
34
|
"Bさん": ["ケーキ", "いちご", "メロン"],
|
|
34
35
|
"Cさん": ["いちご", "プリン", "ケーキ"],
|