第３章 最適経路の探索

3.2.1 最適探索のアルゴリズム

1. 初期状態のコスト値を0としてオープンリストに追加する。クローズドリストを空に初期化する。
2. while  オープンリストが空でない do
3.      オープンリストから先頭の要素sを取り出す。クローズドリストにsを追加する。
4.      s が目標状態ならば、解は発見されたそ知恵探索を終了
5.      s から接続していてまだ探査していない状態をすべてオープンリストに追加する。
　　　　　　　　オープンリスト内の状態の累積コストの推定値 g^(s) を再検査し、
        　　　　累積コストの推定値が小さい順に並び替える
6. end while  探索を終了

# 最適探索
class OptimalSearch(object):
    """ 最適探索器
        パラメタ
        ------
            verbose : メッセージ表示ありかなしか
    """         
    def __init__(self, verbose=True):
        self.verbose = verbose

    def search(self, statesMap, start, goal):
        """ 最適探索
            パラメタ
            -----
                statesMap : 辞書 キーに対する値はそのキーに接続する状態とコストのタプルを要素とするリスト
                start : キー(状態)
                goal : キー(状態)
            戻り値: 
                goalに到達できれば True, そうでなければ False
        """
        # openは探索対象の状態の記録用, 実態は状態とコストのタプルのリスト
        closed = dict()         # closedは探索済み用の辞書、キーは状態、値はコスト
        cost = 0                # スタート地点のコストは0とする
        open=[(cost,start)]       # open は探索すべき状態とコストのタプルを要素とするリスト
        while open:     # 探索すべき状態があれば以下を繰り返す
            if self.verbose :
                    print ('open = ',list(reversed(open)), '\t closed =', closed)  # openリストとclosedリストの表示
            cost, s = open.pop()    # openリストから最後の要素(コストと状態のタプル)を取り出す.
            if self.verbose:
                print(s, 'is visited')
            closed[s]=cost          # closed辞書に状態をコストと共に登録
            #
            if (s == goal):			# 目標状態に到達
                if (self.verbose) : 
                    print('reached the goal. closed = ', closed)
                return True
            self.open=open; self.closed=closed; self.cost=cost # apend_to_open を呼び出すための変数の受け渡し
            open = sorted(self.append_to_open(s,statesMap),reverse=True)   # あらたなopenリストを作り並び替え
        return False
    ###
    def append_to_open(self, state, stateMap):
        """
            オープンリストに新たな状態を追加する
            パラメタ
            -----
                state : 状態
                statesMap : 辞書 キーに対する値はそのキーに接続する状態とコストのタプルを要素とするリスト
            戻り値: 
                コストと状態のタプルを要素とするリスト
        """
        new_open = { s:c for (c,s) in self.open}    # 探索対象の状態とそのコストの辞書
        adjacents = stateMap[state].copy()     # state状態に接続する状態を取り出す
        #
        while adjacents :   # copyを行わないと元データが破壊される
             next_state, added_cost = adjacents.pop()    # 状態を取り出す(正確には状態とコストのタプル)
             if next_state not in self.closed:       #  closed に登録されていなければ
                new_cost = self.cost + added_cost         # コストの計算
                if next_state not in  new_open:    # open に登録されていなければ
                    new_open[next_state] = new_cost         # その状態とコストを登録
                elif new_open[next_state] > new_cost:     # openにあった場合でかつこちらの経路の方がコストが小さい場合
                    new_open[next_state] = new_cost         # コストを書き換える
        return [(c,s) for (s,c) in new_open.items()]  # 辞書からリストに変換---要素も(コスト、状態)のタプルに変換

# 状態空間  { 状態: [ (隣接する状態, コスト) ... ] , ... }

StateMap = {'s': [('a',2), ('b',6)], 
            'a':[('s',2),('b',2),('c',1)],
            'b': [('s',6),('a',2),('e',5),('f',4)],
            'c':[('a',1),('d',5),('e',2)],
            'd':[('c',5),('e',2),('g',1)], 
            'e':[('b',5),('c',2),('d',1),('g',5)],
            'f':[('b',4)],
            'g':[('d',1),('e',5)]}

状態空間の図示

# 最適探索
print ("optimal search...")
opt = OptimalSearch()
map=StateMap.copy()
opt.search(StateMap,'s','g')

# これだと経路が出力されない

