はじめに
- あるスポーツのトーナメント戦を8カ国で行います。4試合づつ7日間の試合を行うとします。
- 前評判の人気順位がわかっているものとします。
- なるべく、人気の高いペアの試合を後半にするようにして、最後までハラハラするような日程を作成してみましょう。
この問題を組合せ最適化で解いてみます。
定式化
変数を、国1、国2、日ごとに、その組合せを"選ぶ選ばない"を表す0-1変数とします。
また、変数に対応する、"2国(i,j)のある日(k)の試合の重み"を以下のようにします。この重みの和を最大化することにより、"あとの方の順位の小さい国 同士の試合"を優先するようになります。
$$重み = \frac{2^k}{iの順位 \times jの順位}$$
| 最大化 | $\sum_i{重み_i x_i}$ | 重みの総和 |
| 変数 | $x_i \in \{0, 1\} ~ ~ \forall i \in 候補$ | その候補を選択するかどうか |
| 制約条件 | $\sum_{i \in j,kの組~~~~~}{x_i} = 1 ~ ~ \forall j,k \in \mbox{国}$ | 同じ組は1つ |
| $\sum_{i \in 国jを含むk日目~~~~~~~~~~~~~}{x_i} = 1 ~ ~ \forall j \in \mbox{国}, \forall k \in \mbox{日}$ | 同国、同日は1つ |
Pythonでやってみる
まずは、組合せの表を作成します。
python3
import pandas as pd
from itertools import combinations, product
from pulp import *
ss = 'イタリア オランダ 日本 韓国 タイ ドミニカ共和国 ペルー カザフスタン'.split()
rnk = {s:(i+1) for i, s in enumerate(ss)} # 国名→順位
a = pd.DataFrame([(i, j, k, 2**k/rnk[i]/rnk[j]) for i, j in combinations(ss, 2)
for k in range(7)], columns='国1 国2 日 重み'.split())
a[:3]
>>>
国1 国2 日 重み
0 イタリア オランダ 0 0.5
1 イタリア オランダ 1 1.0
2 イタリア オランダ 2 2.0
定式化して解いてみましょう。
python3
m = LpProblem(sense=LpMaximize) # 数理モデル
a['Var'] = [LpVariable('v%d'%i, cat=LpBinary) for i in a.index] # 変数
m += lpDot(a.重み, a.Var) # 目的関数
for _, b in a.groupby(['国1', '国2']):
m += lpSum(b.Var) == 1 # 同じ組は1つ
for s, i in product(ss, range(7)):
# 同国、同日は1つ
m += lpSum(a.query('(国1=="{0}" | 国2=="{0}") & 日=={1}'.format(s, i)).Var) == 1
m.solve() # 求解
a['Val'] = a.Var.apply(value) # 結果
# 表示
for i, b in a.groupby('日'):
print(i+1, '日目 ')
for _, r in b[b.Val > 0].iterrows():
print(' %*s - %s'%(8-len(r.国1), r.国1, r.国2))
>>>
1 日目
イタリア - カザフスタン
オランダ - ペルー
日本 - ドミニカ共和国
韓国 - タイ
2 日目
イタリア - ペルー
オランダ - カザフスタン
日本 - タイ
韓国 - ドミニカ共和国
3 日目
イタリア - ドミニカ共和国
オランダ - タイ
日本 - カザフスタン
韓国 - ペルー
4 日目
イタリア - タイ
オランダ - ドミニカ共和国
日本 - ペルー
韓国 - カザフスタン
5 日目
イタリア - 韓国
オランダ - 日本
タイ - カザフスタン
ドミニカ共和国 - ペルー
6 日目
イタリア - 日本
オランダ - 韓国
タイ - ペルー
ドミニカ共和国 - カザフスタン
7 日目
イタリア - オランダ
日本 - 韓国
タイ - ドミニカ共和国
ペルー - カザフスタン
各日の日程が出力されました。
他の方法としては、前半に戦力差のある組合せ、後半に拮抗した戦力差の組合せというのもあるかもしれません。
おまけ
一時的に、私の直近のPython関連の投稿を、Arukasで実行できるようにしています。
-
https://qiita-jupyter.arukascloud.io/
- 各記事を開いた後で、セルを選択後、Shiftキーを押しながらEnterキーを押すと、実行できます。
- 上記の元イメージです。
以上