人工知能に関する断創録

このブログでは人工知能のさまざまな分野について調査したことをまとめています(更新停止: 2019年12月31日)

探索による問題解決

今日は、エージェントアプローチ人工知能第2版の3章「探索による問題解決」を読んでた。

そういえば大学の人工知能の講義では一番はじめに探索やったなぁ。この本にも載ってるけど8クイーンとか15パズルが例に出て探索アルゴリズムの説明とか受けた覚えがある。人工知能ワクワクってときにいきなり探索なんか出てきて、人間の知能と何の関係があるんだろう?全然関係ないじゃんとか思った覚えがある。

この本を読み直してみると知的エージェントの構築という目的には探索は非常に重要な技術だと思い返した。探索はパズルとかチェスとか巡回セールスマン問題とかに使うというイメージが強いけど実はそれだけじゃないってことに気づかされたなぁ。抽象的に考えるとエージェントが目的を達するためにどのような行動の系列を取ればよいかを計算するのが探索技術だ。パズルやゲームはその一部の応用にすぎない。

3章では、幅優先探索深さ優先探索反復深化探索など情報のない探索手法が紹介されている。例題に出てくるルーマニア地図を表したグラフ上でAradからBucharestへの経路を探索するという問題を解くプログラムをPythonで実装してみた。

#coding:utf-8
"""エージェントアプローチ人工知能 3章 探索による問題解決"""

# ルーマニアの道路地図の隣接リスト表現
adjacent = ((1,7),         # Oradea (0)
            (0,2),         # Zerind (1)
            (1,3,7),       # Arad (2)
            (2,4),         # Timisoara (3)
            (3,5),         # Lugoj (4)
            (4,6),         # Mehadia (5)
            (5,9),         # Dobreta (6)
            (0,2,8,10),    # Sibiu (7)
            (7,9,11),      # Rimnicu Vilcea (8)
            (6,8,11),      # Craiova (9)
            (7,12),        # Fagaras (10)
            (8,9,12),      # Pitesti (11)
            (10,11,13,14), # Bucharest (12)
            (12,),         # Giurgiu (13)
            (12,15,18),    # Urziceni (14)
            (14,16),       # Vaslui (15)
            (15,17),       # Iasi (16)
            (16,),         # Neamt (17)
            (14,19),       # Hirsova (18)
            (18,))         # Eforie (19)

def breadth_first_search(start, goal):
    """幅優先探索"""
    queue = [[start]]  # 未探索の経路を格納するキュー
    while len(queue) > 0:
        path = queue.pop(0)  # キューなのでpathを先頭から取得
        cur_pos = path[len(path)-1]  # 現在位置
        if cur_pos == goal:  # 目的地ならパスを表示
            print path
        else:
            # cur_posまでのpathに隣接ノードをつなげたpathをキューに全部追加
            for p in adjacent[cur_pos]:
                if p not in path:  # 繰り返し状態の回避
                    new_path = path[:]
                    new_path.append(p)
                    queue.append(new_path)

def depth_first_search(goal, path):
    """深さ優先探索(バックトラック探索)"""
    cur_pos = path[len(path)-1]
    if cur_pos == goal:
        print path
    else:
        for p in adjacent[cur_pos]:
            if p not in path:
                path.append(p)
                depth_first_search(goal, path)  # 再帰で深さ優先
                path.pop()  # バックトラック

def iterative_deepening_search(limit, goal, path):
    """反復深化探索"""
    depth = len(path)
    cur_pos = path[depth-1]
    if depth == limit:  # 深さがlimitに達したら探索終了
        if cur_pos == goal:
            print path
    else:
        # 深さ優先探索
        for p in adjacent[cur_pos]:
            if p not in path:
                path.append(p)
                iterative_deepening_search(limit, goal, path)
                path.pop()

def main():
    print "■幅優先探索"
    breadth_first_search(2, 12)  # AradからBucharestへのパスを幅優先で探索
    print "■深さ優先探索"
    depth_first_search(12, [2])  # AradからBucharestへのパスを深さ優先で探索
    print "■反復深化探索"
    for limit in range(1, 12):
        print "limit:", limit
        iterative_deepening_search(limit, 12, [2])

if __name__ == "__main__":
    main()

実行結果は下の通り。AradからBucharestへ行くには、2 (Arad) → 7 (Sibiu) → 10 (Fagaras) → 12 (Bucharest) が最短経路だとわかる。

■幅優先探索
[2, 7, 10, 12]
[2, 7, 8, 11, 12]
[2, 1, 0, 7, 10, 12]
[2, 7, 8, 9, 11, 12]
[2, 1, 0, 7, 8, 11, 12]
[2, 1, 0, 7, 8, 9, 11, 12]
[2, 3, 4, 5, 6, 9, 11, 12]
[2, 3, 4, 5, 6, 9, 8, 11, 12]
[2, 3, 4, 5, 6, 9, 8, 7, 10, 12]
[2, 3, 4, 5, 6, 9, 11, 8, 7, 10, 12]

■深さ優先探索
[2, 1, 0, 7, 8, 9, 11, 12]
[2, 1, 0, 7, 8, 11, 12]
[2, 1, 0, 7, 10, 12]
[2, 3, 4, 5, 6, 9, 8, 7, 10, 12]
[2, 3, 4, 5, 6, 9, 8, 11, 12]
[2, 3, 4, 5, 6, 9, 11, 8, 7, 10, 12]
[2, 3, 4, 5, 6, 9, 11, 12]
[2, 7, 8, 9, 11, 12]
[2, 7, 8, 11, 12]
[2, 7, 10, 12]

■反復深化探索
limit: 1
limit: 2
limit: 3
limit: 4
[2, 7, 10, 12]
limit: 5
[2, 7, 8, 11, 12]
limit: 6
[2, 1, 0, 7, 10, 12]
[2, 7, 8, 9, 11, 12]
limit: 7
[2, 1, 0, 7, 8, 11, 12]
limit: 8
[2, 1, 0, 7, 8, 9, 11, 12]
[2, 3, 4, 5, 6, 9, 11, 12]
limit: 9
[2, 3, 4, 5, 6, 9, 8, 11, 12]
limit: 10
[2, 3, 4, 5, 6, 9, 8, 7, 10, 12]
limit: 11
[2, 3, 4, 5, 6, 9, 11, 8, 7, 10, 12]

幅優先探索は、一番はじめに見つかるのが最適解(最短経路)になるが、分岐度が大きいと大量にメモリを消費してしまう。一方、深さ優先探索は、メモリ消費はほとんどないが、はじめに最適解が見つかるとは限らないし、下手すると深みにはまって解が見つからない場合もありえる。幅優先探索と深さ優先探索のいいとこどりしたのが反復深化探索で探索を打ち切る深さをだんだん深くして深さ優先探索を繰り返し行う。はじめに最適解が見つかるし、メモリもほとんど使わないが、何回も繰り返すので計算時間はかかる。

8クイーンと15パズルもちょっと解いてみたい。次の4章ではゲームプログラミングでもよく使うヒューリスティック探索法(A*探索)を勉強するぞ。

関連リンク

  • Algorithms with Python - 集合、グラフ、経路の探索を参考にした。このサイトすごい。いろんなデータ構造やアルゴリズムをPythonで実装してる!