optimal search...
open =  [(0, 's')] 	 closed = {}
s is visited
open =  [(2, 'a'), (6, 'b')] 	 closed = {'s': 0}
a is visited
open =  [(3, 'c'), (4, 'b')] 	 closed = {'s': 0, 'a': 2}
c is visited
open =  [(4, 'b'), (5, 'e'), (8, 'd')] 	 closed = {'s': 0, 'a': 2, 'c': 3}
b is visited
open =  [(5, 'e'), (8, 'd'), (8, 'f')] 	 closed = {'s': 0, 'a': 2, 'c': 3, 'b': 4}
e is visited
open =  [(6, 'd'), (8, 'f'), (10, 'g')] 	 closed = {'s': 0, 'a': 2, 'c': 3, 'b': 4, 'e': 5}
d is visited
open =  [(7, 'g'), (8, 'f')] 	 closed = {'s': 0, 'a': 2, 'c': 3, 'b': 4, 'e': 5, 'd': 6}
g is visited
reached the goal. closed =  {'s': 0, 'a': 2, 'c': 3, 'b': 4, 'e': 5, 'd': 6, 'g': 7}

True

StateMap

{'s': [('a', 2), ('b', 6)],
 'a': [('s', 2), ('b', 2), ('c', 1)],
 'b': [('s', 6), ('a', 2), ('e', 5), ('f', 4)],
 'c': [('a', 1), ('d', 5), ('e', 2)],
 'd': [('c', 5), ('e', 2), ('g', 1)],
 'e': [('b', 5), ('c', 2), ('d', 1), ('g', 5)],
 'f': [('b', 4)],
 'g': [('d', 1), ('e', 5)]}

経路を表示するバージョン

class OptimalSearch_R(object):
    """ 最適探索器, 経路表示つき
        パラメタ
        ------
            verbose : メッセージ表示ありかなしか
    """         
    def __init__(self, verbose=True):
        self.verbose = verbose

    def search(self, statesMap, start, goal):
        """ 最適探索
            パラメタ
            -----
                statesMap : 辞書 キーに対する値はそのキーに接続する状態とコストのタプルを要素とするリスト
                start : キー(状態)
                goal : キー(状態)
            戻り値: 
                goalに到達できれば True, そうでなければ False
        """
        # openは探索対象の状態の記録用, 実態は状態とコストのタプルのリスト
        closed = dict()         # closedは探索済み用の辞書、キーは状態、値はコスト
        cost = 0                # スタート地点のコストは0とする
        open=[(cost,start,start)]       # open は探索すべきコスト、状態、直前の状態のタプルを要素とするリスト
        while open:     # 探索すべき状態があれば以下を繰り返す
            if self.verbose :
                    print ('open = ',list(reversed(open)), '\t closed =', closed)  # openリストとclosedリストの表示
            cost, s, prec = open.pop()    # openリストから最後の要素(コストと状態,直前状態のタプル)を取り出す.
            if self.verbose:
                print(s, 'is visited')
            closed[s] = (cost, prec)          # closed辞書に状態をコストと直前の状態を共に登録
            #
            if (s == goal):			# 目標状態に到達
                if (self.verbose) : 
                    print('reached the goal. closed = ', closed)
                return self.showRoute(closed,start,goal)
            self.open=open; self.closed=closed; self.cost=cost # apend_to_open を呼び出すための変数の受け渡し
            open = sorted(self.append_to_open(s, statesMap),reverse=True)   # あらたなopenリストを作り並び替え
        return False
    ###
    def append_to_open(self, state, stateMap):
        """
            オープンリストに新たな状態を追加する
            パラメタ
            -----
                state : 状態
                statesMap : 辞書 キーに対する値はそのキーに接続する状態とコストのタプルを要素とするリスト
            戻り値: 
                コストと状態のタプルを要素とするリスト
        """
        new_open = { s:(c,prec) for (c,s,prec) in self.open}    # 探索対象の状態とそのコストの辞書
        adjacents = stateMap[state].copy()      # state状態に接続する状態を取り出す
        #
        while adjacents :
             next_state, added_cost = adjacents.pop()    # 状態を取り出す(正確には状態とコストのタプル)
             if next_state not in self.closed:       #  closed に登録されていなければ
                new_cost = self.cost + added_cost         # コストの計算
                if next_state not in  new_open:    # open に登録されていなければ
                    new_open[next_state] = (new_cost, state)         # その状態とコストを登録
                elif new_open[next_state][0] > new_cost:     # openにあった場合でかつこちらの経路の方がコストが小さい場合
                    new_open[next_state] = (new_cost,state)        # コストを書き換える
        return [(c,s,p) for (s,(c,p)) in new_open.items()]  # 辞書からリストに変換---要素も(コスト、状態)のタプルに変換
    #
    def showRoute(self, result, start, goal):
        """ 経路表示
            パラメタ
            -----
                result :　辞書、値は (コスト1, node)型タプル
                start, goal : 状態
            戻り値
            -----
                経路の状態のリスト
        """
        node=goal
        route = []
        if (self.verbose) :
                print ('cost = ',result[goal][0] )
        while (node != start):
          route.append(node)
          _,node = result[node]
        route.append(start)
        route.reverse()
        if (self.verbose) :
           for x in route[:-1]:
                 print ( x,'=(',result[x][0],') -> ',end="")
           print ( goal, '=(',result[goal][0],')' )
        return route

