「いい感じに分けてくれない？」
そう頼まれたことはないでしょうか。
困るのは、その「いい感じ」を誰も定義していないことです。
聞いてみると、だいたいこういう感じの回答が返ってきます。
- シフトを、なるべく公平に
- 当番を、なるべく連続させずに
- レビュアーを、なるべく同じ人に偏らせずに
- 研修グループは、なるべく初対面同士で
全部に「なるべく」が入っています。
残念ながら「なるべく」のままでは、コードに落とせません。
if にも for にも翻訳できない。だから実装する側が困ってしまう。
この記事では、その「いい感じ」を定義して解いた話を書きます。
題材は社内のシャッフルランチ（普段いっしょに仕事をしない人同士でランチに行く制度）で、80人を3〜4人のグループに分けるというものです。
ただ、やっていることはシフト表でも当番表でも同じです。今回はソルバーもライブラリも使わず、Google Apps Script だけで書きました。
まず、結果から
80人を毎月3〜4人ずつのグループに分けます。
ランダムに割り振ると、先月と同じペアが毎月およそ5ペアできてしまいます。
「シャッフルランチなのに、先月とまた同じですね」が、毎月5ペアです。
この5ペアはどう出したか（飛ばしてもOK）
80人は4人×20グループなので、同席するペアは C(4,2)×20 = 120ペア。
80人でつくれるペアの総数は C(80,2) = 3160ペア。
特定の2人が同じグループに入る確率は 120/3160 = 約3.8%。
先月の120ペアが今月もう一度同席する期待値は 120 × 3.8% = 約4.6ペア。
そこで「いい感じ」をちゃんと定義して解いてみたところ、こうなりました。
| 前月ペアの再会 | 0ペア（12ヶ月連続） |
| 6ヶ月以内に会った人との再会 | 0ペア（12ヶ月連続） |
| 計算時間 | 約2秒 |
| 小規模での厳密最適解との一致 | 140/140 ケース |
| 使ったソルバー・ライブラリ | なし |
ランダムなら毎月だいたい5ペアが被るはずでしたが、ちゃんとアルゴを組んだら0ペアにできました。
ここから先は、この「いい感じ」を何に翻訳したのかという話を書いていきます。
ちなみに、ランダムでも偏ってしまう現象は、当番表でもシフト表でも同じで、「たまたま」で想像する範囲を超えて偏ることが多いです。
「なるべく」を2種類に分ける
運用側から出てきた要望を並べると、こうなりました。
- 不参加申請した人は絶対に入れない
- どのグループも3人か4人
- 4人グループをなるべく多く
- 最近いっしょだった人を避ける
- 同じ事業部で固めない
最初に、この一覧を2つに分けることをしました。
(A)破ったら運用が壊れるもの。
(B)破っても運用は回るが、価値が下がるもの。
たとえば、不参加申請した人が入っていたらそれはバグなので、「不参加申請した人は絶対に入れない」という要望はAになります。
一方、先月と同じ人が1組いても、ランチは開催できるので、「最近いっしょだった人を避ける」という要望はBになります。
ちなみに、(A)をハード制約、(B)をソフト制約と呼びます。
そして重要なのは、
ソフト制約どうしは、衝突する可能性がある
という点です。
先月一緒だった2人を引き離す。すると玉突きで、同じ事業部の2人が同席する。
あちらを立てればこちらが立たない。
だから「全部満たす」という設計は、最初から捨てました。この種の問題だと良くあることです。(余談: 運用側も完璧に解けないことが直感的に分かってたから、「いい感じに」と言ったのかもしれませんね。)
「なるべく多く」が、実はハード制約だった
仕分けの途中で、判断に困る項目がひとつありました。
「4人グループをなるべく多く」です。
なるべく。どう見てもソフト制約です。
これをペナルティ項にすると、3人グループが1つ増えるごとに何点、みたいな話になってきます。
でも、その必要はありませんでした。
「4人グループを最大化する」は、言い換えると「グループ数を最小にする」になります。
ここで問題です。
78人を3〜4人ずつに分けて、「4人グループをなるべく多く」したい。
この条件、最適化する必要があるでしょうか？
実はありません。
78人なら「4人×18 + 3人×2」しかありません。
これを式で表現するとこんな感じです。
G = \left\lceil \frac{N}{4} \right\rceil, \qquad n_4 = N - 3G, \qquad n_3 = 4G - N
$n_4$ が4人グループの数、$n_3$ が3人グループの数です。
N=80 なら G=20。ちょうど割り切れるので、4人×20 で3人グループはゼロ。
不参加申請が2人出て N=78 になると、G は20のまま、内訳が 4人×18 + 3人×2 に変わります。
どちらも、これ以外の構成はありえません。選択の余地がないですよね。
「なるべく」に見えて実は一意に決まる要望は、意外とあります。
見つけたら儲けもので、探索の対象がまるごと1つ消えます！
制約は「避ける」のではなく「作れなくする」
さらに踏み込んで、もう一つ工夫ポイントを紹介します。
ハード制約だと分かったので、巨大なペナルティを置いて事実上避けさせる ——-
とは、しませんでした。
そもそも違反した分け方を生成しないようにしました。
const G = Math.ceil(N / 4);
const numFour = N - 3 * G;
const numThree = 4 * G - N;
const sizes = [];
for (let i = 0; i < numFour; i++) sizes.push(4);
for (let i = 0; i < numThree; i++) sizes.push(3);
// 以降、この sizes どおりにしか分割しない
探索アルゴリズムは、このサイズ構成しか作らないようにしました。
後で出てくる「1手」も、サイズを変えない操作だけに限定します。
こうすると、ハード制約違反は原理的に起こりません。
チェック処理も、リトライも、不要になります。
制約は、罰するより、作れなくするほうが良い👌
残った「なるべく」に、嫌さの点数をつける
ここまででハード制約は構造で片付きました。残ったソフト制約をどうするか。
やることは単純です。望ましくないことが1件起きるたびに、点数を足す。
そして点数の合計がいちばん小さい分け方を選ぶ。それだけです。
この点数を、ふつうは「ペナルティ」と呼びます。要は 嫌さの点数 です。
ペナルティを下記のように定義しました。
| 事象 | ペナルティ |
|---|---|
| 先月同席したペアが再会 | 3 × 6 = 18 |
| 同一事業部のペアが1組発生ごとに | 8 |
ペナルティの値自体には意味はありません。他の項目と比較したときの比率が重要です。
「先月のペア(18) > 事業部被り(8)」。
この不等号が、そのまま優先順位です。要望ヒアリングで出た「これが最優先」「次にこれ」というリクエストが、ここで数になっています。
運用しながら「今月は事業部混ぜるのをもっと強く」と言われたら、8 を上げるだけで済みます。
ちなみに 18 と 8 は約分できます。9 と 4 にしても、選ばれる分け方は変わりません。効いているのは比だけです。
ここまでを1本の式にするとこうなる
グループ $g$ ごとに点数を出して、全グループ分を足すだけです。
\begin{aligned}
P = \sum_{g} \Bigl[\;
& 3 \sum_{\{a,b\} \subset g} \mathrm{PairScore}(a,b) && \text{直近同席度} \\
+\; & 8 \sum_{d} \binom{k_d}{2} \;\Bigr] && \text{同一事業部のペア数}
\end{aligned}
新しいことは何もしていません。さっきの表を、そのまま式にしただけです。
式の 3 は倍率です。先月の同席は6ポイントなので、3倍して18になります（6の理由は後ほど説明します）。
ここで「重みは学習させればいいのでは」と思うかもしれません
思いました。
でも、やめました。
月1回では、学習に使えるデータが年に12件しか増えません。
それに、重みを人が決められることには運用上の価値があります。
「なぜこの2人が同じグループなのか」と聞かれたとき、説明できるからです。
社内向けの仕組みでは、精度より説明可能性のほうが効くことがあります。
同じ事業部を「人数」ではなく「ペア数」で数える
数え方の工夫を、もうひとつ紹介します。
「同じ事業部が2人いたら8点」ではなく、「同じ事業部のペア1組につき8点」にしました。
すると、
- 2人 → 1組 → 8点
- 3人 → 3組 → 24点
- 4人 → 6組 → 48点
固まるほど、1人増やす代償が大きくなります。「2人までなら許容、3人以上は本気で避ける」という運用感覚が、数え方を変えるだけで出せます。
「最近いっしょだった」を0/1で持つと、情報が落ちる
「なるべく最近の人を避ける」の 最近 も翻訳が要ります。
素朴に実装するなら、こんな感じになると思います。
if (先月同じグループだった) penalty += 18;
これでも動きますが、2ヶ月以上前の情報が完全に消えてしまいます。
そこで、過去の各回に減衰係数を与えて足します。
// decay(m) = max(0, 7 − m) m は何ヶ月前か（先月=1）
function decay_(monthsAgo) {
return Math.max(0, 7 - monthsAgo);
}
先月は6点。半年前は1点。7ヶ月以上前は0点。
これを合算したものが PairScore(a, b) です。
「3ヶ月前に1回だけ同席（4点）」より「先月同席（6点）」のほうが痛い。
近い過去ほど重く減点し、遠い過去は減点しない。
しきい値でバッサリ切らず、連続的に効かせるのがポイントです。当番表の「同じ人が続かないように」も、この形がそのまま使えます。
一手ずつ交換して、点数を下げていく
構造で決まる部分はここまでです。残りは「探索」で決めます。
80人を4人×20グループに分ける方法は、7.3×10⁷² 通りあります。総当たりは無理です。
そこでやることは、これだけです。
いまの分け方から2人を入れ替えてみる。点数が下がるなら、採用する。
下がる入れ替えがなくなるまで繰り返す。以上です。
実際に動かすとこうなります↓
初期状態は「先月とまったく同じグループ分け」。全ペアが再会ペナルティを抱えているので、428点から始まります。
そこから1手ずつ、いちばん効く入れ替えを踏んでいく。
428 → 288 → 184 → 107 → 55 → 37 → 19 → 16。7手で下がりきります。
効く手から順に選ばれているのが見えます（−140、−104、−77、−52、…、最後は−3）。
これに「山登り法」という名前がついている
やっているのは「今より良くなる方向へ1歩ずつ進む」だけです。これを局所探索、あるいは山登り法（hill climbing）と呼びます。
1手として用意したのは2種類だけです。
- グループをまたぐ1対1スワップ
- 4人グループから3人グループへの1人移動
どちらもサイズ構成を壊しません。だからハード制約は最後まで自動的に保たれます。
// 1対1スワップ: ga[i] ⇔ gb[j]
const delta = groupPenalty_(newA, ...) + groupPenalty_(newB, ...)
- pen[a] - pen[b]; // ← 影響を受ける2グループだけ再計算
if (delta < bestDelta) { bestDelta = delta; bestOp = {type:'swap', a, b, i, j}; }
ちなみに80人ちょうどだと全グループが4人なので、移動のほうは出番がありません。
不参加が2人出て78人になると3人グループが2つできて、そこで初めて効きます。GIFで2回出てくる「移動」がそれです。
「それ、大域最適じゃないですよね」
そのとおりです。
山登り法は局所最適で止まります。谷を1つ下り切ったら、隣にもっと深い谷があっても気づきません。
そこで、出発点を変えて30回登ります（マルチスタート）。
ランダムな初期配置から山を下り、30本のうちいちばん低い谷を採用する。
正直な話、これでも大域最適は保証されません。
なので、実際どれくらいズレるのかを測りました。
厳密解と突き合わせて、どれだけズレるか測った
冒頭に出した結果は、このようにして測ったものです。
① 小規模で総当たりと突き合わせる（N=6〜12）
人数が少なければ全分割を列挙できます。N=6〜12 について、それぞれ20ケースずつ厳密最適解と比べたところ、140ケースすべて一致。
山登り法でも、少なくとも小規模では取りこぼしゼロでした（N=12 なら全分割は5,775通りあります）。
② 12ヶ月連続でシミュレーションする
80人の名簿で12ヶ月分を回し、毎月「先月と同席したペアが何ペア再会したか」を数えました。
結果は12ヶ月すべて 0ペア。「6ヶ月以内に同席したペア」まで広げても 0ペアでした。
ランダムなら毎月5ペア。そこがゼロになったので、PairScore は狙いどおり効いています。
まとめ
「いい感じにやっといて」と頼まれたとき、やったことは5つでした。
- 要望をハード制約とソフト制約に仕分ける
- 「なるべく」に見えて実は一意に決まるものを探す
- ハード制約は罰するのではなく、そもそも作れなくする
- 残ったソフト制約に嫌さの点数をつけて、比で優先順位を表す
- 一手ずつ交換して点数を下げ、保証できない分は測る
特に面白かったのは、2です。
「なるべく」に見えたものが、実は選択の余地のない制約だった。つまり探索しなくていいものを、探索から追い出せたわけです。
最適化というと、賢い探索アルゴリズムやソルバーを持ってくる話に見えます。
でも実際に効いたのは、探索する前に問題を削るほうでした。
「いい感じ」は、そのままではコードになりません。
でも、制約と、重みの比と、数え方に翻訳はできます。
最後に：この記事を面白いと思ってくださった方へ
今回の記事では、「いい感じに分けて」という曖昧な依頼を、制約と重みと数え方に翻訳していきました。
Sapeetでは、このようにAIやアルゴリズムの仕組みを掘り下げ、実際に手を動かしながらプロダクトや業務へつなげていくことを大切にしています。
そんなSapeetの技術や開発の雰囲気を、もう少し知っていただける機会として、交流イベント「Open Sapeet！」を開催します。
2026年9月11日（金）19:30より、Sapeetのエンジニアをはじめとする社員が登壇し、AIやプロダクト開発、これからの働き方についてお話しします。この記事で扱ったような「『いい感じ』をどうコードに翻訳するか」に近い話も出てくるかもしれません。
トークのあとは、軽食とドリンクを片手にゆるりと交流できる時間もご用意しています。
スタートアップの開発現場を覗いてみたい方、Sapeetの雰囲気を知ってみたい方、気軽に遊びに来てください。
イベント詳細・お申し込みはこちら👇️
https://connpass.com/event/398374/