最小限のコストでN本のロープを接続するアルゴリズム

長さの異なる N 本のロープが与えられます。これらをすべて連結しなければなりませんが、2 本のロープをつなぐコストは「その 2 本の長さの合計」となります。ここでの目的は、N 本すべてのロープを最小のコストで 1 本につなぎ合わせることです。

この問題はヒープ木（優先度付きキュー）を使うと効率よく解けます。まずすべてのロープの長さを最小ヒープに挿入し、ヒープから最も短いロープと 2 番目に短いロープを取り出して連結します。その後、連結後の長さを再びヒープに戻します。この操作を繰り返し、ヒープ内に要素が 1 つだけになった時点で処理を終了すれば、最小コストで連結されたロープが得られます。

この手法がうまく機能するのは、短いロープほど連結の対象になる回数が多いためです。毎回最も短い 2 本を選んでつなぐことで、短いロープがコスト計算に登場する回数を抑えられます。これは典型的な貪欲法（グリーディ法）の応用例といえます。

入力と出力

入力：
ロープの長さ：{4, 3, 2, 6, 5, 7, 12}
出力：
合計最小コスト：103

アルゴリズム

findMinCost(array, n)

入力 − ロープの長さのリスト、およびリスト内の要素数

出力 − ロープを連結する際の最小コスト

Begin
    minCost := 0
    配列の全要素で優先度付きキューを初期化（小さい値ほど高い優先度＝最小ヒープ）
    while キューのサイズが 1 より大きい間、繰り返す
        item1 := キューから最小の要素を取り出して削除
        item2 := キューから次に小さい要素を取り出して削除
        minCost := minCost + item1 + item2
        (item1 + item2) をキューに追加
    done
    return minCost
End

計算過程の例

入力 {4, 3, 2, 6, 5, 7, 12} の場合、処理は次のように進みます。

最終的に、合計最小コストは 103 となります。

C++ による実装例

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int findMinimumCost(int arr[], int n) {
    // 最小ヒープとして動作する優先度付きキューを用意
    priority_queue< int, vector<int>, greater<int>> queue(arr, arr+n);

    int minCost = 0;

    while (queue.size() > 1) {            // キューに2本以上のロープがある間
        int item1 = queue.top();           // item1 は最も短いロープ
        queue.pop();

        int item2 = queue.top();           // item2 は2番目に短いロープ
        queue.pop();

        minCost += item1 + item2;          // 連結コストを加算
        queue.push(item1 + item2);         // 連結したロープをキューに戻す
    }
    return minCost;
}

int main() {
    int ropeLength[] = {4, 3, 2, 6, 5, 7, 12};
    int n = 7;
    cout << "Total minimum cost: " << findMinimumCost(ropeLength, n);
}

実行結果

Total minimum cost: 103

各ステップでヒープへの挿入と削除を行うため、このアルゴリズムの計算量は O(N log N) となります。ロープの本数が増えても効率的に動作するのが特徴です。