#Pythonで学ぶアルゴリズム< 木構造 >

はじめに

基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第11弾として木構造を扱う．

木構造

幅優先探索

・階層ごとに見ていくような感じ
・何か1つだけ合致するものを見つける場合に高速に処理できる
・探索途中のノードをすべて保持　⇒　メモリを大きく消費してしまう

深さ優先探索

・限界まで進んで，また戻ってくる方法（バックトラックともいう）
・すべての（ある程度の深さまでの）答えを見つけるときによく使われる
・再帰処理を使うことが多い
・3種の異なるルートがある（行きがけ・帰りがけ・通りがけ）

木構造の処理ルート

幅優先探索

おおまかなイメージ図を次に示す．

実際に処理順を各ノードに記したものを次に示す．

幅優先ははじめに書いたとおり，階層ごとに処理している．

深さ優先探索

おおまかなイメージ図を次に示す．

3種のルートすべては上記のおおまかなイメージに従うが，ノードを処理するタイミングによりそれらは分類される．

①行きがけ順

各ノードの子をたどる前にそのノードを処理

②帰りがけ順

各ノードの子をすべてたどった後でそのノードを処理

③通りがけ順

2分木の左側の子ノードをたどった後に処理し，右側の子のノードをたどる．

実装

pythonに実装するが，ここでは簡易のため，リストで木構造を表現することとする．その対応付けは次の通りである．

以下では，幅優先探索，深さ優先探索について簡単な実装サンプルコードとそのときの出力を示す．

コード（幅優先探索）

breadth_search.py

"""
2020/12/29
@Yuya Shimizu

幅優先探索
"""

tree = [[1,2], [3,4], [5,6], [7,8], [9,10], [11,12],
            [13,14], [], [], [], [], [], [], [], []]

data = [0]
while len(data) > 0:
    pos = data.pop(0) #pop: dataから0を取り出す（dataからは0が要素が消える）
    print(pos, end = ' ')
    for i in tree[pos]:
        data.append(i)

出力

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

上記の図と照らし合わせると，幅優先探索の順で処理されていることが分かる．

コード（深さ優先探索：行きがけ順）

depth_search1.py

"""
2020/12/29
@Yuya Shimizu

深さ優先探索１：行きがけ順
"""

tree = [[1,2], [3,4], [5,6], [7,8], [9,10], [11,12],
            [13,14], [], [], [], [], [], [], [], []]


def search(pos):
    print(pos, end = ' ')      #配下のノードを調べる前に出力
    for i in tree[pos]:        #配下のノードを調べる
        search(i)       #再帰的に探索

search(0)

出力

0 1 3 7 8 4 9 10 2 5 11 12 6 13 14

上記の図と照らし合わせると，深さ優先探索行きがけ順で処理されていることが分かる．

コード（深さ優先探索：帰りがけ順）

depth_search2.py

"""
2020/12/29
@Yuya Shimizu

深さ優先探索２：帰りがけ順
"""

tree = [[1,2], [3,4], [5,6], [7,8], [9,10], [11,12],
            [13,14], [], [], [], [], [], [], [], []]


def search(pos):
    for i in tree[pos]:        #配下のノードを調べる
        search(i)              #再帰的に探索
    print(pos, end = ' ')      #配下のノードを調べた後に出力

search(0)

出力

7 8 3 9 10 4 1 11 12 5 13 14 6 2 0

上記の図と照らし合わせると，深さ優先探索帰りがけ順で処理されていることが分かる．

コード（深さ優先探索：通りがけ順）

depth_search3.py

"""
2020/12/29
@Yuya Shimizu

深さ優先探索３：通りがけ順
"""

tree = [[1,2], [3,4], [5,6], [7,8], [9,10], [11,12],
            [13,14], [], [], [], [], [], [], [], []]


def search(pos):
    if len(tree[pos]) == 2:       #子が２つあるとき
        search(tree[pos][0])
        print(pos, end = ' ')       #左のノードと右のノードの間に出力
        search(tree[pos][1])
    elif len(tree[pos]) == 1:    #子が１つのとき
        search(tree[pos][0])
        print(pos, end = ' ')       #左のノードを調べた後に出力
    else:                               #配下のノードがないとき
        print(pos, end = ' ')

search(0)

出力

7 3 8 1 9 4 10 0 11 5 12 2 13 6 14

上記の図と照らし合わせると，深さ優先探索通りがけ順で処理されていることが分かる．

感想

今回，コードの中でpop()の使い方を知れたことはよかった．また，木構造について，特に深さ優先探索の中にもタイミングにより３つの異なる探索ルートがあることを知れた．ここでは，サンプルプログラムを動かしアルゴリズムの動作のみ確認したが，ロボットの意志決定のときにも使われることもあると学んだため，今後それも実装できたらと思う．

参考文献

Pythonで始めるアルゴリズム入門　伝統的なアルゴリズムで学ぶ定石と計算量
　　　　　　　　　　　　　　　　　　　　　　　　増井敏克　著　　翔泳社