Kuratani Shigeru Weblog

***
2019年6月9日

探索問題を解いてみた

はじめに

通勤時間の隙間の時間を利用して、「人口知能」に関する書籍を読んでいます。
人口知能の教科書の最初に紹介がされることが多い、「探索」に関して以下の問題を解いてみました。

問題

3×3の9コマのマスがあるパズルの「スタート状態」から「ゴール状態」を探索木を作成しながら探索をする

今回はC言語を使用して問題を解いてみました。
「問題(課題)をコンピュータに解かせる」という作業は、とても楽しく知的な作業だと思います。楽しく取り組むことが出来たので記録しておこうと思います。

今回のお題

今回のお題は以下の「スタート状態」から「ゴール状態」までを、横型探索を実行して探索をしてみました。
横型探索のアルゴリズムは以下になります。

横型探索アルゴリズム

初期化 クローズリスト(CL)を空にし、オープンリスト(OL)に初期状態だけを追加する。
ステップ1 OLが空ならは終了(解なし)
ステップ2 OLから先頭要素をXを取り出し、ゴール状態かを判定、ゴールなら終了(解が発見された)。ゴールでないならXをCLに追加する。
ステップ3 Xで適用可能なオペレータをすべて適用してできる状態全体V(X)を作成する。Xで適用するオペレータがないならステップ1に戻る。
ステップ4 V(X)の要素全部をOLの末尾に追加する。親子ポインタリストにXをそれらの親として登録する。※CLとOLに存在しない状態要素のみを追加する必要がありますが、簡単の為に今回の実装では見送ります
ステップ5 ステップ1に戻る。

スタート状態

364
1 2
875

ゴール状態

123
8 4
765

上記パズルでは、空いたマスに移動可能な数字を移動させながら、ゴール状態を探索します。
実装したプログラムの実行結果は以下になります。

実行結果

CW-01:chap02 XXX$ clang -o tansaku_h tansaku_h.c
CW-01:chap02 XXX$ ./tansaku_h 
ゴールを探索出来ました
--------
 3 6 4
 1    2
 8 7 5
--------
 3    4
 1 6 2
 8 7 5
--------
    3 4
 1 6 2
 8 7 5
--------
 1 3 4
    6 2
 8 7 5
--------
 1 3 4
 8 6 2
    7 5
--------
 1 3 4
 8 6 2
 7    5
--------
 1 3 4
 8    2
 7 6 5
--------
 1 3 4
 8 2  
 7 6 5
--------
 1 3  
 8 2 4
 7 6 5
--------
 1    3
 8 2 4
 7 6 5
--------
 1 2 3
 8    4
 7 6 5
--------

実装をしてみて

現在のシステム開発のお仕事をさせて頂くようになってから、「目の前の問題(作業)を早く完了する」というのを優先にしてきました。
今回のように、個人で取り組む学習分野を、じっくりとやってみるというのはとても楽しかったです。理解も進みましたし。
これまでもプライベートでの学習が、実務に活かせた経験は沢山ありましたので、興味のある分野をのんびりと学習していきたいです。
あと、これまで「開発者として必要だ」と感じるものは時間が許す限り学習をしてきました。コンピュータサイエンスの基礎も同様です。
しかし、コンピュータサイエンスに関する分野は多岐に渡ります。数年前から「自分には全部やるのは無理!」となっていまして...
これからは、興味のある分野、目標とする職域に必要な分野に範囲を絞って、じっくりと腰を据えて学習をしていこうと思っています。

今回の探索問題に戻ります。
お題として設定した「スタート状態」から「ゴール状態」までは、9ステップで探索が可能なものを選択しています。
上記探索でも、約28000の状態空間を探索します。
試しに任意のスタート状態を設定して、探索を実行してみましたが、私のMacBook Airでは、約100000以上の探索空間を探索して、30分を経過しても解を見つけることが出来ませんでした。 (処理の途中でキャンセルしました)

今回の実装のように力ずくで全探索空間を探索する方法では、実用的な探索を実現することは難しいのだと感じました。実世界の問題は、今回のような9コマのパズル問題よりもっと複雑です。
「最良優先探索」などの手法を取り入れて、探索を必要があると思います。
今後の課題としたいです。

