JavaScriptで条件付きの総当たり対戦順を求める

旅行プラットフォーム部エンジニアの谷井です。
普段の業務では主にTypeScript + PostgreSQLで開発を行っています。今回は「個人的な課題をJavaScriptで解決してみたら、競プロの世界に足を踏み入れていた」話を書きます。
日常生活のちょっとした困りごとを自分のコードで解決できるのはエンジニアの役得ですね！

今回はアプリの構成やUIはスコープ外とし、ロジックの部分だけを取り出して扱うので、「JavaScriptの書き方は一通り学んだが、複雑なアプリは作ったことがない」という方も、ぜひパズルのつもりで考えながら読んでみてください！

解決したい課題

「連戦の少ない総当たりの対戦順を決めたい」

この記事を読んでいるみなさんも、「連戦の少ない総当たりの対戦順を楽に求めたい！」と思ったことはきっと一度や二度ではないですよね。

私は大学から躰道という武道をやっており、地区の選考会運営などで対戦順を決める機会がありました（躰道についてはこの記事では到底語り尽くせないのでぜひ動画を検索してみてください）。
選考会では対象選手の総当たり戦を順番に行うのですが、連続して試合に出ることは選手にとっても負荷が大きく、連戦を極力減らした組み合わせが求められます。
また、事前の大会で実施した対戦カードはその結果を流用するため、一部の組み合わせを対戦順から除外する必要がありました。

当然、試合順を事前に考えておければ楽なのですが、対象選手や人数が当日確定することもあり、その場で急いで対戦順を考えなければいけません。
今回はこれまでは紙とペンでやっていた地味に大変なこの作業を、自動化していきたいと思います。

実現したい内容は下記の図のようなイメージです。

「選手を登録し、すでに実施済みの試合を選択すると、総当たりに必要な残りの試合を（連戦の少ない形で）自動で提示してくれる」という流れです。

この記事では、(ii)→(iii)の組み合わせ最適化について考えます。

• n人(~10程度)の総当たり戦の対戦順を決める
• 同時に行う試合の数は1試合とする
• 一部の組み合わせを除外した上で、連戦数を最小にする
  • ここでの「連戦数」とは「前の試合に出た選手と同じ選手が出る試合の数」のこと
  • たとえば"A-B", "B-C", "A-C", "D-E"の順で実施した場合、1,2試合目のBと2,3試合目のCが連戦となるため、連戦数は2

方針

• 選手のリストを作る
• リストから組み合わせを列挙する
• 列挙した組み合わせを並べ替え、評価関数を通してコスト（連戦数）が最小のものを取り出す

パフォーマンスや実装の手軽さを考慮すると他の言語に軍配が上がりそうですが、今回はTypeScriptで作っているWebアプリに乗せることを想定しているため、一旦JSで実装してみたいと思います。
本文中のサンプルコードはNode.js 12.19.0で動作確認しています。

実装

はじめに、選手の組み合わせの表現方法を考えます。

A, B, C...と選手が与えられたとき、A対Bの試合を "AB" のように文字列で与えても良いのですが、連戦判定をよりシンプルに行うために、各選手にビットを割り当てて表現してみたいと思います。
すなわち、選手A, B, C, D...に対して 1, 2, 4, 8... と数値を割り当てていき、選手同士の対戦組み合わせはその和によって表現することにします。

たとえば"A-D"の試合は 9 として一意に表現できますね。

表1: n=5の場合の各試合の表現

続けて、実際にコードを書いていきましょう。

1. 選手を表すリストを作る

参加人数nが与えられたとき、各選手に割り当てられたビットに1を立てた数値の配列を作っていきます。

n個の要素の配列を作り、map関数で各要素をindex分だけシフトさせた数値に変換します。
なお、Array(n) では空配列が生成されるので、一度スプレッド演算子で展開しています。

const createList = n => [...Array(n)].map((_, i) => 1 << i);

// example
createList(5);
// [1, 2, 4, 8, 16]

2. 組み合わせを全て列挙する

二重のループを通して二選手の数値の和を配列に加えていきます。
"A-B"と"B-A"は区別する必要がないため、内側のループのカウンタが外側のそれを超えない範囲であることに注意します。

引数には先ほどのcreateListで作った選手を表す配列を渡します。

const combination = list => {
    let combinationList = [];
    for (let i = 0; i < list.length; i++) {
        for (let j = 0; j < i; j++) {
            combinationList.push(list[i] + list[j]);
        }
    }
    return combinationList;
}

// example
combination([1, 2, 4]);
// [3, 5, 6]
combination([1, 2, 4, 8]);
// [3, 5, 6, 9, 10, 12]

一つ目の例は ["A-B", "A-C", "B-C"] を表す配列が得られたことになります。

3. すでに結果がある試合を除外する

今回は、実施済みの試合を表す数値の配列 excludeList が与えられているものとします。
たとえば、"A-C", "C-D"の試合が実施済みの場合は excludeList は [5, 12] となります。

Array.filter() を使って、これらを除外した「これから行う試合のリスト」を作成します。

