『Javaによる知能プログラミング入門』の「2.探索とパターン照合」にある幅優先探索のソースコードをPythonで実装してみました。
有向グラフとして表現されている状態空間の、初期状態から目標状態までの探索を行います。
元のJavaのコードはSearchクラスのbreadthFirstメソッドとして実装されていますが、 今回は関数として実装しました。
実際に探索を行うのはbreadth_first()関数です。
ポイントは隣接する状態を探索して、探索予定ノードリスト(変数open)に追加するところです。
for m in node.children:
if m in open or m in closed:
continue
m.pointer = node
if m == goal:
open.insert(0, m)
else:
open.append(m)
探索予定ノードリスト(変数open)の末尾に隣接する状態を追加しているので、幅優先探索になります。
ここを変えると深さ優先探索になります。
#! /usr/bin/python
# -*- coding: Shift_JIS -*-
class Node:
def __init__(self, name):
"""
@param name: 都市名
"""
self.name = name
self.children = [] #遷移できるノードのリスト
self.pointer = None #解表示のためのポインタ
def __str__(self):
return self.name
def nodes_str(nodes):
"""
Nodeのリストの出力用文字列を作成する
@param nodes: Nodeのリスト
"""
return map(str, nodes)
def make_state_space():
"""
状態空間の生成
@return: ノードのリストを返す。
"""
node = [Node("L.A.Airport"),
Node("UCLA"),
Node("Hoolywood"),
Node("Anaheim"),
Node("GrandCanyon"),
Node("SanDiego"),
Node("Downtown"),
Node("Pasadena"),
Node("DisneyLand"),
Node("Las Vegas")]
node[0].children = [node[1], node[2]]
node[1].children = [node[2], node[6]]
node[2].children = [node[3], node[6], node[7]]
node[3].children = [node[4], node[7], node[8]]
node[4].children = [node[8], node[9]]
node[5].children = [node[1]]
node[6].children = [node[5], node[7]]
node[7].children = [node[8], node[9]]
node[8].children = [node[9]]
return node
def print_solution(node):
"""
解の表示
"""
if node.pointer == None:
print node
else:
print node, "<-",
print_solution(node.pointer)
def breadth_first(start, goal):
"""
幅優先探索
@param start: 探索開始ノード
@param goal: 探索終了ノード
"""
open = [start] #探索予定のノードのリスト
closed = [] #探索を終了したノードのリスト
success = False
step = 0
while 1:
step += 1
print "STEP:", step
print "OPEN:", nodes_str(open)
print "closed:", nodes_str(closed)
if len(open) == 0:
success = False
break
node = open.pop(0)
if node == goal:
success = True
break
closed.append(node)
for m in node.children:
if m in open or m in closed:
continue
m.pointer = node
if m == goal:
open.insert(0, m)
else:
open.append(m)
if success:
print "*** Solution ***"
print_solution(goal)
if __name__ == "__main__":
nodes = make_state_space()
breadth_first(nodes[0], nodes[-1])
ちなみに、NetBeansのPythonプラグインを使ってみました。
よくできていて、なかなか快適です。