以前、100000個のランダムな数字をバブルソートしてみたことがあるのですが、私のマシンで約10分必要でした。これをクイックソートで実行すると一瞬で処理を完了することが出来ました。 その時、アルゴリズムによって実用的な処理となるかどうかが決まるのだと感じましたが、今回の探索でもアルゴリズムの重要性を再確認出来ました。

追記

「横型探索アルゴリズム」の「ステップ4」で、「CLとOLに存在しない状態要素のみを追加する」処理を追加すれば、常識的な時間で9コマパズル問題は解を出すことが出来ます。 こういった細かな処理が処理量に大きく影響します。

この記事の最後に、今回C言語で実装した「横型探索プログラム」を掲載しますので、Java・C#・Python・PHPなど皆さんのお好みの言語で実装をして、実行してみてください。とても興味深いですよ!

横型探索プログラム(tansaku_h.c)

/***********************************************/
/* パズル問題探索(横型探索)                       */
/***********************************************/
// マクロ定義
#define MAX_LIST_SIZE 16777216
#define CELL_SIZE 9

// ヘッダ
#include <stdio.h>
#include <stdlib.h>

// 構造体定義
struct puzzle_state
{
    int id;               // 状態ID
    int parent_id;        // 親状態ID
    int state[CELL_SIZE]; // 状態
};
typedef struct puzzle_state State; 

// プロトタイプ宣言
void execute_search(State start, State goal);
void set_result_list(State start, State goal);
State search_state(int state_id);
void set_next_state(State cur_state);
int isGoal(State goal, State cur_state);
void print_result_list();
void print_state(State puzzle_state);
void next_state_0(State puzzle_state);
void next_state_1(State puzzle_state);
void next_state_2(State puzzle_state);
void next_state_3(State puzzle_state);
void next_state_4(State puzzle_state);
void next_state_5(State puzzle_state);
void next_state_6(State puzzle_state);
void next_state_7(State puzzle_state);
void next_state_8(State puzzle_state);
void swapdata(int *i, int *j);
void shift_ol(State data);
State unshift_ol(void);
void push_ol(State data);
State pop_ol(void);
void push_cl(State data);
State pop_cl(void);

// グローバル変数
State open_list[MAX_LIST_SIZE];
State close_list[MAX_LIST_SIZE];
State result_list[MAX_LIST_SIZE];
int stack_pointer_ol = 0;
int stack_pointer_cl = 0;
int status_id = 0;
int result_cnt = 0;

/******************************/
/* MAIN関数                    */
/******************************/
int main(int argc, char const *argv[])
{
    // スタート状態
    State start = {
        0 ,
        0 ,
        {3, 6, 4, 1, ' ', 2, 8, 7, 5}
    };

    // ゴール状態
    State goal = {
        0 ,
        0 ,
        {1, 2, 3, 8, ' ', 4, 7, 6, 5}
    };

    // 探索処理
    execute_search(start, goal);

    return 0;
}

/******************************/
/* 探索処理                     */
/******************************/
void execute_search(State start, State goal)
{
    // オープンリストに初期状態をセット
    push_ol(start);

    // 探索開始
    while (1) {

        // オープンリストが空なら処理終了
        if (stack_pointer_ol <= 0) {
            fprintf(stderr, "ゴールが見つかりませんでした\n");
            break;
        }

        // オープンリストから状態を取り出し
        State cur_state = unshift_ol();
        // ゴール判定
        if (isGoal(goal, cur_state)) {
            printf("ゴールを探索出来ました\n");
            set_result_list(start, cur_state);
            print_result_list();
            break;
        }

        // 現在の状態をクローズリストに追加
        push_cl(cur_state);
        // 次の状態をオープンリストに追加
        set_next_state(cur_state);
    }   
}

