【再帰・分割統治法】高速なソートアルゴリズム前提知識 -考え方編-

高速なアルゴリズムと呼ばれる以下の3つ。

• クイックソート
• マージソート
• ヒープソート

これらは、直感的にはちょっと分かりづらい。

なぜかというと、単純なアルゴリズム三つ(バブル・選択・挿入ソート)とは違って、他のアルゴリズムやデータ構造の知識も必要になるからだ。

そこで、今回はいきなりソートアルゴリズムに入るのではなく、前提知識を補充しておこう。

その中でも、アルゴリズム…考え方の部分を解説していく。

前回の復習

今回とは直接関係ないのだが、前回の復習をしておこう。

まず、前回からソートアルゴリズム…複数のデータを昇順(あるいは降順)に並べ替える考え方を解説している。

前回は、単純なアルゴリズムと呼ばれる以下3つを解説した。

• バブルソート
• 選択ソート
• 挿入ソート

また、並べ替える際に参照する値が同じだった場合、元の順番が保持されるかどうか、という安定・不安定という用語も解説した。

今回、次回はいったんこれらのソートから離れるが、更にその次でまた戻ってくるので、それまでに理解しておいて欲しい。

高速なアルゴリズムのための考え方

今回は、大きく二つの考え方を扱う。

一つは、再帰。これは、アルゴリズムというよりプログラムのお話に近い。

で、もう一つは、分割統治法。これは、アルゴリズムの種類と思ってくれていいだろう。

再帰とは

再帰とは、ある処理について、再度自分自身を呼びだすような処理のことだ。

もうちょっと具体的に言うと、関数内で、自身を呼びだす処理のこと。

「え、何に使うの？」と思われるかもしれないので、使える例をいくつか紹介していこう。

再帰の例

まずは、簡単なものから。

前回まで、1からnまでの和を求める2つの関数を何度も出していると思う。

for文で回す方法と、公式を使って1回の計算で求める方法だ。

その他にも、この再帰を使って求めることもできる。以下のように組んでみよう。

function sumAll3(n){
    if(n == 1){
        return 1;
    }
    var nn = sumAll3(n - 1)
    return n + nn;
}

ちょっとハイライトを付けた部分、ここで再帰を行っている。

そのままではちょっと分かりづらいと思うので、入力を4として細かく見ていこう。

• 4が入力され、1ではないので5行目へ。
• sumAll3(3)を実行する。
  • 3が入力され、1ではないので5行目へ。
  • sumAll3(2)を実行する。
    • 2が入力され、1ではないので5行目へ。
    • sumAll3(1)を実行する。
      • 1が入力され、ifが真なので1を返す。
    • 2と1を足し、3を返す。
  • 3と3を足し、6を返す。
• 4と6を足し、10を返す。

こんな感じだ。

ここで一つ注意だが、必ず終了条件を設定すること。

今回の例だと、最初のif文がそうだ。これがないと、マイナスの数を含め、どんどん小さい数まで足してしまう。

そして、それが無限に続き…はせず、途中でエラーが発生する。

なので、「こうなったら終わる」というものを必ず設定するようにしよう。

次に、ちょっと複雑にしてみよう。フィボナッチ数列をご存じだろうか。

これは、以下で表される(数学的な)関数だ。

