ワードラップ問題を動的計画法で解く｜バランスの取れた改行アルゴリズムとC++実装

ワードラップ（Word Wrap）問題は、一連の単語と「1行に入力できる最大文字数」が与えられたとき、どこで改行すればテキストがもっとも見やすくなるかを求める、動的計画法の古典的な応用例です。

ポイントとなるのは行のバランスです。余分な空白が多い行と、ぎりぎりまで詰め込まれた行が混在すると、文章全体の見た目が悪くなります。このアルゴリズムでは、各行の余白の量をコストとして評価し、その合計が最小になるように改行位置を決めることで、余白が均等に分散した美しい整形を実現します。

アルゴリズムを実行すると、「1行あたり何個の単語を配置できるか」と「全体で何行必要か」が得られます。

入力と出力

入力：
各単語の長さの配列 {3, 2, 2, 5}。行の最大幅は 6。
出力：
1行目：単語番号 1 ～ 1（最初の単語のみ）
2行目：単語番号 2 ～ 3（2番目と3番目の単語）
3行目：単語番号 4 ～ 4（4番目の単語）

アルゴリズム

wordWrap(wordLenArr, size, maxWidth)

入力：単語の長さの配列、配列のサイズ、行の最大幅

出力：各行に配置される単語の範囲のリスト

処理の流れ

このアルゴリズムは、次の3つのステップで構成されます。

1. 余白の計算：単語 i から j を同じ行に置いたときの余白（残りスペース）を、すべての組み合わせについて求めます。
2. 行コストの計算：余白が負（＝その行に収まりきらない）ならコストは無限大、最終行ならコスト0、それ以外は「余白の2乗」を行コストとします。
3. 最小コストの探索：動的計画法により、先頭から各単語位置までの累積コストが最小になる分割方法を求めます。

余白の2乗和をコストに採用するのは、余白の偏りに対して大きなペナルティを与えるためです。これにより、ある行に空白が集中するような非効率な改行が自動的に避けられます。また、最終行にはペナルティを課さないのが一般的です。

Begin
    define two square matrix extraSpace and lineCost of order (size + 1)
    define two array totalCost and solution of size (size + 1)

    for i := 1 to size, do
        extraSpace[i, i] := maxWidth – wordLenArr[i − 1]
        for j := i+1 to size, do
            extraSpace[i, j] := extraSpace[i, j−1] – wordLenArr[j − 1] – 1
        done
    done

    for i := 1 to size, do
        for j := i to size, do
            if extraSpace[i, j] < 0, then
                lineCost[i, j] := ∞
            else if j = size and extraSpace[i, j] ≥ 0, then
                lineCost[i, j] := 0
            else
                lineCost[i, j] := extraSpace[i, j]^2
        done
    done

    totalCost[0] := 0
    for j := 1 to size, do
        totalCost[j] := ∞
        for i := 1 to j, do
            if totalCost[i−1] ≠ ∞ and lineCost[i, j] ≠ ∞ and
               (totalCost[i−1] + lineCost[i, j] < totalCost[j]), then
                totalCost[j] := totalCost[i−1] + lineCost[i, j]
                solution[j] := i
        done
    done
    display the solution matrix
End

C++による実装例

#include<iostream>
using namespace std;

int dispSolution (int solution[], int size) {
    int k;
    if (solution[size] == 1)
        k = 1;
    else
        k = dispSolution (solution, solution[size]-1) + 1;
    cout << "Line number "<< k << ": Word Number: " <<solution[size]<<" to "<< size << endl;
    return k;
}

void wordWrap(int wordLenArr[], int size, int maxWidth) {
    int extraSpace[size+1][size+1];
    int lineCost[size+1][size+1];
    int totalCost[size+1];
    int solution[size+1];

    for(int i = 1; i<=size; i++) {      //すべての行について余白を求める
        extraSpace[i][i] = maxWidth - wordLenArr[i-1];

        for(int j = i+1; j<=size; j++) {   //単語i～jを1行に収めた場合の余白
            extraSpace[i][j] = extraSpace[i][j-1] - wordLenArr[j-1] - 1;
        }
    }

    for (int i = 1; i <= size; i++) {   //余白の配列をもとに行コストを求める

        for (int j = i; j <= size; j++) {

            if (extraSpace[i][j] < 0)
                lineCost[i][j] = INT_MAX;
            else if (j == size && extraSpace[i][j] >= 0)
                lineCost[i][j] = 0;
            else
                lineCost[i][j] = extraSpace[i][j]*extraSpace[i][j];
        }
    }

    totalCost[0] = 0;
    for (int j = 1; j <= size; j++) {   //各単語位置までの最小コストを求める
        totalCost[j] = INT_MAX;

        for (int i = 1; i <= j; i++) {
            if (totalCost[i-1] != INT_MAX && lineCost[i][j] != INT_MAX && (totalCost[i-1] + lineCost[i][j] < totalCost[j])){
                totalCost[j] = totalCost[i-1] + lineCost[i][j];
                solution[j] = i;
            }
        }
    }

    dispSolution(solution, size);
}

main() {
    int wordLenArr[] = {3, 2, 2, 5};
    int n = 4;
    int maxWidth = 6;
    wordWrap (wordLenArr, n, maxWidth);
}

再帰関数 dispSolution() は、solution 配列をたどって各行の開始単語を遡り、行番号順に結果を出力します。wordWrap() 本体では、余白・行コスト・累積コストの3段階の計算を行い、最後に解を表示します。

出力

Line number 1: Word Number: 1 to 1
Line number 2: Word Number: 2 to 3
Line number 3: Word Number: 4 to 4

計算量

余白と行コストの表を作成するのに O(n²)、最小コストを求める動的計画法も O(n²) のため、全体の時間計算量・空間計算量はともに O(n²) となります。