探索アルゴリズム・幅優先探索と深さ優先探索

Image from Gyazo

ノートブックの作成

Jupyter Notebook を起動し,新規にノートブックを作成してください. ノートブックのタイトルは AI-6 とします. ノートブックの作成方法は第1回の資料を参照してください.

迷路問題

今回は 迷路問題 を独自に設計します.

迷路問題

初期状態$A$から目的状態$Y$に至るまでの最短経路とコスト(距離)を求めよ. ただし,隣り合う状態への移動にかかるコストは$1$とする. Image from Gyazo

この問題を 状態空間モデル で表現します.

状態空間モデル

$A$から$Y$までの25の状態から,冗長な状態を取り除く. 例えば,$A \rightarrow B \rightarrow C \rightarrow D \rightarrow E$という経路においては,$B$,$C$,$D$に分岐は存在せず,通り抜けることしかしないため,これらの状態を省略する. この結果,$S1$から$S17$までの,17通りの状態で問題を表現する. Image from Gyazo 行動は移動可能な状態のペアとして定義する. 例えば,$S1$からは,$S2$と$S7$に移動可能なため, 下記のように表現できる.

  • $S1 \rightarrow S2$
  • $S1 \rightarrow S7$
同様に全ての状態について列挙すると, 合わせて31通りの行動が定義できる.

探索アルゴリズム

探索木を用いて初期状態から目的状態を探索するための アルゴリズム(探索する手順) について紹介します. ここでは,ヒューリスティックスと呼ばれる知識を用いないで探索する 幅優先探索深さ優先探索 を取り上げます. これまでに取り上げた,水差し問題,8パズル,ハノイの塔では, 実は幅優先探索を用いていました.

幅優先探索は,探索木の同じ深さの状態を探索してから, 次の深さの状態を探索する手法のことです. ここで,深さ とは初期状態からのコスト(ステップ数)を意味しています. 例えば,上記の迷路問題では,初期状態$S1$から 1ステップで到達可能な$S2$と$S3$を探索します. その次に,2ステップで到達可能な$S6$,$S8$,$S14$を探索します. これを目的状態$S17$に到達するまで繰り返します.

Image from Gyazo

深さ優先探索は,探索木の末端まで探索して目的状態を発見できなければ, 一つ前の分岐まで後戻りして探索する手法のことです. 例えば,上記の迷路問題では,初期状態$S1$から,$S2$,$S6$へと進み, 目的状態が発見できなかったため,$S1$まで戻り,$S7$,$S8$へと探索を進めます. これを目的状態$S17$に到達するまで繰り返します.

Image from Gyazo

実装

最初にライブラリをインポートします. 探索問題の型 を表すSearchPrblem幅優先探索 を表すbreadth_first,そして, 深さ優先探索 を表すdepth_firstをインポートします.

from simpleai.search import SearchProblem, breadth_first, depth_first

次に 初期状態目的状態 を定義します. 初期状態は$1$,目的状態は$17$です.

START = 1
GOAL  = 17

インポートしたSearchProblemクラスをオーバライドして, 迷路問題を表すMazeProblemを定義します. オーバライドするメソッドは,actionsresultis_goalの3種類です.

class MazeProblem(SearchProblem):

    def actions(self, state):
        ...
        
    def result(self, state, action):
        ...
        
    def is_goal(self, state):
        ...

actions(self, state)

実行可能な行動のリストを返します. 行動は全部で31パターンが存在します.

def actions(self, state):
    list = []
    
    if state == 1: #S1からS2,S7に到達可能
        list = [2, 7]
    if state == 2: #S2からS1,S6に到達可能
        list = [1, 6]
    if state == 3: #S3からS4に到達可能
        list = [4]
    if state == 4: #S4からS3,S5,S8に到達可能
        list = [3, 5, 8]
    if state == 5: #S5からS4に到達可能
        list = [4]
    if state == 6: #S6からS2に到達可能
        list = [2]
    if state == 7: #S7からS1,S8,S14に到達可能
        list = [1, 8, 14]
    if state == 8: #S8からS4,S7,S12に到達可能
        list = [4, 7, 12]
    if state == 9: #S9からS10,S13に到達可能
        list = [10, 13]
    if state == 10: #S10からS9,S17に到達可能
        list = [9, 17]
    if state == 11: #S11からS12に到達可能
        list = [12]
    if state == 12: #S12からS8,S11,S13に到達可能
        list = [8, 11, 13]
    if state == 13: #S13からS9,S12に到達可能
        list = [9, 12]
    if state == 14: #S14からS7,S15に到達可能
        list = [7, 15]
    if state == 15: #S15からS4に到達可能
        list = [14]
    if state == 16: #S16からS17に到達可能
        list = [17]
    if state == 17: #S17からS10,S16に到達可能
        list = [10, 16]

    print("{} -> {}".format(state, list))

    return list

result(self, state, action)

行動actionを,そのまま次の状態として扱います.

def result(self, state, action):
    return action

is_goal(self, state)

状態stateGOALと一致すれば目的状態に達したと判断します.

def is_goal(self, state):
    return state == GOAL

解の探索

幅優先探索

まずは,幅優先探索breadth_firstを用いて探索します. 探索順番は$S1,S2,S7,\cdots,S9,S10$となっていることがわかります.

problem = MazeProblem(initial_state=START)
result = breadth_first(problem, graph_search=True)
1 -> [2, 7]
2 -> [1, 6]
7 -> [1, 8, 14]
6 -> [2]
8 -> [4, 12]
14 -> [7, 15]
4 -> [3, 5, 8]
12 -> [8, 11, 13]
15 -> [14]
3 -> [4]
5 -> [4]
11 -> [12]
13 -> [9, 12]
9 -> [10, 13]
10 -> [9, 17]

最終状態,パス,コストを確認してみましょう. 初期状態$S1$から目的状態$S17$までのパスは, $S1, S7, S8, S12, S13, S9, S10, S17$であり, そのコスト(ステップ数)は$7$となっています.

print(result.state)
print(result.path())
print(result.cost)
17
[(None, 1), (7, 7), (8, 8), (12, 12), (13, 13), (9, 9), (10, 10), (17, 17)]
7

深さ優先探索

次は,深さ先探索depth_firstを用いて探索します. ここでは,探索順番を揃えるため,行動のリストlistの順番をreverse関数で反転しておきます(深さ優先探索では番号の大きい状態を優先するため).

list.reverse() #リストの順番を反転
        
return list

探索順番は$S1,S2,S6,\cdots,S9,S10$となっていることがわかります.

problem = MazeProblem(initial_state=START)
result = depth_first(problem, graph_search=True)
1 -> [2, 7]
2 -> [1, 6]
6 -> [2]
7 -> [1, 8, 14]
8 -> [4, 12]
4 -> [3, 5, 8]
3 -> [4]
5 -> [4]
12 -> [8, 11, 13]
11 -> [12]
13 -> [9, 12]
9 -> [10, 13]
10 -> [9, 17]

最終状態,パス,コストを確認してみましょう. 初期状態$S1$から目的状態$S17$までのパスは, $S1, S7, S8, S12, S13, S9, S10, S17$であり, そのコスト(ステップ数)は$7$となっています. これは幅優先探索と同じ結果です.

print(result.state)
print(result.path())
print(result.cost)
17
[(None, 1), (7, 7), (8, 8), (12, 12), (13, 13), (9, 9), (10, 10), (17, 17)]
7

参考書籍