はじめに

組み合わせ最適化問題において、最適な組み合わせを求める基本的なアプローチは、考えうる全てのパターンを生成し、目的関数が最小（または最大）となるパターンを探索することだ。しかし、パターンの総数は要素数が増加するにつれて爆発的に増加するため、一般的なPCでは（場合によってはスーパーコンピュータでも）、全パターンの評価を現実的な計算時間内に完了させることが困難となる場合が多い。

もし、生成する順列パターンに何らかの制約を設け、評価対象となるパターン数を大幅に削減できれば、一般的なPCでも許容可能な計算時間で最適な組み合わせ、あるいはそれに近い解を求めることが可能になる。

この方法では２コートまでの組み合わせしか許容される処理時間内で計算できなかった。そこで筆者は、順列生成と制約チェック処理を統合して評価パターン数を大幅に削減する手法を考案した。その結果、本稿で提案する手法によって３コートまでの計算が可能となった。本稿では、その詳細について述べる。

制約付き高速順列生成

サークルテニスダブルス組み合わせ最適化では、next_permutation() により、すべての順列を生成し、その中で正規化された順列のみを目的関数で評価することで、コート数が２面までであれば現実的な処理時間で最適解を得ることに成功した。

  vector<int> ar = {1, 2, ...};
  do {
    if( is_normalized(ar) ) {  // 制約を満たしているか？
      auto ev = eval(ar);  // 目的関数により、パターンを評価
      ev が保存している評価値より優れていれば、ar を保存
    }
  } while( std::next_permutation(ar.begin(), ar.end()) );  // 次の順列を生成

しかし、順列の要素数がある程度大きくなると、制約による評価を行う以前に、順列を網羅的に生成する処理そのものが計算量のボトルネックとなる。例えば、12個の要素からなる順列の総数は 12!（約4億7900万通り）にも上り、この規模の全探索は現実的な時間内での完了が困難である。

そこで本稿では、全ての順列を生成した後に制約をチェックするのではなく、制約を満たす順列のみを効率的に生成する枝刈り探索の手法を提案する。

具体的には、再帰関数を用いて順列の要素を1つずつ決定していく過程で、各ステップごとに制約を満たしているかを判定する。もし制約に違反した場合は、その先の分岐を全て破棄（枝刈り）する。これにより、無駄な順列生成を根本から省略し、計算量を大幅に削減することが可能となる。以下にその実装を示す。

void gen_permutation(vector<int> &ar, int ix) {
    if( ix == ar.size() ) {
      auto ev = eval(ar);  // 目的関数により、パターンを評価
      ev が保存している評価値より優れていれば、ar を保存
      return;
    }
    for(int dst = ix; dst < ar.size(); ++dst) {
        swap(ar[ix], ar[dst]);  // 要素交換
        if( ar[ix] が制約を満たしているか？ )
            gen_permutation(ar, ix+1);
        swap(ar[ix], ar[dst]);
    }
}

  vector<int> ar = {1, 2, ...};
  gen_permutation(ar, 0);

3面12人の組み合わせ問題について、1ラウンドあたりの最適な組み合わせを求める処理時間を計測し、提案手法の有効性を評価した。比較対象として、単純な全探索（next_permutationを使用）と、本稿で提案する枝刈り探索（gen_permutationを使用）の2つの実装を用いた。

計測環境


OS	Windows 10
CPU	Intel Core i7-9700 (3.00GHz)
メモリ	32GB
言語	C++

計測結果

計測の結果、1ラウンドあたりの処理時間は以下の通りとなった。

手法	処理時間
全順列生成 (next_permutation)	16.861秒
本稿の手法：枝刈り探索 (gen_permutation)	0.312秒

この結果から、提案手法である枝刈り探索を用いることで、処理時間を約54倍高速化できることが確認できた。これにより、従来手法では実用的でなかった規模の問題に対しても、許容時間内での計算が可能となる。

おわりに