opt2=OptimalSearch_R()
opt2.search(StateMap,'s','g')

open =  [(0, 's', 's')] 	 closed = {}
s is visited
open =  [(2, 'a', 's'), (6, 'b', 's')] 	 closed = {'s': (0, 's')}
a is visited
open =  [(3, 'c', 'a'), (4, 'b', 'a')] 	 closed = {'s': (0, 's'), 'a': (2, 's')}
c is visited
open =  [(4, 'b', 'a'), (5, 'e', 'c'), (8, 'd', 'c')] 	 closed = {'s': (0, 's'), 'a': (2, 's'), 'c': (3, 'a')}
b is visited
open =  [(5, 'e', 'c'), (8, 'd', 'c'), (8, 'f', 'b')] 	 closed = {'s': (0, 's'), 'a': (2, 's'), 'c': (3, 'a'), 'b': (4, 'a')}
e is visited
open =  [(6, 'd', 'e'), (8, 'f', 'b'), (10, 'g', 'e')] 	 closed = {'s': (0, 's'), 'a': (2, 's'), 'c': (3, 'a'), 'b': (4, 'a'), 'e': (5, 'c')}
d is visited
open =  [(7, 'g', 'd'), (8, 'f', 'b')] 	 closed = {'s': (0, 's'), 'a': (2, 's'), 'c': (3, 'a'), 'b': (4, 'a'), 'e': (5, 'c'), 'd': (6, 'e')}
g is visited
reached the goal. closed =  {'s': (0, 's'), 'a': (2, 's'), 'c': (3, 'a'), 'b': (4, 'a'), 'e': (5, 'c'), 'd': (6, 'e'), 'g': (7, 'd')}
cost =  7
s =( 0 ) -> a =( 2 ) -> c =( 3 ) -> e =( 5 ) -> d =( 6 ) -> g =( 7 )

['s', 'a', 'c', 'e', 'd', 'g']

3.3.1 最良優先探索

Algorithm 3.2

1. 初期状態のコスト値を0としてオープンリストに追加する。クローズドリストを空に初期化する。
2. while   オープンリストが空ではない  do
3.       オープンリストから先頭の要素s を取り出す。クローズドリストにsを追加する(sを探査することに相当)
4.       s が目標状態ならば、解は発見されたとして探索を終了
5.       s から接続していてまだ探査していない状態をすべてオープンリストに追加する。
                     オープンリスト内の状態を、予測評価値h^(s)が小さい順に並び替える
6. end while  探索を終了

###########################################################
# 3.2 Best-first Search
###########################################################