/***************************************************/
/* ゴール状態に紐付く状態を、クローズリストから状態を検索    */
/* 探索状態リストに状態を追加                           */
/***************************************************/
void set_result_list(State start, State goal)
{
    // ゴール状態を結果リストにセット
    result_list[result_cnt++] = goal;

    int parent_id = goal.parent_id;
    while (1) {
        // 親IDから状態を検索
        State parent_state = search_state(parent_id);
        // 結果リストに追加
        result_list[result_cnt++] = parent_state;
        // スタート状態なら検索終了
        if (parent_state.parent_id == 0) break;
        // 親状態IDをセット
        parent_id = parent_state.parent_id;
    }

    // スタート状態を結果リストにセット
    result_list[result_cnt++] = start;
}

/******************************/
/* クローズリストから状態を検索    */
/******************************/
State search_state(int state_id)
{
    for (int i = 0; i < MAX_LIST_SIZE; i++) {
        if (close_list[i].id == state_id) {
            return close_list[i];
        }
    }
    State null_state = {
        0 ,
        0 ,
        {0, 0, 0, 0, 0, 0, 0, 0, 0}
    };
    return null_state;
}

/******************************/
/* 次の状態を探索                */
/******************************/
void set_next_state(State cur_state)
{
    for (int i = 0; i < CELL_SIZE; ++i) {
        if (i == 0 && cur_state.state[i] == ' ') {
            next_state_0(cur_state);
        } else if (i == 1 && cur_state.state[i] == ' ') {
            next_state_1(cur_state);
        } else if (i == 2 && cur_state.state[i] == ' ') {
            next_state_2(cur_state);
        } else if (i == 3 && cur_state.state[i] == ' ') {
            next_state_3(cur_state);
        } else if (i == 4 && cur_state.state[i] == ' ') {
            next_state_4(cur_state);
        } else if (i == 5 && cur_state.state[i] == ' ') {
            next_state_5(cur_state);
        } else if (i == 6 && cur_state.state[i] == ' ') {
            next_state_6(cur_state);
        } else if (i == 7 && cur_state.state[i] == ' ') {
            next_state_7(cur_state);
        } else if (i == 8 && cur_state.state[i] == ' ') {
            next_state_8(cur_state);
        }
    }
}

/******************************/
/* ゴール判定                   */
/*   0 : ゴールない             */
/*   1 : ゴールである            */
/******************************/
int isGoal(State goal, State cur_state)
{
    for (int i = 0; i < CELL_SIZE; ++i) {
        if (goal.state[i] != cur_state.state[i]) {
            return 0;
        }
    }

    return 1;
}

/******************************/
/* 探索結果リストを表示           */
/******************************/
void print_result_list()
{
    printf("--------\n");
    for (int i = result_cnt - 1; 0 <= i; i--) {
        print_state(result_list[i]);
    }
}

/******************************/
/* 状態表示                     */
/******************************/
void print_state(State puzzle_state)
{
    for (int i = 0; i < CELL_SIZE; i++) {
        if (puzzle_state.state[i] != ' ') {
            printf(" %d", puzzle_state.state[i]);
        } else {
            printf("%s", "  ");
        }
        if (i % 3 == 2) printf("\n");
    }
    printf("--------\n");
}

/******************************/
/* 位置0の場合の次の状態          */
/*  次の状態をOLに追加する        */
/******************************/
void next_state_0(State puzzle_state)
{
    State ns1 = puzzle_state;
    swapdata(&ns1.state[0], &ns1.state[1]);
    ns1.id = ++status_id;
    ns1.parent_id = puzzle_state.id;
    push_ol(ns1);

    State ns2 = puzzle_state;
    swapdata(&ns2.state[0], &ns2.state[3]);
    ns2.id = ++status_id;
    ns2.parent_id = puzzle_state.id;
    push_ol(ns2);
}

