pythonによる経路探索 ( 深さ優先 or 幅優先 )

経路探索は、過去1),2)で何度か書いた(写経)ことがありますが、改めて? 上記3)を pythonにて写経し、少々、修正。

#!/usr/local/python3/bin/python3
# -*- coding: utf-8 -*-

# http://www.nct9.ne.jp/m_hiroi/light/pyalgo05.html
#       B(1)──D(3)──F(5)
#     ／ │     │      │
#  A(0)  │     │      │
#     ＼ │     │      │
#       C(2)──E(4)──G(6)
adjacent = ((1, 2),    # A
            (0, 2, 3), # B
            (0, 1, 4), # C
            (1, 4, 5), # D
            (2, 3, 6), # E
            (3,),      # F
            (1,))      # G

def main():
    print("#### 深さ優先探索 ####")
    search(6, [0])

    print("#### 幅優先探索 ####")
    bf_search(0, 6)


# 深さ優先探索 (最初に見つかる経路が最短経路とは限らない)
def search(goal, path):
    n = path[len(path) - 1]
    
    if n == goal:
        print("GOAL REACHED!", path )
        return path

    for x in adjacent[n]:
        # 既に通過した経路に設定xが含まれない場合
        # これを追加(path+[x])し、再帰探索
        if x not in path:
            search(goal, path+[x] )
    return None


# 幅優先探索
def bf_search(start, goal):
    q = [[start]]  # 「q」には探索中の経路が複数含まれます
    while len(q) > 0:
        # dequeu
        path = q.pop(0)
        n = path[len(path) - 1]
        if n == goal:
            print("GOAL REACHED!", path )
        else:
            for x in adjacent[n]:
                if x not in path:
                    q.append( path+[x])


if __name__ == '__main__':
    main()

↑こう書くと、↓こう表示されます

C:\home\end0tknr\tmp\PYTHON>python foo.py
#### 深さ優先探索 ####
GOAL REACHED! [0, 1, 2, 4, 6]
GOAL REACHED! [0, 1, 3, 4, 6]
GOAL REACHED! [0, 2, 1, 3, 4, 6]
GOAL REACHED! [0, 2, 4, 6]
#### 幅優先探索 ####
GOAL REACHED! [0, 2, 4, 6]
GOAL REACHED! [0, 1, 2, 4, 6]
GOAL REACHED! [0, 1, 3, 4, 6]
GOAL REACHED! [0, 2, 1, 3, 4, 6]

end0tknr's kipple - web写経開発

太宰府天満宮の狛犬って、妙にカワイイ