class bestFSearch(object):
    """ 最良優先探索器
        パラメタ
        ------
            verbose : メッセージ表示ありかなしか
    """         
    def __init__(self, verbose=True):
        self.verbose = verbose

    def search(self, statesMap, predicted_cost_Map, start, goal):
        """ 最良優先探索
            パラメタ
            -----
                statesMap : 辞書 キーに対する値はそのキーに接続する状態とコストのタプルを要素とするリスト
                predicted_cost_Map: 辞書、状態をキーとし、値はその状態の予測評価値
                start : キー(状態)
                goal : キー(状態)
            戻り値: 
                goalに到達できれば True, そうでなければ False
        """
        # openは探索対象の状態の記録用, 実態は予測評価値、状態、累積コストのタプルのリスト
        closed = dict()         # closedは探索済み用の辞書、キーは状態、値はコスト
        cost = 0                # スタート地点のコストは0とする
        hcost = predicted_cost_Map[start]
        open=[(hcost,start,cost)]       # open は探索すべき状態と予測評価値と累積コストのタプルを要素とするリスト
        while open:     # 探索すべき状態があれば以下を繰り返す
            if self.verbose :
                    print ('open = ',list(reversed(open)), '\t closed =', closed)  # openリストとclosedリストの表示
            hcost, s, cost = open.pop()    # openリストから最後の要素(コストと状態のタプル)を取り出す.
            if self.verbose:
                print(s, 'is visited')
            closed[s]=cost          # closed辞書に状態をコストと共に登録
            #
            if (s == goal):			# 目標状態に到達
                if (self.verbose) : 
                    print('reached the goal. closed = ', closed)
                return True
            self.open=open; self.closed=closed; self.cost=cost # apend_to_open を呼び出すための変数の受け渡し
            open = sorted(self.append_to_open(s, statesMap, predicted_cost_Map),reverse=True)   # あらたなopenリストを作り並び替え
        return False
    ###
    def append_to_open(self, state,  stateMap, predicted_cost_Map):
        """
            オープンリストに新たな状態を追加する
            パラメタ
            -----
                state : 状態
                statesMap : 辞書 キーに対する値はそのキーに接続する状態とコストのタプルを要素とするリスト
                predicted_cost_Map: 辞書、状態をキーとし、値はその状態の予測評価値
            戻り値: 
                コストと状態のタプルを要素とするリスト
        """
        new_open = { s:(h,c) for (h,s,c) in self.open}    # 探索対象の状態とそのコストの辞書
        adjacents = stateMap[state].copy()     # state状態に接続する状態を取り出す
        #
        while adjacents :   # copyを行わないと元データが破壊される
             next_state, added_cost = adjacents.pop()    # 状態を取り出す(正確には状態とコストのタプル)
             if next_state not in self.closed:       #  closed に登録されていなければ
                new_cost = self.cost + added_cost         # コストの計算
                if next_state not in  new_open:    # open に登録されていなければ
                    new_open[next_state] = (predicted_cost_Map[next_state], new_cost)         # その状態と予測評価値とコストを登録
                elif new_open[next_state][1] > new_cost:     # openにあった場合でかつこちらの経路の方がコストが小さい場合
                    new_open[next_state] =  (new_open[next_state][0], new_cost)        # コストを書き換える
        return [(h,s,c) for (s,(h,c)) in new_open.items()]  # 辞書からリストに変換---要素も(コスト、状態)のタプルに変換

#　予測評価値
Predicted_costs = {'a':4, 'b':2, 'c':3, 'd':1, 'e':1, 'f':0, 'g':0, 's':4}

# 状態空間  { 状態: [ (隣の状態, コスト) ... ] , ... }
StateMap = {'s': [('a',2), ('b',6)], 
            'a':[('s',2),('b',2),('c',1)],
            'b': [('s',6),('a',2),('e',5),('f',4)],
            'c':[('a',1),('d',5),('e',2)],
            'd':[('c',5),('e',2),('g',1)], 
            'e':[('b',5),('c',2),('d',1),('g',5)],
            'f':[('b',4)],
            'g':[('d',1),('e',5)]}

状態空間の図示

# 最良優先探索
print ("\n\nBest First Search...")
bestFS = bestFSearch()
bestFS.search(StateMap,Predicted_costs,'s','g')

Best First Search...
open =  [(4, 's', 0)] 	 closed = {}
s is visited
open =  [(2, 'b', 6), (4, 'a', 2)] 	 closed = {'s': 0}
b is visited
open =  [(0, 'f', 10), (1, 'e', 11), (4, 'a', 2)] 	 closed = {'s': 0, 'b': 6}
f is visited
open =  [(1, 'e', 11), (4, 'a', 2)] 	 closed = {'s': 0, 'b': 6, 'f': 10}
e is visited
open =  [(0, 'g', 16), (1, 'd', 12), (3, 'c', 13), (4, 'a', 2)] 	 closed = {'s': 0, 'b': 6, 'f': 10, 'e': 11}
g is visited
reached the goal. closed =  {'s': 0, 'b': 6, 'f': 10, 'e': 11, 'g': 16}

True

経路表示つきの最良優先探索

