全探索アルゴリズム入門

はじめに

本記事はアルゴリズムを勉強し始めた人向け(初心者/中級者)に、アルゴリズムとは何で、なぜ勉強する必要があるのか、またどのように学習したら良いのかなどをまとめた記事である。
本記事で対象とするアルゴリズムは全探索アルゴリズムのみで、ソートアルゴリズムなど別のアルゴリズムを勉強したい人には無意味な記事である。

アルゴリズムの基礎知識

アルゴリズムとは

アルゴリズムとは 何らかの問題を解決する手順 のことであり、この手順をコンピュータが理解できるように記述したものがプログラムである。つまり、プログラムを書いている以上は何らかのアルゴリズムを記述していることになるのである。

なぜプログラマにアルゴリズムの知識が必要なのか

プログラマにアルゴリズムの知識が必要な理由は アルゴリズムの違いによってプログラムの処理能力に雲泥の差が生じるから である。一般的にプログラムの処理能力の差はデータ量などが増えると大きくなる傾向にある。大規模なデータを処理する場合、あるアルゴリズムでは1分で済む処理が、別のアルゴリズムでは1日かかる(または1日かかっても終わらない)場合もある。処理の完了に1日かかる(または1日かかっても終わらない)ようなプログラムしか作れないプログラマは使い物にならないだろう。

良いアルゴリズムとは

アルゴリズムの善し悪しを判断する指標の一つに 計算量 という概念がある。計算量には、アルゴリズムの実行に必要な時間を表す 時間計算量 と、アルゴリズムの実行に必要なメモリ領域を表す 領域計算量 の2つがある。時間計算量の少ないアルゴリズムは計算回数が少ないので早く結果が返ってくるだろう。また、領域計算量の少ないアルゴリズムはメモリを多く搭載できない場合でも動作するだろう。つまり計算回数とメモリ使用量が共に少ない(計算量が少ない)アルゴリズムが良いアルゴリズムとなる。
ただし、時間計算量と領域計算量はトレードオフの関係にあるため、プログラムの目的に応じて相反する2つの要素を調整する必要がある。

アルゴリズムの学習方法

アルゴリズムを学習する方法は人それぞれだろうが、私は 実際に自分でプログラミングの問題を解くこと が必要だと思う。プログラミングの問題を提供しているサービスの一例としては AIZU ONLINE JUDGE や CodeIQ や Paiza などがある。これらのサービスの中には自分の回答に対してフィードバックをもらえるものもあるので、自分のスキルを客観的に把握できておもしろいと思う。

注1:CodeIQで出題される問題には「腕試し」問題と「ウチに来ない？」問題の2種類がある。「ウチに来ない？」問題は転職希望者向けの問題なので、転職希望でない方は「ウチに来ない？」問題の挑戦は控えましょう

注2:Paizaを利用するが転職意思はない場合は、スカウトを受けないよう設定をしましょう

全探索アルゴリズム

本記事では、[アルゴリズムの学習方法]で紹介したサービスが提供する問題を解く際に必要となるアルゴリズムとして、全探索アルゴリズムの解説を行うこととする。
全探索アルゴリズムには 幅優先アルゴリズム と 深さ優先アルゴリズム の2つがある。

幅優先探索とは？

幅優先探索とは グラフ を始点から近い順に1つずつ調べていく探索法のこと。グラフの全ての頂点を漏れなく調べるのに非常に有効な探索法である。
幅優先探索における探索手順のイメージは VisuAlgo (アルゴリズムをビジュアル化するサービス)の「Graph Traversal」の「BFS」で掴むことができると思う。ちなみに「BFS」は「Breadth First Search」の略で、幅優先探索の意味。

例題1:最短歩数の測定

問題

幅優先アルゴリズムの実装例を示す例題として、最短歩数を求める問題がある。問題の概要は下記の通り( 例題1は こちらの記事 を参考にしました )。

列の数がm、行の数がnのマスで構成される迷路がある。
迷路の各マスはスタート(s)、ゴール(g)、通行可能なマス(0)、通行不可能なマス(1)のいずれかの状態である。
スタート(s)から出発し上下左右に1マスずつ通行可能なマス(0)のみ通りゴール(g)まで移動した場合の、最短歩数を求めよ。

