第二回とありますが続かない可能性が高いです。

「幅」とは?

幅優先探索は「なんの幅」を優先しているのでしょうか?どういう場合に使えるのでしょうか?今回はそんな疑問も解消します。

ルービックキューブを解く

前回、深さ優先探索を解説しました。深さ優先探索は「とりあえずゴールまでズンズン進んでダメだったらやり直す」トライ&エラー型でした。では深さ優先探索でルービックキューブはとけるでしょうか?

結論から言えば、深さ優先探索ではルービックキューブは解けません。なぜなら「やり直そう」と思うタイミングが存在しないためです。何をどこまでやったら「条件を満たしているか(=完成したか)」判定するべきか、そんな設定ができないのです。

ではどうすればいいのでしょうか?ここで登場するのが「幅優先探索」です。

とりあえず回してみる

ルービックキューブを自力で解けるとIQ130あるらしいので、僕のようなポンコツには綺麗なアルゴリズムは書けません。でもゴリ押しのアルゴリズムならできます。とりあえず回してみればいいのです。

まず1回、どこでもいいので回してみます。これでもし完成しなかったら初期状態に戻します。そして、別のところを1回まわしてみて完成するか確認します。ダメならまた元に戻します。

1回まわすだけではダメと分かったら、回数を増やしてみます。初期状態から2回まわしてみます。すべてのパターンを試してもダメなら回す回数を3回にしてみます。

このようにしてどんどん回す回数を増やしていけば、いずれ完成するはずです。パターン数が膨大にこそなりますが*1。

具体的な解法

実際のアルゴリズムとしては次のようになります。

1回まわして、まわしたあとの状態をキュー(付録1参照)へ格納
もとに戻してすべての回し方を試す
キューから状態を取り出し(=1回まわしたあとの状態のうちはじめのもの)すべての回し方を試す
それぞれの状態をキューへ格納する
6面揃うまで3と4を繰り返す

このようになります。2回まわすときはわざわざ初期状態から回すのではなく、1回まわしたあとの状態から回す、ということをしています。このコードは付録2に記しました。

結局、幅優先探索とは

さて話を戻します。ルービックキューブを解くアルゴリズムでは、「初期状態」から「1回まわしてできる状態」をすべて試して、ダメなら「2回まわしてできる状態」をすべて試して、それもダメなら…というふうに回す回数を増やしていきました。これを図に表すとこのようになります(簡略化されていますがご了承ください)。

f:id:panda_noir:20170913125306p:plain

前回の「深さ優先探索」は、この図でいうと「下へ下へ」掘り進む探索です。まさに「深さを」優先しています。

それに対して、「幅優先探索」はこの図でいうと「まず1層目、次は2層目」というふうに浅く広く掘っていく探索です。まさに「幅を」優先しています。

そう、この図こそが「深さ優先探索」「幅優先探索」の名前の意味なのです。

深さ優先探索と幅優先探索のつかいわけ

「深さ優先探索」と「幅優先探索」は深さが有限かどうか、でつかいわけることができます。

「ナンプレ」は、とりあえず可能な限りマス目を埋めていくと、必ず埋められるマスがなくなる=限界がきます。そこから状態を変えることができないのですから、そこが最下層です。

それに対して「ルービックキューブ」はとりあえずで回し続けていても、ずっと回していられるので限界はきません。深さが無限ということです。

なんとなく違いがわかっていただけたでしょうか?

付録

1. キューとは

キューとは簡単に言うと「格納された順に値が取り出される配列」です。簡単に実装するとこんな感じです。

class Queue {
    constructor() {
        this.queue = [];
    }
    push(val) {
        this.queue.push(val); // 末尾に要素を加える
    }
    pop(val) {
        return this.queue.shift(); // 先頭(=はじめに格納された要素)を取り出す
    }
}
const q = new Queue();
q.push(1); q.push(2); q.push(3);
q.pop(); // 1
q.pop(); // 2
q.pop(); // 3

2. 疑似コード

const cube = new RubiksCube();
const queue = new Queue();
queue.push(cube); // 初期状態を格納
while(true) {
    const now = queue.pop();
    if (now.isFinished()) break; // 完成していたらループを抜ける
    // ルービックキューブの回し方は12通りあるのですべて試す。
    // 以下のRやLというのは回し方を表す記号。本記事とはあまり関係ないので説明は割愛
    queue.push(now.rotate('R'));
    queue.push(now.rotate("R'"));
    queue.push(now.rotate('L'));
    queue.push(now.rotate("L'"));
    queue.push(now.rotate('U'));
    queue.push(now.rotate("U'"));
    queue.push(now.rotate('D'));
    queue.push(now.rotate("D'"));
    queue.push(now.rotate('F'));
    queue.push(now.rotate("F'"));
    queue.push(now.rotate('B'));
    queue.push(now.rotate("B'"));
}

このコードはRubiksCubeクラスさえ実装すれば完璧に動きます。

ちなみに、このアルゴリズムは計算量が大きすぎる(揃うのにN回まわすとすると12^N回試行しなければならない)ので、実際に解くときはこれを改良したアルゴリズムを使います。具体的には、初期状態から探索しつつ、同時に完成形からも探索していきます。二つが同じところにたどり着いたらそれがゴールです。これなら揃うのにN回まわすと仮定すると2*12^N/2しかかかりません。先ほどの計算量と比べるとかなり減っていることがわかります。

*1:ルービックキューブ「神の数字」を証明によれば、初期状態がどうであれ必ず20手以内で解けるらしいので、計算量はせいぜい12²⁰程度です。さらに改善したアルゴリズムなら2*12¹⁰、つまり1200億ほどで解けます

Panda Noir

JavaScript の限界を究めるブログでした。最近はいろんな分野を幅広めに書いてます。

アルゴリズム勉強会第二回幅優先探索