class bestFSearch_R(object):
    """ 最良優先探索器, 経路表示つき
        パラメタ
        ------
            verbose : メッセージ表示ありかなしか
    """         
    def __init__(self, verbose=True):
        self.verbose = verbose

    def search(self, statesMap, predicted_cost_Map, start, goal):
        """ 最良優先探索
            パラメタ
            -----
                statesMap : 辞書 キーに対する値はそのキーに接続する状態とコストのタプルを要素とするリスト
                predicted_cost_Map: 辞書、状態をキーとし、値はその状態の予測評価値
                start : キー(状態)
                goal : キー(状態)
            戻り値: 
                goalに到達できれば True, そうでなければ False
        """
        # openは探索対象の状態の記録用, 実態は予測評価値、状態、累積コストのタプルのリスト
        closed = dict()         # closedは探索済み用の辞書、キーは状態、値はコスト
        cost = 0                # スタート地点のコストは0とする
        hcost = predicted_cost_Map[start]
        open=[(hcost,start,cost,start)]       # open は探索すべき状態と予測評価値と累積コストと前の状態のタプルを要素とするリスト
        while open:     # 探索すべき状態があれば以下を繰り返す
            if self.verbose :
                    print ('open = ',list(reversed(open)), '\t closed =', closed)  # openリストとclosedリストの表示
            hcost, s, cost, pre = open.pop()    # openリストから最後の要素(予測評価値、状態、コスト、前状態のタプル)を取り出す.
            if self.verbose:
                print(s, 'is visited')
            closed[s]=(cost,pre)          # closed辞書に状態をコストと共に登録
            #
            if (s == goal):			# 目標状態に到達
                if (self.verbose) : 
                    print('reached the goal. closed = ', closed)
                return self.showRoute(closed, start, goal)
            self.open=open; self.closed=closed; self.cost=cost # apend_to_open を呼び出すための変数の受け渡し
            open = sorted(self.append_to_open(s, statesMap, predicted_cost_Map),reverse=True)   # あらたなopenリストを作り並び替え
        return False
    ###
    def append_to_open(self,  state,  stateMap, predicted_cost_Map):
        """
            オープンリストに新たな状態を追加する
            パラメタ
            -----
                state : 状態
                statesMap : 辞書 キーに対する値はそのキーに接続する状態とコストのタプルを要素とするリスト
                predicted_cost_Map: 辞書、状態をキーとし、値はその状態の予測評価値
            戻り値: 
                コストと状態と前の状態のタプルを要素とするリスト
        """
        new_open = { s:(h,c,p) for (h,s,c,p) in self.open}    # 探索対象の状態とそのコストの辞書
        adjacents = stateMap[state].copy()     # state状態に接続する状態を取り出す
        #
        while adjacents :   # copyを行わないと元データが破壊される
             next_state, added_cost = adjacents.pop()    # 状態を取り出す(正確には状態とコストのタプル)
             if next_state not in self.closed:       #  closed に登録されていなければ
                new_cost = self.cost + added_cost         # コストの計算
                if next_state not in  new_open:    # open に登録されていなければ
                    new_open[next_state] = (predicted_cost_Map[next_state], new_cost,state)         # その状態と予測評価値とコストを登録
                elif new_open[next_state][1] > new_cost:     # openにあった場合でかつこちらの経路の方がコストが小さい場合
                    new_open[next_state] =  (new_open[next_state][0], new_cost,state)        # コストを書き換える
        return [(h,s,c,p) for (s,(h,c,p)) in new_open.items()]  # 辞書からリストに変換---要素も(予測評価値、状態、コスト、前状態)のタプルに変換
    #
    def showRoute(self, result, start, goal):
        """ 経路表示
            パラメタ
            -----
                result :　辞書、値は (コスト1, node)型タプル
                start, goal : 状態
            戻り値
            -----
                経路の状態のリスト
        """
        node=goal
        route = []
        if (self.verbose) :
                print ('cost = ',result[goal][0] )
        while (node != start):
          route.append(node)
          _,node = result[node]
        route.append(start)
        route.reverse()
        if (self.verbose) :
           for x in route[:-1]:
                 print ( x,'=(',result[x][0],') -> ',end="")
           print ( goal, '=(',result[goal][0],')' )
        return route

# 最良優先探索
print ("\n\nBest First Search...")
bestFS = bestFSearch_R()
bestFS.search(StateMap,Predicted_costs,'s','g')

Best First Search...
open =  [(4, 's', 0, 's')] 	 closed = {}
s is visited
open =  [(2, 'b', 6, 's'), (4, 'a', 2, 's')] 	 closed = {'s': (0, 's')}
b is visited
open =  [(0, 'f', 10, 'b'), (1, 'e', 11, 'b'), (4, 'a', 2, 's')] 	 closed = {'s': (0, 's'), 'b': (6, 's')}
f is visited
open =  [(1, 'e', 11, 'b'), (4, 'a', 2, 's')] 	 closed = {'s': (0, 's'), 'b': (6, 's'), 'f': (10, 'b')}
e is visited
open =  [(0, 'g', 16, 'e'), (1, 'd', 12, 'e'), (3, 'c', 13, 'e'), (4, 'a', 2, 's')] 	 closed = {'s': (0, 's'), 'b': (6, 's'), 'f': (10, 'b'), 'e': (11, 'b')}
g is visited
reached the goal. closed =  {'s': (0, 's'), 'b': (6, 's'), 'f': (10, 'b'), 'e': (11, 'b'), 'g': (16, 'e')}
cost =  16
s =( 0 ) -> b =( 6 ) -> e =( 11 ) -> g =( 16 )

