綱引きアルゴリズムとは？整数集合を2つのグループに最適分割する手法を解説

綱引きアルゴリズムとは

綱引きアルゴリズム（Tug of War）は、与えられた整数の集合を2つの部分集合に分割し、それぞれの合計値の差をできるだけ小さくするという問題を解くための手法です。イメージとしては、綱引きゲームに参加する2チームを、力がほぼ同等になるように振り分けることに相当します。

部分集合のサイズに関するルールは以下の通りです。

• 要素数 n が偶数の場合：各グループのサイズは n/2 ずつに分割します。
• 要素数 n が奇数の場合：一方のグループは (n−1)/2 個、もう一方は (n+1)/2 個に分割します。

入力と出力の例

入力:
異なる重みの集合
{23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}

出力:
合計の差が最小になるように重みを振り分けた左側・右側の部分集合
Left: {45, -34, 12, 98, -1}
Right: {23, 0, -99, 4, 189, 4}

アルゴリズムの考え方

この問題はバックトラッキング（探索の枝刈り）を用いて解きます。各要素について「左側のグループに入れる／入れない」を順番に試しながら再帰的に探索し、左側の要素数が n/2 に達した時点で合計の差を評価します。これにより、すべての組み合わせを総当たりせずとも効率的に最適解へたどり着けます。

tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos)

引数の意味：

• weight： 与えられた重み（値）の配列
• n： 要素の総数
• curr： 現在の探索状態を記録するフラグ配列
• select： すでに選択済みの要素数
• sol： 最良解を保存するフラグ配列
• diff： 2つの部分集合の合計の差（最小値を更新していく）
• sum： 全要素の合計値
• total： 現在選択中の部分集合の合計値
• pos： 現在処理中の要素の位置

出力： 左右の部分集合に対応する最良の解の集合。

Begin
    if pos = n, then            // すべての要素を処理し終えたら終了
       return
    if (n/2-select) > (n - pos), then   // 残りの要素では必要な個数に届かない場合は枝刈り
       return
    tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1)
    select := select + 1
    total := total + weight[pos]
    curr[pos] := true           // pos の要素を選択に含める場合

    if select = n/2, then       // 左側グループが完成したら
       if difference of (sum/2 and total) < diff, then
          diff := difference of (sum/2 and total)
          for i := 0 to n, do
             sol[i] := curr[i]
          done
    else
       tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1)
    curr[pos] := false          // 条件を満たさなければ選択を取り消す（バックトラック）
End

ポイント：枝刈りによる高速化

「(n/2 − select) > (n − pos)」という条件チェックが重要です。残りの要素数では左側グループに必要な個数を満たせない場合、その先の探索を打ち切ることで無駄な計算を大幅に削減できます。

C++による実装例

#include <iostream>
#include<cmath>
using namespace std;

void tugOfWar(int* weight, int n, bool curr[], int select, bool sol[], int &diff, int sum, int total, int pos) {
    if (pos == n)      // すべての重みを走査し終えたら終了
       return;
    if ((n/2 - select) > (n - pos))     // 残り要素では必要数に届かない場合は枝刈り
       return;
    tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1);

    select++;
    total += weight[pos];
    curr[pos] = true;      // 現在の要素を解に追加

    if (select == n/2) {       // グループが完成したとき
       if (abs(sum/2 - total) < diff) {     // より良い解かどうか判定
          diff = abs(sum/2 - total);
          for (int i = 0; i<n; i++)
             sol[i] = curr[i];
       }
    } else {
       tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1);
    }
    curr[pos] = false;     // 条件を満たさなければ選択を取り消す
}

void findSolution(int *arr, int n) {
    bool* curr = new bool[n];
    bool* soln = new bool[n];
    int diff = INT_MAX;         // 差の初期値を最大値に設定
    int sum = 0;

    for (int i=0; i<n; i++) {
        sum += arr[i];                     // 全要素の合計を求める
        curr[i] =  soln[i] = false;     // フラグをすべて false で初期化
    }

    tugOfWar(arr, n, curr, 0, soln, diff, sum, 0, 0);
    cout << "Left: ";

    for (int i=0; i<n; i++)
        if (soln[i] == true)
           cout << arr[i] << " ";
    cout << endl << "Right: ";

    for (int i=0; i<n; i++)
        if (soln[i] == false)
           cout << arr[i] << " ";
}

int main() {
    int weight[] = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4};
    int n = 11;
    findSolution(weight, n);
}

実行結果

Left: 45 -34 12 98 -1
Right: 23 0 -99 4 189 4

このように、11個の要素（奇数）が5個と6個の2グループに分割され、両グループの合計の差が最小となる組み合わせが出力されます。負の値を含むデータにも対応できる点も、このアルゴリズムの特徴です。

まとめ

綱引きアルゴリズムは、バックトラッキングを活用して「2グループへの均等分割＋合計差の最小化」を実現する古典的な探索手法です。要素ごとに「含める／含めない」を試行し、条件を満たさない経路を早期に切り捨てることで効率よく最適解を求められます。パーティション問題や負荷分散など、さまざまな場面に応用できる考え方なので、ぜひ理解しておきましょう。