[入力]
1行目には列の数mと行の数nがスペース区切りで入力される。
2行目以降は、m個の文字がスペース区切りでn行入力される。
2行目以降に入力される文字は s/g/0/1 のいずれかであり、他の文字が入力されることは考慮しなくて良い。

[出力]
最短歩数を一行で出力する。
ただしゴールにたどり着けない場合は「-1」を出力する。

入力値のサンプルとしては下記のような感じ。

1:5 6
2:s 0 0 0 0
3:0 0 1 0 0
4:0 1 0 0 0
5:0 0 g 1 0
6:0 0 0 0 0
7:0 0 1 0 0

回答例

手順

1. 迷路を作成する
2. 各マスの訪問履歴を作成する
3. スタートのマスをキューに格納する
4. キューの先頭から一マス取得する
5. 取り出したマスがゴールなら終了
6. 手順4で取り出したマスから上下左右の何れかに移動する
7. 移動先のマスが迷路外でないことを確認する(迷路外の場合は手順6に戻る)
8. 移動先のマスが道またはゴールであることを確認する(道でもゴールでもない場合は手順6に戻る)
9. 移動先のマスが未訪問であることを確認する(訪問済みの場合は手順6に戻る)
10. 移動先のマスをキューに格納し、訪問履歴を更新する
11. 4から10をキューが空になるまで繰り返す

実装例(C++11)

bfs.cpp

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef vector<vector<char>> field_t;

typedef pair<int, int> point_t;

point_t operator+(const point_t &lhs, const point_t &rhs)
{
    point_t p = { lhs.first + rhs.first, lhs.second + rhs.second };
    return p;
}

bool operator==(const point_t &lhs, const point_t &rhs)
{
    return (lhs.first == rhs.first) && (lhs.second == rhs.second);
}

bool is_in_field(int col, int row, const point_t &point)
{
    const int c = point.second;
    const int r = point.first;
    return (0 <= c && c < col) && (0 <= r && r < row); 
}

int solve(int col, int row, field_t &field, const point_t &start, const point_t &goal)
{
    // 2. 各マスの訪問履歴(memo)を作成する
    //    memoにはスタートからそのマスまでの歩数を格納する(初期値は0)
    vector<vector<int>> memo;
    for(int i = 0; i < row; ++i) {
        vector<int> v(col, 0); 
        memo.push_back(v);
    }   

    // 移動方向(上下左右)
    const point_t points[] = { 
        { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 },
    };  

    // 3. スタートのマスをキューに格納する
    queue<point_t> q;
    q.push(start);

    // 11. 4から10をキューが空になるまで繰り返す
    while( !q.empty() ) {
        // 4. キューの先頭から一マス取得する
        point_t cur = q.front(); q.pop();

        // 5. 取り出したマスがゴールなら終了
        if(cur == goal) {
            return memo[cur.first][cur.second];
        }

        for(const auto &point : points) {
            // 6. 手順4で取り出したマス(cur)から上下左右の何れかに移動する
            point_t next = cur + point;
            // 7. 移動先のマス(next)が迷路外でないことを確認する(迷路外の場合は手順6に戻る)
            if( is_in_field(col, row, next) ) {
                const char s = field[next.first][next.second];
                // 8. 移動先のマス(next)が道またはゴールであることを確認する(道でもゴールでもない場合は手順6に戻る)
                if(s == '0' || s == 'g') {
                    // 9. 移動先のマス(next)が未訪問であることを確認する(訪問済みの場合は手順6に戻る)
                    if(memo[next.first][next.second] == 0) {
                        // 10. 移動先のマス(next)をキューに格納し、訪問履歴を更新する
                        q.push(next);
                        memo[next.first][next.second] = memo[cur.first][cur.second] + 1;
                    }
                }
            }
        }
    }
    return -1;
}

int main()
{
    int col, row;
    cin >> col >> row;

    point_t start, goal;
    field_t field;

    // 1. 迷路(field)を作成する
    for(int i = 0; i < row; ++i) {
        vector<char> v;
        for(int j = 0; j < col; ++j) {
            char c;
            cin >> c;
            v.push_back(c);
            // スタート地点とゴール地点は別途覚えておく
            if( c == 's' ) {
                start.first = i;
                start.second = j;
            } else if( c == 'g' ) {
                goal.first = i;
                goal.second = j;
            }
        }
        field.push_back(v);
    }

    // 最短歩数はsolveで計算する
    cout << solve(col, row, field, start, goal) << endl;
    return 0;
}