$$f(n) = \left\{ \begin{array}{ll} 0 & ( n = 0 ) \\ 1 & ( n = 1 ) \\ f(n-1)+f(n-2) & ( n > 1 ) \end{array} \right.$$

具体的な数字を入れると、0から順番に\(0, 1, 1, 2, 3, 5, 8, 13, 21, …\)となる。

これを、再帰を使ったプログラムで書いてみよう。

function fibonacci(n){
    if(n == 0){
        return 0;
    }
    if(n == 1){
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

こんな感じだ。具体的な動き方は、皆さんにお任せしよう。

分割統治法

分割統治法とは

分割統治法とは、誤解を恐れずに言ってしまうと「大きな問題を、小さく分けて考えよう」というものだ。

ただし、元の問題を解決する手法と、小さく分けた後に使う手法が一致している、というのが条件になる。

手法が一致している、ということは…そう、上で解説した再帰の考え方を使うのだ。

分割統治法の例

具体的な考え方で解説しよう。例えば、100個の数字が並んでいて、それを並び替えたいとする。

そのとき、とりあえず適当に1個数字を選ぶ。

そして、その数字より左に小さいグループと、右に大きいグループを作る。

で、その左側、右側それぞれで同じことをする。つまり…

お分かりだろうか。小さい問題に分割して、また同じことを繰り返す。

これでどんどん小さくしていき、それ以上分割できなかったら今度はくっつけていく。

すると、最終的に元に戻ってきて、並び替えが終わっているのだ。

このように問題を解決する手法を、分割統治法と呼ぶ。

…実は、上で出した例はそのまま高速なアルゴリズムの一つ「クイックソート」の考え方だ。

どうやってコーディングするのかは、またその時にお見せしよう。

ちなみに、「マージソート」もこの考え方を使っている。

まとめ

今回は、再帰と分割統治法という二つの考え方を紹介した。

• 再帰：ある処理の中で、自分自身を再度呼び出す考え方
• 分割統治法：大きい問題を、小さい問題に分けて解決する考え方

これらは、高速なアルゴリズムのクイックソートとマージソートに使われている。

「あれ、ヒープソートは？」と思われるかもしれないが、実はヒープソートにはデータ構造の考え方のみ使われている。

そのまま、ヒープという構造がある。詳細は、次回解説しよう。

更新情報はTwitterでも呟いている。よかったらページ下部のTwitterアイコンから覗いていってほしい。

それでは。

オマケ：バックトラック法

オマケにするほど小さい内容でもないのだが、再帰と密接に絡んでいるのでこれも解説してしまおう。

あ、高速なアルゴリズムには関係ないので、ちょっと別枠で考えて欲しい。

バックトラック法とは

バックトラック法とは、ある問題を解決するときに、いったん考えられるパターンを埋めていき、条件を満たさなくなったらちょっと前に戻って別のパターンを考える…ということを繰り返す方法だ。

要するに、とりあえずやってみて、ダメなら戻って別のことをやってみる。

高速に計算できるコンピュータだからこそできる力技だ。

これをやるときは、ふつうは再帰を使用する。で、大枠は以下の通りだ。

• 全部の条件に合致していたらOKを返す
• 考えられるパターンで以下の繰り返し処理を行う
  • パターンの一つを試しに入れる
  • 再帰を行い、その結果がOKだったらここでもOKを返す
  • 駄目だったらそのパターンを取り消す

バックトラック法の例

上だけ見て分かれば苦労しない。というわけで具体例を見ていこう。

有名なのは、8-クイーン問題というもの。

これは、8×8のチェス盤上に、8個のクイーンを縦・横・斜めに重ならないように1個ずつ置くパターンを求める問題だ。

一般化して、n-クイーン問題と呼んだりもする。n×nの盤上に、n個のクイーン。

考え方としては以下の通りだ。

入力は、その時点での盤面arrと今何個のクイーンを置いたかqの2つ。

一番最初は、何も置かれていない盤面と、0個置いたということで0を入力することになる。

なお、マスの横については左から右に\(0, 1, 2, …, n-1\)となっていることとしよう。

また、マスの縦も同じく上から順に\(0, 1, 2, …, n-1\)となっているが、今何個のクイーンを置いたかと一致している。

1. qとnが等しいなら、trueを返す
2. iを0からn-1まで増やしながら、以下を繰り返す
   1. arr[q][i]にクイーンを置けるかチェックし、置けるなら以下を実行
      1. arr[q][i]にいったんクイーンを置く
      2. 自身を(arr, q + 1)で呼び出し、その結果がtrueならここでもtrueを返す
      3. いったん置いたクイーンを取り除く
3. このパターンはクイーンを置けなかったのでfalseを返す

これを解くソースコードも載せてしまおう。

二つ関数があるが、上のsolve関数が上のアルゴリズムを実装した関数、下のcheck関数がそこにクイーンを置けるかどうか判定する関数だ。

function solve(arr, q){
    var n = arr.length;
    if(n == q){
        return true;
    }
    for(var i = 0; i < n; i++){
        if(check(arr, q, i)){
            arr[q][i] = 1;
            if(solve(arr, q + 1)){
                return true;
            }
            arr[q][i] = 0;
        }
    }
    return false;
}

function check(arr, q, i){
    var n = arr.length;
    for(var j = 0; j < n; j++){
        if(arr[j][i] != 0){
            return false;
        }
        if(arr[q][j] != 0){
            return false;
        }
    }

    var up = [];
    var down = [];
    for(var j = 0; j < n * 2 - 1; j++){
        up[j] = 0;
        down[j] = 0;
    }
    for(var j = 0; j < n; j++){
        for(var k = 0; k < n; k++){
            up[j + k] += arr[j][k];
            down[j - k + n - 1] += arr[j][k];
        }
    }
    if(up[q + i] != 0){
        return false;
    }
    if(down[q - i + n - 1] != 0){
        return false;
    }
    return true;
}

これを一個一個解説…したいのだが、あまりにも長くなってしまうので、割愛させていただく。

よかったら、一回一回どうやって動いているか、出力などしながら確認してみて欲しい。