['s', 'b', 'e', 'g']

• 最適探索に比べ経路は短いが、コストが高いものが得られた

3.4.1 A*アルゴリズム

A* アルゴリズム

1. 初期状態のコスト値を0としてオープンリストに追加する。クローズドリストを空に初期化する。
2. while   オープンリストが空ではない  do
3.       オープンリストから先頭の要素s を取り出す。クローズドリストにsを追加する(sを探査することに相当)
4.       s が目標状態ならば、解は発見されたとして探索を終了
5.       s から接続されているすべての状態s'に対してコスト値g^(s')と予測評価値h^(s')からf^(s')を計算する。
6.       5の状態のうちで、オープンリストにもクローズドリストにも含まれていないものはオープンリストに加える。
7.       5の状態のうちで、オープンリストかクローズドリストに含まれていたものについては、
　　　　すでに入っているものよりf^(s)の値が小さければ、元のものを削除し、
    　　新しいものをオープンリストに追加する
8.      オープンリスト内の状態を、コスト値と予測評価値の和f^(s)が小さい順に並び替える
6. end while  探索を終了

###########################################################
# 3.3 A-star
###########################################################

class aStarSearch(object):
    """ A*探索器
        パラメタ
        ------
            verbose : メッセージ表示ありかなしか
    """         
    def __init__(self, verbose=True):
        self.verbose = verbose

    def search(self, statesMap, predictedCostMap, start, goal):
        """ A*探索
            パラメタ
            -----
                statesMap : 辞書 キーに対する値はそのキーに接続する状態とコストのタプルを要素とするリスト
                predicted_cost_Map: 辞書、状態をキーとし、値はその状態の予測評価値
                start : キー(状態)
                goal : キー(状態)
            戻り値: 
                クローズドリストを返す
        """
        # openは探索対象の状態の記録用, 実態は予測評価値、状態、累積コストのタプルのリスト
        closed = dict()         # closedは探索済み用の辞書、キーは状態、値はコスト
        cost = 0                # スタート地点のコストは0とする
        hcost = predictedCostMap[start]+cost
        open=[(hcost,start,cost)]       # open は探索すべき状態と予測評価値と累積コストのタプルを要素とするリスト
        while open:     # 探索すべき状態があれば以下を繰り返す
            if self.verbose :
                    print ('open = ',list(reversed(open)), '\t closed =', closed)  # openリストとclosedリストの表示
            hcost, s, cost = open.pop()    # openリストから最後の要素(コストと状態のタプル)を取り出す.
            if self.verbose:
                print(s, 'is visited')
            closed[s]=(hcost,cost)          # closed辞書に状態をコストと共に登録
            self.open=open; self.closed=closed; self.cost=cost # apend_to_open を呼び出すための変数の受け渡し
            open = sorted(self.append_to_open(s, statesMap, predictedCostMap),reverse=True)  
            # あらたなopenリストを作り並び替え
        return closed
    ###
    def append_to_open(self, state, stateMap, predictedCostMap):
        """
            オープンリストに新たな状態を追加する
            パラメタ
            -----
                state : 状態
                statesMap : 辞書 キーに対する値はそのキーに接続する状態とコストのタプルを要素とするリスト
                predicted_cost_Map: 辞書、状態をキーとし、値はその状態の予測評価値
            戻り値: 
                コストと状態のタプルを要素とするリスト
        """
        new_open = { s:(h,c) for (h,s,c) in self.open}    # 探索対象の状態とそのコストの辞書
        adjacents = stateMap[state].copy()     # state状態に接続する状態を取り出す
        #
        while adjacents :   # copyを行わないと元データが破壊される
             next_state, added_cost = adjacents.pop()    # 状態を取り出す(正確には状態とコストのタプル)
             new_cost = self.cost + added_cost
             hcost = new_cost+predictedCostMap[next_state]
             if next_state in self.closed:       #  closed に登録されていれば
                if self.closed[next_state][0] > hcost:
                    self.closed[next_state] = (hcost, new_cost)
             else:
                if next_state not in  new_open:    # open に登録されていなければ
                        new_open[next_state] = (hcost, new_cost)         # その状態と予測評価値とコストを登録
                elif new_open[next_state][0] > hcost:     # openにあった場合でかつこちらの経路の方がコストが小さい場合
                        new_open[next_state] =  (hcost, new_cost)        # コストを書き換える
        return [(h,s,c) for (s,(h,c)) in new_open.items()]  # 辞書からリストに変換---要素も(コスト、状態)のタプルに変換

