About

このアプリケーションの目的は、良いチーム分けをする、つまり良い割当を考えることです。

チーム分けの対象となる人が $K$ 人おり、それぞれ $1, 2, 3, \ldots, K$ と番号付けられているとします。全員についてレートがついているものとし、$i$ $(1 \leq i \leq K)$ 番目の人のレーティング値が $x_i$ であるとします。

この $K$ 人を $N$ グループに分けることを考えます。$i$ $(1 \leq i \leq N)$ 番目のグループは $M_i$ 人で構成されるものとし、$i$ 番目のグループの $j$ $(1 \leq j \leq M_i)$ 番目のメンバーの番号が $a_{i, j}$ であるとします。以下、$\left\{ a \right\}$ を「割当」と呼ぶことにします。

冒頭で述べた「良い割当」とは、次の条件を満たすような割当を指しています。

• チーム間の実力差が小さい
• 所属の重複が少ない (できるだけ所属が異なる参加者同士でチームを組む)

ある割当 $\left\{ a \right\}$ に対し、それがどれくらい良いものであるか評価する方法について述べます。

チームに対する評価指標

$i$ 番目のチームに対する評価指標 $s_i$ は、そのチームに属するメンバーのレーティング値の二乗和平均です。より詳細には、以下の式で表されます。

$s_i = \frac{\sum_{j=1}^{M_i} \left( x_{a_{i, j}} \right)^2}{M_i}$

単純な和ではなく二乗和を採用しているのは、レートが高いメンバーの影響をより大きくするためです。例えば水色コーダーが 3 人いるチームと、赤コーダーが 1 人と緑コーダーが 2 人いるチームはレートの和の意味では似通っていますが、実際の実力差は大きいでしょう。このような事情を解消することを目的として二乗和にしています。

割当全体に対する評価指標

評価指標は、チームに対する評価指標の分散 $V$ をベースにしています。分散は以下の式で表されます。

$V = \frac{1}{N} \sum_{i=1}^{N} s_i^2 - \left( \frac{1}{N} \sum_{i=1}^{N} s_i \right)^2$

また、$i$ 番目のチームにおける所属の重複数 $d_i$ を以下のように定義します。さらに、$D = \sum_{i=1}^{N} d_i$ とします。

$d_i = \left| \left\{ (x, y) \mid 1 \leq x \lt y \leq M_i, a_{i, x} \text{の所属} = a_{i, y} \text{の所属} \right\} \right|$

これらを用いて、割当全体に対する評価指標 $P$ を以下のように定義します。

$P = V (D + 1)$

良いチーム分けにおいて、分散は小さいほうが良いうえ重複数も小さいほうが良いため、$P$ をできるだけ小さくすることが求められます。

割当全体に対する評価指標 $P$ を最適化する、すなわち $P$ を最小化するために、焼きなまし法 (Simulated Annealing) を使用しています。はじめに適当な割当を考え、ある 2 人をランダムに選び swap することで近傍を得て探索しています。