/******************************/
/* 位置1の場合の次の状態          */
/*  次の状態をOLに追加する        */
/******************************/
void next_state_1(State puzzle_state)
{
    State ns1 = puzzle_state;
    swapdata(&ns1.state[1], &ns1.state[0]);
    ns1.id = ++status_id;
    ns1.parent_id = puzzle_state.id;
    push_ol(ns1);

    State ns2 = puzzle_state;
    swapdata(&ns2.state[1], &ns2.state[2]);
    ns2.id = ++status_id;
    ns2.parent_id = puzzle_state.id;
    push_ol(ns2);

    State ns3 = puzzle_state;
    swapdata(&ns3.state[1], &ns3.state[4]);
    ns3.id = ++status_id;
    ns3.parent_id = puzzle_state.id;
    push_ol(ns3);   
}

/******************************/
/* 位置2の場合の次の状態          */
/*  次の状態をOLに追加する        */
/******************************/
void next_state_2(State puzzle_state)
{
    State ns1 = puzzle_state;
    swapdata(&ns1.state[2], &ns1.state[1]);
    ns1.id = ++status_id;
    ns1.parent_id = puzzle_state.id;
    push_ol(ns1);

    State ns2 = puzzle_state;
    swapdata(&ns2.state[2], &ns2.state[5]);
    ns2.id = ++status_id;
    ns2.parent_id = puzzle_state.id;
    push_ol(ns2);

}

/******************************/
/* 位置3の場合の次の状態          */
/*  次の状態をOLに追加する        */
/******************************/
void next_state_3(State puzzle_state)
{
    State ns1 = puzzle_state;
    swapdata(&ns1.state[3], &ns1.state[0]);
    ns1.id = ++status_id;
    ns1.parent_id = puzzle_state.id;
    push_ol(ns1);

    State ns2 = puzzle_state;
    swapdata(&ns2.state[3], &ns2.state[4]);
    ns2.id = ++status_id;
    ns2.parent_id = puzzle_state.id;
    push_ol(ns2);

    State ns3 = puzzle_state;
    swapdata(&ns3.state[3], &ns3.state[6]);
    ns3.id = ++status_id;
    ns3.parent_id = puzzle_state.id;
    push_ol(ns3);   
}

/******************************/
/* 位置4の場合の次の状態          */
/*  次の状態をOLに追加する        */
/******************************/
void next_state_4(State puzzle_state)
{
    State ns1 = puzzle_state;
    swapdata(&ns1.state[4], &ns1.state[1]);
    ns1.id = ++status_id;
    ns1.parent_id = puzzle_state.id;
    push_ol(ns1);

    State ns2 = puzzle_state;
    swapdata(&ns2.state[4], &ns2.state[3]);
    ns2.id = ++status_id;
    ns2.parent_id = puzzle_state.id;
    push_ol(ns2);

    State ns3 = puzzle_state;
    swapdata(&ns3.state[4], &ns3.state[5]);
    ns3.id = ++status_id;
    ns3.parent_id = puzzle_state.id;
    push_ol(ns3);

    State ns4 = puzzle_state;
    swapdata(&ns4.state[4], &ns4.state[7]);
    ns4.id = ++status_id;
    ns4.parent_id = puzzle_state.id;
    push_ol(ns4);   
}

/******************************/
/* 位置5の場合の次の状態          */
/*  次の状態をOLに追加する        */
/******************************/
void next_state_5(State puzzle_state)
{
    State ns1 = puzzle_state;
    swapdata(&ns1.state[5], &ns1.state[2]);
    ns1.id = ++status_id;
    ns1.parent_id = puzzle_state.id;
    push_ol(ns1);

    State ns2 = puzzle_state;
    swapdata(&ns2.state[5], &ns2.state[4]);
    ns2.id = ++status_id;
    ns2.parent_id = puzzle_state.id;
    push_ol(ns2);

    State ns3 = puzzle_state;
    swapdata(&ns3.state[5], &ns3.state[8]);
    ns3.id = ++status_id;
    ns3.parent_id = puzzle_state.id;
    push_ol(ns3);   
}