const combinationList = combination(createList(5));
const excludeList = [5, 12];
const filteredList = combinationList.filter(elm => !excludeList.includes(elm));

4. 連戦数を計算する関数（評価関数）を作る

さて、並べ替えて対戦順の探索をする前に、連戦数を求める関数を作っておきます。

各要素から順に、「1つ前の要素と比較して同じ選手が含まれる場合はコストに1加算する」操作を行います。
「同じ選手が含まれるかどうか」の判定は、ビット論理積によって判定することができます。
同じ選手が含まれている場合は同じ位置に1が立っているため、論理積を取ると0になりません。

表2: 連戦となる場合、ならない場合の2試合の論理積の結果

これを順繰りに判定し、連戦の場合はコストを加算していきます。

for文で書いても良いのですが、配列を畳み込んでいってある値を得たいときは、その意図を明示するためにも Array.reduce() 関数をよく使います。

const evaluationFunc = list => list.reduce((cost, _, idx, src) => src[idx] & src[idx - 1] ? ++cost : cost, 0);

// example
const listA = [3, 5, 6, 9, 10, 12];
const listB = [3, 12, 5, 10, 6, 9];
evaluationFunc(listA);
// 4
evaluationFunc(listB);
// 2

• idxが0のとき、src[idx - 1] = undefinedとなりますが、論理積を取ると0になるので分岐は省略します。
• src[idx]は第二引数で表せますが、こちらの方が操作を直感的に理解しやすそうなためこのように書いています。

5. 並べ替えて評価する

順番を入れ替えるため、順列を求める関数を実装します。

const permutation = (list, k) => {
    let ans = [];
    if (list.length < k) {
        return [];
    }
    if (k === 1) {
        return list.map(i => [i]);
    } else {
        for (let i = 0; i < list.length; i++) {
            let parts = [...list];
            parts.splice(i, 1);
            let row = permutation(parts, k - 1);
            for (let j = 0; j < row.length; j++) {
                ans.push([list[i], ...row[j]]);
            }
        }
    }
    return ans;
}

全部並べ替えてから評価しても良いのですが、連戦なしの解が見つかった時点で打ち切りたいため、再帰の一番浅い階層で評価しながらfor文を回します。

const search = (filteredList) => {
    let ans = [];
    let cost = undefined;
    for (let i = 0; i < filteredList.length; i++) {
        let parts = [...filteredList];
        parts.splice(i, 1)
        let row = permutation(parts, filteredList.length - 1);
        for (let j = 0; j < row.length; j++) {
            let v = [filteredList[i], ...row[j]];
            if (!cost || evaluationFunc(v) < cost) {
                cost = evaluationFunc(v);
                ans = v;
                if (cost === 0) break;
            }
        }
        if (cost === 0) break;
    };
    return {ans, cost}
}

これで、連戦数 cost の対戦順 ans を得ることができます。

試しに参加人数を6名、実施済みの試合を"A-C", "C-D", "B-E", "B-F"として対戦順を求めてみます。

const list = createList(6);
const excludeList = [5, 12, 18, 34];
const filteredList = combination(list).filter(elm => !excludeList.includes(elm));
search(filteredList);

// {
//     ans: [ 3, 20, 9, 6, 40, 17, 36, 24, 33, 10, 48 ],
//     cost: 0
// }

これを復元すると、

となり、確かに指定した試合を除いた、連戦のない対戦順を求めることができました。

上記の例では試しに手元で10回計測したところ、実行時間は平均10.8秒でした。

改善

さて、一応答えを求めることはできましたが、どうにも愚直にやりすぎている気がしてなりません。
かの老子も「千里の道も全探索から」とは言いましたが、もう少し効率よく探すことはできないでしょうか。

うすうす勘付いていましたが、いかにも競プロチックな問題ですね。
競プロど素人の私では調べようにも効率が悪いと思い、社内の競プロ歴戦の猛者達にレビューをお願いしたところ、以下のような啓示を賜ることができました。

• 連戦にならない試合同士をコスト0の辺、連戦になる試合同士をコスト1の辺でつないだ無向グラフを考えると、連戦数を最小化する問題は、「このグラフのすべての頂点を1度ずつ通るもっとも合計コストの小さい経路はどれか？」という問題に帰着し、これは 巡回セールスマン問題 と呼ばれる
• これは計算量 O(2^n n^2) (n: 頂点数=試合数)で決定的に求めるアルゴリズムが知られている
• ただ、巡回セールスマン問題については近似的によい解を求める方法も考案されており(2-optなど)、今回のケースでは十分な解が得られる可能性が高い

アルゴリズムや問題の名称を知ることで「検索する」という手段を手に入れたので、調べながら改良してみたいと思います。

2-opt法

次のゴールである「効率よく探す」方法のひとつとして、局所探索法があります。
これは「現在の組み合わせに少しだけ変化を加え、コストが下がれば採用する」という操作を、コストが下がらなくなるまで繰り返すものです。

その中でも巡回セールスマン問題によく使われる2-opt法は、グラフ任意の2つの辺を選びそれらをつなぎ変えることで、組み合わせを変化させていきます。
つまり、...-a-b-...-c-d-...のようなグラフに対して、...-a-c-...-b-d-...のようにb-...-cのブロックを反転させてつなぎ替えるような操作を試していくことになります。