解説

上に載せたサンプル値を例に若干の解説。
回答例で示したコードの動作を文章で記述すると以下のようになる。

1. 迷路の初期状態(下図(0))のsからスタートする。
2. (0)のsから上下左右に移動した状態が(1)となる。(1)のAとBは(0)のsから移動可能なマスを示す。
   AとBは未訪問なマスのためキューに格納される(キューのサイズは2となる)。
3. (1)のAから上下左右に移動した状態が(2)となる。(1)のAからは(2)のs, C, Dに移動可能。CとDは未訪問なマスのためキューに格納される(キューのサイズは3となる)。
4. (1)のBから上下左右に移動した状態が(3)となる。(1)のBからは(3)のs, D, Eに移動可能。Eは未訪問なますのためキューに格納される(キューサイズは3となる)。
5. (2)のCから...

(0)          (1)          (2)          (3)
s 0 0 0 0    s B 0 0 0    s B 0 0 0    s 0 E 0 0
0 0 1 0 0    A 0 1 0 0    0 D 1 0 0    A D 1 0 0
0 1 0 0 0    0 1 0 0 0    C 1 0 0 0    0 1 0 0 0
0 0 g 1 0    0 0 g 1 0    0 0 g 1 0    0 0 g 1 0
0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0
0 0 1 0 0    0 0 1 0 0    0 0 1 0 0    0 0 1 0 0

回答例では、移動先のマスが訪問済みか否かを覚えておくことで、計算量を減らすよう工夫してある。訪問済みか否かを覚えておかなかった場合、(1)→(2), (1)→(3)の遷移でDが重複してキューに格納されることとなり、全く同じ状態を複数回計算することとなる。6行5列程度の迷路なら同じ状態を重複しても問題ないかもしれないが、1000行1000列の迷路とかになると、しんどいだろう。

深さ優先探索とは？

深さ優先探索とはある状態から始めて、遷移できなくなるまで状態遷移を続け、遷移できなくなったら一つ前の状態に戻って・・・を繰り返すことで、 グラフ の全頂点を漏れなく調べる探索法である。
深さ優先探索における探索手順のイメージは VisuAlgo (アルゴリズムをビジュアル化するサービス)の「Graph Traversal」の「DFS」で掴むことができると思う。ちなみに「DFS」は「Depth First Search」の略で、深さ優先探索の意味。

例題2:CrazyBot

問題

問題文は こちら を参照。

回答例(C++11)

手順

1. 各マスの訪問履歴を作成する
2. CrazyBotが東西南北の各方角に進む確率を作成する
3. 探索を開始する
4. 訪問済みのマスの場合は0.0を返す(訪問済みのマスには再訪不可)
5. 所定の歩数進んだ場合は1.0を返す(探索終了)
6. 現在のマスの訪問履歴を訪問済みにする
7. 現在のマスから東西南北に進む確率を計算する(所定の歩数進み終えていない場合は手順4に戻る)
8. 現在のマスの訪問履歴を未訪問にする
9. グラフの全頂点の探索を終えるまで探索を繰り返す

回答例

dfs.cpp

#include <iostream>
#include <vector>

using namespace std;

class CrazyBot
{
    private:
        vector<pair<int, int>> directions_ = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} }; // 東西南北
        vector<vector<bool>> memo_;
        vector<double> probabilities_;
    private:
        double dfs(int col, int row, int n)
        {   
            // 4. 訪問済みのマスの場合は0.0を返す(訪問済みのマスには再訪不可)
            if(memo_[row][col]) return 0.0;

            // 5. 所定の歩数進んだ場合は1.0を返す(探索終了)
            if(n == 0) return 1.0;

            // 6. 現在のマス(row, col)の訪問履歴を訪問済みにする
            memo_[row][col] = true;
            double res = 0.0;
            // 7. 現在のマス(row, col)から東西南北に進む確率を計算する(所定の歩数進み終えていない場合は手順4に戻る)
            for(size_t i = 0; i < directions_.size(); ++i)
                res += dfs(col + directions_[i].second, row + directions_[i].first, n - 1) * probabilities_[i];

            // 8. 現在のマス(row, col)の訪問履歴を未訪問にする
            memo_[row][col] = false;

            return res;
        }   
    public:
        CrazyBot() 
        {   
            // 1. 各マスの訪問履歴を作成する
            for(size_t i = 0; i < 30; ++i) {
                vector<bool> v(30, false);
                memo_.push_back(v);
            }   
        }   

        double getProbability(int n, int east, int west, int south, int north)
        {   
            // 2. CrazyBotが東西南北の各方角に進む確率を作成する
            probabilities_.push_back( east / 100.0 );
            probabilities_.push_back( west / 100.0 );
            probabilities_.push_back( south / 100.0 );
            probabilities_.push_back( north / 100.0 );

            // 3. 探索を開始する
            return dfs(15, 15, n); 
        }   
};