/******************************/
/* 位置6の場合の次の状態          */
/*  次の状態をOLに追加する        */
/******************************/
void next_state_6(State puzzle_state)
{
    State ns1 = puzzle_state;
    swapdata(&ns1.state[6], &ns1.state[3]);
    ns1.id = ++status_id;
    ns1.parent_id = puzzle_state.id;
    push_ol(ns1);

    State ns2 = puzzle_state;
    swapdata(&ns2.state[6], &ns2.state[7]);
    ns2.id = ++status_id;
    ns2.parent_id = puzzle_state.id;
    push_ol(ns2);
}
/******************************/
/* 位置7の場合の次の状態          */
/*  次の状態をOLに追加する        */
/******************************/
void next_state_7(State puzzle_state)
{
    State ns1 = puzzle_state;
    swapdata(&ns1.state[7], &ns1.state[4]);
    ns1.id = ++status_id;
    ns1.parent_id = puzzle_state.id;
    push_ol(ns1);

    State ns2 = puzzle_state;
    swapdata(&ns2.state[7], &ns2.state[6]);
    ns2.id = ++status_id;
    ns2.parent_id = puzzle_state.id;
    push_ol(ns2);

    State ns3 = puzzle_state;
    swapdata(&ns3.state[7], &ns3.state[8]);
    ns3.id = ++status_id;
    ns3.parent_id = puzzle_state.id;
    push_ol(ns3);   
}

/******************************/
/* 位置8の場合の次の状態          */
/*  次の状態をOLに追加する        */
/******************************/
void next_state_8(State puzzle_state)
{
    State ns1 = puzzle_state;
    swapdata(&ns1.state[8], &ns1.state[5]);
    ns1.id = ++status_id;
    ns1.parent_id = puzzle_state.id;
    push_ol(ns1);

    State ns2 = puzzle_state;
    swapdata(&ns2.state[8], &ns2.state[7]);
    ns2.id = ++status_id;
    ns2.parent_id = puzzle_state.id;
    push_ol(ns2);
}

/******************************/
/* swapdata関数                */
/******************************/
void swapdata(int *i, int *j)
{
    int temp;

    temp = *i;
    *i = *j;
    *j = temp;
}

/******************************/
/* SHIFT関数(OL)              */
/******************************/
void shift_ol(State data)
{
    if (stack_pointer_ol > MAX_LIST_SIZE - 1) {
        fprintf(stderr, "エラー オープンリストが一杯です\n");
        exit(1);
    }
    int max_point = stack_pointer_ol;
    for (int i = max_point - 1; 0 <= i; i--) {
        open_list[i + 1] = open_list[i];
    }
    open_list[0] = data;
    stack_pointer_ol++;
}

/******************************/
/* UNSHIFT関数(OL)            */
/******************************/
State unshift_ol(void)
{
    if (stack_pointer_ol <= 0) {
        fprintf(stderr, "エラー オープンリストにデータがありません\n");
        exit(1);
    }
    State ret_state = open_list[0];
    int max_point = stack_pointer_ol;
    for (int i = 0; i < max_point - 1; i++) {
        open_list[i] = open_list[i + 1];
    }
    stack_pointer_ol--;
    return ret_state;
}

/******************************/
/* PUSH関数(OL)               */
/******************************/
void push_ol(State data)
{
    if (stack_pointer_ol >= MAX_LIST_SIZE - 1) {
        fprintf(stderr, "エラー オープンリストが一杯です\n");
        exit(1);
    }
    open_list[stack_pointer_ol++] = data;
}

/******************************/
/* POP関数(OL)                */
/******************************/
State pop_ol(void)
{
    if (stack_pointer_ol <= 0) {
        fprintf(stderr, "エラー オープンリストにデータがありません\n");
        exit(1);
    }
    return open_list[--stack_pointer_ol];
}

/******************************/
/* PUSH関数(CL)               */
/******************************/
void push_cl(State data)
{
    if (stack_pointer_cl >= MAX_LIST_SIZE - 1) {
        fprintf(stderr, "エラー クローズリストが一杯です\n");
        exit(1);
    }
    close_list[stack_pointer_cl++] = data;
}

/******************************/
/* POP関数(CL)                */
/******************************/
State pop_cl(void)
{
    if (stack_pointer_cl <= 0) {
        fprintf(stderr, "エラー クローズリストにデータがありません\n");
        exit(1);
    }
    return close_list[--stack_pointer_cl];
}