状態空間の図示

# A* 探索
#　予測評価値
Predicted_costs = {'a':4, 'b':2, 'c':3, 'd':1, 'e':1, 'f':0, 'g':0, 's':4}

# 状態空間  { 状態: [ (隣接状態, コスト) ... ] , ... }
StateMap = {'s': [('a',2), ('b',6)], 
            'a':[('s',2),('b',2),('c',1)],
            'b': [('s',6),('a',2),('e',5),('f',4)],
            'c':[('a',1),('d',5),('e',2)],
            'd':[('c',5),('e',2),('g',1)], 
            'e':[('b',5),('c',2),('d',1),('g',5)],
            'f':[('b',4)],
            'g':[('d',1),('e',5)]}

print ("\n\nA* Search")
ass = aStarSearch()
ass.search(StateMap,Predicted_costs,'s','g')

A* Search
open =  [(4, 's', 0)] 	 closed = {}
s is visited
open =  [(6, 'a', 2), (8, 'b', 6)] 	 closed = {'s': (4, 0)}
a is visited
open =  [(6, 'b', 4), (6, 'c', 3)] 	 closed = {'s': (4, 0), 'a': (6, 2)}
b is visited
open =  [(6, 'c', 3), (8, 'f', 8), (10, 'e', 9)] 	 closed = {'s': (4, 0), 'a': (6, 2), 'b': (6, 4)}
c is visited
open =  [(6, 'e', 5), (8, 'f', 8), (9, 'd', 8)] 	 closed = {'s': (4, 0), 'a': (6, 2), 'b': (6, 4), 'c': (6, 3)}
e is visited
open =  [(7, 'd', 6), (8, 'f', 8), (10, 'g', 10)] 	 closed = {'s': (4, 0), 'a': (6, 2), 'b': (6, 4), 'c': (6, 3), 'e': (6, 5)}
d is visited
open =  [(7, 'g', 7), (8, 'f', 8)] 	 closed = {'s': (4, 0), 'a': (6, 2), 'b': (6, 4), 'c': (6, 3), 'e': (6, 5), 'd': (7, 6)}
g is visited
open =  [(8, 'f', 8)] 	 closed = {'s': (4, 0), 'a': (6, 2), 'b': (6, 4), 'c': (6, 3), 'e': (6, 5), 'd': (7, 6), 'g': (7, 7)}
f is visited

{'s': (4, 0),
 'a': (6, 2),
 'b': (6, 4),
 'c': (6, 3),
 'e': (6, 5),
 'd': (7, 6),
 'g': (7, 7),
 'f': (8, 8)}

問題点:目標状態に達するパスが表示されない

解決策: 今までのプログラムと同様にどこから来たかというノードを記憶する