int main()
{
    int n, east, west, south, north;
    cin >> n >> east >> west >> south >> north;
    cout << showpoint << CrazyBot().getProbability(n, east, west, south, north) << endl;
    return 0;
}

解説

問題文よりCrazyBotの最大歩数は14なので、30行30列のセルを用意し、その中央である15行15列のマスをCrazyBotのスタート地点とすればCrazyBotがセルの外に出てしまう心配はない。
また、手順8は一つ上の階層に戻り別のルートから探索を行う場面で別のルートから探索を行う場合は(row, col)のマスを通行できるので、手順6で訪問済みにした(row, col)のマスの訪問履歴を手順8で未訪問状態に戻す必要がある。

深さ優先探索と幅優先探索の使い分け

深さ優先探索/幅優先探索のどちらを使ってもグラフの全頂点(考えられる全てのケース)を漏れなく探索することができる。しかしどちらか片方を使えれば良いというわけではなく、問題に応じて上手に使い分ける必要がある。使い分ける際のポイントは下記のような観点だろうか。

• 求めたい解に応じて使い分ける

  例題1のような最短経路をもとめる場合は幅優先探索、辞書順で最初の解を求める場合は深さ優先探索を採用するなど。

• ツリー構造の形状に応じて使い分ける

  1つの階層に大量のノードが存在する場合は深さ優先探索、深い階層まで一本道で探索する場合は幅優先探索など。

その他

幅優先探索または深さ優先探索のような探索アルゴリズムを使わない(でも解ける)問題もある。

例題3: 7の数を数える

問題

問題の概要は こちら を参照。

回答例(JavaScript)

count-seven.js

function count(n) {
	var ans = 0,
	value = 0;
	s = (n || '').toString(), // nにundefinedやnullを指定された場合の対処
	digits = s.length,
	values = s.split('').reverse();

	// nに1以上の整数値以外の値を指定された場合は0を返す仕様とした
	if(!s.match(/^[1-9]{1}[0-9]*$/g)) {
		console.log('nには1以上の整数を指定して下さい。');
		return ans;
	}

	while(0 <= --digits) {
		value = values[digits] - 0;
		ans += value * digits * Math.pow(10, digits - 1);
		if(value === 7) {
			ans += (n % Math.pow(10, digits)) + 1;
		} else if(8 <= value) {
			ans += Math.pow(10, digits);
		}
	}

	return ans;
}

// console.log( count(178) ); // => 37を表示

解説

Bさんの回答例のように全探索すれば正解を得ることができるが、ものすごく時間がかかる。
計算量を減らすための方法は何通りかあるのだろうが、私は下記のような一般性があることを利用した。

answer = \sum_{k=1}^d
     \begin{cases}
       v_k \times (k - 1) \times 10^{k - 2} & (v_k < 7) \\
       v_k \times (k - 1) \times 10^{k - 2} + (n \% 10^{k - 1} + 1) & (v_k = 7) \\
       v_k \times (k - 1) \times 10^{k - 2} + 10^{k - 1} & (8 \leq v_k)
     \end{cases}

ここで

• d は入力値 n の桁数を表す
  ex) n = 178 の場合は d = 3 となる

• v_k は 入力値 n の(1の位から数えた) k 番目の値
  ex) n = 178 の場合 v_1, v_2, v_3 はそれぞれ 8, 7, 1 となる

上記式を入力値 n の各位の数に対して適用した結果を合計した値が求めたい解となる。