A*アルゴリズム

前回の「分岐限定法」の続きです。

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])

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です