class aStarSearch_R(object):
    """ A*探索器, 経路表示付き
        パラメタ
        ------
            verbose : メッセージ表示ありかなしか
    """         
    def __init__(self, verbose=True):
        self.verbose = verbose

    def search(self, statesMap, predictedCostMap, start, goal):
        """ A*探索
            パラメタ
            -----
                statesMap : 辞書 キーに対する値はそのキーに接続する状態とコストのタプルを要素とするリスト
                predicted_cost_Map: 辞書、状態をキーとし、値はその状態の予測評価値
                start : キー(状態)
                goal : キー(状態)
            戻り値: 
                クローズドリストを返す
        """
        # openは探索対象の状態の記録用, 実態は予測評価値、状態、累積コストのタプルのリスト
        closed = dict()         # closedは探索済み用の辞書、キーは状態、値はコスト
        cost = 0                # スタート地点のコストは0とする
        hcost = predictedCostMap[start]+cost
        open=[(hcost,start,cost,start)]       # open は探索すべき状態と予測評価値と累積コストと前の状態のタプルを要素とするリスト
        while open:     # 探索すべき状態があれば以下を繰り返す
            if self.verbose :
                    print ('open = ',list(reversed(open)), '\t closed =', closed)  # openリストとclosedリストの表示
            hcost, s, cost, prec = open.pop()    # openリストから最後の要素(コストと状態と前状態のタプル)を取り出す.
            if self.verbose:
                print(s, 'is visited')
            closed[s]=(hcost,cost,prec)          # closed辞書に状態をコストと共に登録
            self.open=open; self.closed=closed; self.cost=cost # apend_to_open を呼び出すための変数の受け渡し
            open = sorted(self.append_to_open(s, statesMap, predictedCostMap),reverse=True)  
            # あらたなopenリストを作り並び替え
        return self.showRoute(closed,start,goal)
    ###
    def append_to_open(self, state, stateMap, predictedCostMap):
        """
            オープンリストに新たな状態を追加する
            パラメタ
            -----
                state : 状態
                statesMap : 辞書 キーに対する値はそのキーに接続する状態とコストのタプルを要素とするリスト
                predicted_cost_Map: 辞書、状態をキーとし、値はその状態の予測評価値
            戻り値: 
                コストと状態のタプルを要素とするリスト
        """
        new_open = { s:(h,c,p) for (h,s,c,p) in self.open}    # 探索対象の状態とそのコストの辞書
        adjacents = stateMap[state].copy()     # state状態に接続する状態を取り出す
        #
        while adjacents :   # copyを行わないと元データが破壊される
             next_state, added_cost = adjacents.pop()    # 状態を取り出す(正確には状態とコストのタプル)
             new_cost = self.cost + added_cost
             hcost = new_cost+predictedCostMap[next_state]
             if next_state in self.closed:       #  closed に登録されていれば
                if self.closed[next_state][0] > hcost:
                    self.closed[next_state] = (hcost, new_cost, state)
             else:
                if next_state not in  new_open:    # open に登録されていなければ
                        new_open[next_state] = (hcost, new_cost, state)         # その状態と予測評価値とコストを登録
                elif new_open[next_state][0] > hcost:     # openにあった場合でかつこちらの経路の方がコストが小さい場合
                        new_open[next_state] =  (hcost, new_cost, state)        # コストを書き換える
        return [(h,s,c,p) for (s,(h,c,p)) in new_open.items()]  # 辞書からリストに変換---要素も(コスト、状態)のタプルに変換
    
    def showRoute(self, result, start, goal):
        """ 経路表示
            パラメタ
            -----
                result :　辞書、値は (コスト1, node)型タプル
                start, goal : 状態
            戻り値
            -----
                経路の状態のリスト
        """
        node=goal
        route = []
        if (self.verbose) :
                print ('cost = ',result[goal][0] )
        while (node != start):
          route.append(node)
          node = result[node][-1]
        route.append(start)
        route.reverse()
        if (self.verbose) :
           for x in route[:-1]:
                 print ( x,'=(',result[x][-2],') -> ',end="")
           print ( goal, '=(',result[goal][-2],')' )
        return route

ass2 = aStarSearch_R()
ass2.search(StateMap,Predicted_costs,'s','g')

open =  [(4, 's', 0, 's')] 	 closed = {}
s is visited
open =  [(6, 'a', 2, 's'), (8, 'b', 6, 's')] 	 closed = {'s': (4, 0, 's')}
a is visited
open =  [(6, 'b', 4, 'a'), (6, 'c', 3, 'a')] 	 closed = {'s': (4, 0, 's'), 'a': (6, 2, 's')}
b is visited
open =  [(6, 'c', 3, 'a'), (8, 'f', 8, 'b'), (10, 'e', 9, 'b')] 	 closed = {'s': (4, 0, 's'), 'a': (6, 2, 's'), 'b': (6, 4, 'a')}
c is visited
open =  [(6, 'e', 5, 'c'), (8, 'f', 8, 'b'), (9, 'd', 8, 'c')] 	 closed = {'s': (4, 0, 's'), 'a': (6, 2, 's'), 'b': (6, 4, 'a'), 'c': (6, 3, 'a')}
e is visited
open =  [(7, 'd', 6, 'e'), (8, 'f', 8, 'b'), (10, 'g', 10, 'e')] 	 closed = {'s': (4, 0, 's'), 'a': (6, 2, 's'), 'b': (6, 4, 'a'), 'c': (6, 3, 'a'), 'e': (6, 5, 'c')}
d is visited
open =  [(7, 'g', 7, 'd'), (8, 'f', 8, 'b')] 	 closed = {'s': (4, 0, 's'), 'a': (6, 2, 's'), 'b': (6, 4, 'a'), 'c': (6, 3, 'a'), 'e': (6, 5, 'c'), 'd': (7, 6, 'e')}
g is visited
open =  [(8, 'f', 8, 'b')] 	 closed = {'s': (4, 0, 's'), 'a': (6, 2, 's'), 'b': (6, 4, 'a'), 'c': (6, 3, 'a'), 'e': (6, 5, 'c'), 'd': (7, 6, 'e'), 'g': (7, 7, 'd')}
f is visited
cost =  7
s =( 0 ) -> a =( 2 ) -> c =( 3 ) -> e =( 5 ) -> d =( 6 ) -> g =( 7 )

['s', 'a', 'c', 'e', 'd', 'g']