再実装

1から3までの手順については既に作成した関数を流用し、近傍探索部分を追加で実装していきます。

まず辺を入れ替えた際の連戦数の変化について考えます。
最初の実装同様に全体の連戦数を数える評価関数を通すこともできますが、入れ替え前後でコストが変わり得るのは交換した辺の部分のみのため、差分だけを計算することで計算量を減らします。

const getSwapCost = (list, i, j) => {
    const getLocalCost = (x, y) => list[x] & list[y] ? 1 : 0;
    const costBefore = getLocalCost(i, i + 1) + getLocalCost(j, j + 1);    
    const costAfter = getLocalCost(i, j) + getLocalCost(i + 1, j + 1);
    return costAfter - costBefore;
}

（今回も、配列長を超えて参照した場合コストは0と計算されるので、i, j が配列末尾だった場合も例外処理は不要です。）

続いて、コストが下がることがわかった場合に、2つの辺をつなぎ替える関数を作成します。

const swapEdges = (list, i, j) => {
    const head = list.slice(0, i + 1);
    const reverseTarget = list.slice(i + 1, j + 1);
    const tail = list.slice(j + 1);
    return [...head, ...reverseTarget.reverse(), ...tail];
}

// example
const list = [0, 1, 2, 3, 4, 5, 6];
swapEdges(list, 2, 5);
// [0, 1, 2, 5, 4, 3, 6]

さらに、入れ替えた際にコストが最も下がる辺の組み合わせを探し、新しい対戦順を返す関数を作ります。
任意の2辺について試しますが、i と j が連続していると入れ替え操作をしても配列が変わらない（2つの辺が同じ1つの頂点につながっていてつなぎ替えようがない）ため、内側のカウンタ j は i+2 から始まるようにします。
また返り値は、コストが下がった場合には採用された新しい並び順を、コストが変わらなかった場合は null を返すようにしておきます。

const improve = list => {
    let iBest, jBest;
    let diffBest = 0;
    for (let i = 0; i < list.length; i++) {
    for (let j = i + 2; j < list.length; j++) {
            const swapCost = getSwapCost(list, i, j);
            if (swapCost =< diffBest) {
                diffBest = swapCost;
                [iBest, jBest] = [i, j];
            }
    }
    }
    return diffBest < 0 ? swapEdges(list, iBest, jBest) : null;
}

最後に、improve の結果が null になるまで繰り返し探索するメインの関数を実装します。

const localSearch = list => {
    const totalCost = evaluationFunc(list);
    if (totalCost !== 0) {
        while (true) {
            let improvedList = improve(list);
            if (!improvedList) break;
            list = improvedList;
        }
    }
    return {
        ans: list,
        cost: evaluationFunc(list)
    }
};

実行する際は、同様の手順で filter した配列を渡します。

localSearch(filteredList);

// {
//     ans: [ 3, 36, 9, 6, 24, 33, 20, 40, 17, 10, 48 ],
//     cost: 0
// }

最初の実装と同様の配列を渡すと、別の解ですが連戦0の並び順を得ることができました。

しかし、実行時間は全探索の平均10.8sに比べて平均1.2msと、大幅に短縮することができました！

初期解について

2-opt法の探索では、与えられた解から変化させて探索するため、初期解の良さが最終的な解の良さに影響を与えます。
特に、今回は組み合わせを作成するロジック上、連戦が相当数続く並びが初期解となるため、 filteredList をランダムに並べ替えてから実行する方が良いかもしれません。
さらにいえば、複数のランダム初期解からそれぞれ2-optで探索すると、最適解が得られる確度が上がりそうですね。

ランダムに並べ替える関数も実装して試したところ、100セットの探索中、9回は連戦数1の解、それ以外の91回は連戦0の解が導出されていました。

const shuffle = list => {
    for (let i = list.length - 1; i >= 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [list[i], list[j]] = [list[j], list[i]];
    }
    return list;
}

おわりに

最後まで読んでいただき、ありがとうございました！

今回は身近な（とても個人的な）課題をJavaScriptを使って解決しました。
また、2-opt法を用いることで、実行時間を劇的に短縮することができました。

さらなる拡張も現実的になったので、今後の展望としては

• 同一選手が3連戦する場合を評価に組み込む
• 選考試合を2コート同時並行で行う
• 選手数がより増えるケース

なども対応・実証していきたいと思います。

これまで競プロをやってみたいとは思いながらも手を出せていませんでしたが、期せずしてその奥深さの一端に触れることができました。
与えられた問題ありきでなく現実で必要な問題設定を自ら考えることで、より興味と実感を持って学ぶことができたように感じます。

現実的な課題をいかに既知の問題に落とし込むか、また落とし込んだ問題に対して効率よく解ける引き出しをどれだけ持っているか、という部分はセンスや経験が問われることを痛感したので、これからも普段の業務で使う技術領域にとらわれず、幅広く学んで技術を磨いていきたいと改めて感じました。