前回の「分岐限定法」の続きです。
『Javaによる知能プログラミング入門』の「2.探索とパターン照合」にあるA*アルゴリズムのソースコードをPythonで実装してみました。
本では分岐限定法の後に山登り法と最良優先探索を説明して問題点を明らかにし、その後でA*アルゴリズムが説明されています。
有向グラフとして表現されている状態空間の、初期状態から目標状態までの探索を行います。
ノード間の□の中の数字は、各ノード間のコストを表します。
各ノートに添付された○の中の数字は、そのノードのヒューリスティックな値を表します。
#! /usr/bin/python
# -*- coding: Shift_JIS -*-
def printNodes(nodes):
"""
Nodeのリストの出力用文字列を作成する
nodes Nodeのリスト
"""
return map(str, nodes)
class Node(object):
def __init__(self, name, value):
self.name = name
self.children = [] #遷移できるノードのリスト
self.children_costs = {} #<Node, Integer>
self.pointer = None #解表示のためのポインタ
self.__g_value = 0 # コスト
self.__f_value = 0 # 評価値
self.has_g_value = False
self.has_f_value = False
self.h_value = value # ヒューリスティック値
def get_f_value(self):
return self.__f_value
def set_f_value(self, value):
self.has_f_value = True
self.__f_value = value
f_value = property(get_f_value, set_f_value)
def get_g_value(self):
return self.__g_value
def set_g_value(self, value):
self.has_g_value = True
self.__g_value = value
g_value = property(get_g_value, set_g_value)
def add_child(self, child, cost):
"""
@param child: この節点の子節点
@param cost: その子節点までのコスト
"""
self.children.append(child)
self.children_costs[child] = cost
def get_cost(self, child):
"""
子節点までのコストを取得する
@param child: この節点の子節点
@return: 子節点までのコスト
"""
return self.children_costs[child]
def __str__(self):
result = "%s(h:%d)" % (self.name, self.h_value)
if self.has_g_value:
result = "%s(g:%d)" % (result, self.g_value)
if self.has_f_value:
result = "%s(f:%d)" % (result, self.f_value)
return result
def nodes_str(nodes):
"""
Nodeのリストの出力用文字列を作成する
@param nodes: Nodeのリスト
"""
return map(str, nodes)
def make_state_space():
"""
状態空間の生成
@return: ノードのリストを返す。
"""
node = [Node("L.A.Airport",0),
Node("UCLA",7),
Node("Hoolywood",4),
Node("Anaheim",6),
Node("GrandCanyon",1),
Node("SanDiego",2),
Node("Downtown",3),
Node("Pasadena",4),
Node("DisneyLand",2),
Node("Las Vegas",0)]
node[0].add_child(node[1],1)
node[0].add_child(node[2],3)
node[1].add_child(node[2],1)
node[1].add_child(node[6],6)
node[2].add_child(node[3],6)
node[2].add_child(node[6],6)
node[2].add_child(node[7],3)
node[3].add_child(node[4],5)
node[3].add_child(node[7],2)
node[3].add_child(node[8],4)
node[4].add_child(node[8],2)
node[4].add_child(node[9],1)
node[5].add_child(node[1],1)
node[6].add_child(node[5],7)
node[6].add_child(node[7],2)
node[7].add_child(node[8],3)
node[7].add_child(node[9],7)
node[8].add_child(node[9],5)
return node
def print_solution(node):
"""
解の表示
"""
if node.pointer == None:
print node
else:
print node, "<-",
print_solution(node.pointer)
def sort_upper_byf_value(open):
"""
Nodeをf_valueの昇順（小さい順）に列べ換える
@param open: Nodeのリスト
"""
def f_value_compare(x, y):
return x.f_value - y.f_value
open.sort(f_value_compare)
def a_star(start, goal):
"""
最良優先探索
@param start: 探索開始ノード
@param goal: 探索終了ノード
"""
open = [start] #探索予定のノードのリスト
start.g_value = 0
start.f_value = 0
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:
gmn = node.g_value + node.get_cost(m)
if m not in open and m not in closed:
m.g_value = gmn
if m in open:
if gmn < m.g_value:
m.g_value = gmn
m.pointer = node
fmn = gmn + m.h_value
if m not in open and m not in closed:
m.pointer = node
m.f_value = fmn
open.append(m)
if m in open and fmn < m.f_value:
m.f_value = fmn
open.append(m)
m.pointer = node
if m in closed and fmn < m.f_value:
m.pointer = node
m.f_value = fmn
closed.remove(m)
open.append(m)
sort_upper_byf_value(open)
if success:
print "*** Solution ***"
print_solution(goal)
if __name__ == "__main__":
nodes = make_state_space()
a_star(nodes[0], nodes[-1])