第２章 状態空間モデル、基本的な探索¶
2.3.3 深さ優先探索¶
Algorithm 2.1 1. 初期状態をオープンリストに入れる。クローズドリストをカラに初期化する 2. while オープンリストが空でない do 3. オープンリストから先頭の要素 s を取り出す。クローズドリストに s を追加する(sを探査することに相当) 4. s が目標状態ならば、解は発見されたとして探索を終了 5. s から接続していて、まだ追加していない状態をすべてオープンリストの先頭に追加する(スタックにプッシュする) 6. end while 探索を終了
In [2]:
class dfSearch(object):
""" 深さ優先探索器
パラメタ
------
verbose : メッセージ表示ありかなしか
rev : 状態を逆順にするかどうか
"""
def __init__(self, verbose=True, rev=True):
self.verbose = verbose
self.rev = rev
def search(self, states, start, goal):
""" 深さ優先探索
パラメタ
-----
states : 辞書 キーに対する値はそのキーに接続する状態のリスト
start : キー(状態)
goal : キー(状態)
戻り値:
goalに到達できれば True, そうでなければ False
"""
open = [start] # open は探索すべき状態のリスト
closed = [] # closedは探索済みの状態のリスト
while open: # 探索すべき状態があれば以下を繰り返す
if self.verbose :
print ('open = ',list(reversed(open)), '\t closed =', closed) # openリストとclosedリストの表示
s = open.pop() # openリストから最後の要素を取り出す
closed.append(s) # 取り出した状態をclosedに追加
if self.verbose :
print ('\t', s,' is visited')
if (s == goal): # ゴールに到達したなら
if self.verbose:
print('reached the goal. closed = ', closed ) # closedリストを表示
return True # 到達したのでTrueを返す
children = states[s]
if self.rev :
children=reversed(children)
adjacents = [x for x in children # 状態sに接続されているすべての状態を集める
if (x not in open) and (x not in closed)] # ただし open と closed に登録されているものを除く
open = open + adjacents # それらの状態をopenに入れる
return False # 到達しなければFalseを返す
In [3]:
# 実行のためのデータ
states = {'a': ['b','c'], 'b': ['d','e'],
'c':['f','g','h'], 'd':['i'], 'e':[], 'f':[], 'g':['j'],
'h': [], 'i':[], 'j':[] }
上のデータの図示:
In [4]:
dfs = dfSearch()
dfs.search(states,'a','j')
Out[4]:
到達したかどうかは答えられるが、スタートからゴールまでと経路が表示されないという問題がある
In [5]:
# 経路表示の改良
class dfSearch_R(object):
""" 深さ優先探索器, 経路を返す
パラメタ
------
verbose : メッセージ表示ありかなしか
rev : 状態を逆順にするかどうか
"""
def __init__(self, verbose=True, rev=True):
self.verbose = verbose
self.rev = rev
def search(self, states, start, goal):
""" 深さ優先探索
パラメタ
-----
states : 辞書 キーに対する値はそのキーに接続する状態のリスト
start : キー(状態)
goal : キー(状態)
戻り値:
goalに到達できれば スタートからゴールまでの経路のリスト, そうでなければ None
"""
open = [start] # open は探索すべき状態のリスト
closed = [] # closedは探索済みの状態のリスト
checked = [] # 経路断片の記憶
while open: # 探索すべき状態があれば以下を繰り返す
if self.verbose :
print ('open = ',list(reversed(open)), '\t closed =', closed) # openリストとclosedリストの表示
s = open.pop() # openリストから最後の要素を取り出す
closed.append(s) # 取り出した状態をclosedに追加
if self.verbose :
print ('\t', s,' is visited')
if (s == goal): # ゴールに到達したなら
if self.verbose:
print('reached the goal. closed = ', closed ) # closedリストを表示
return self.showRoute(checked,start,goal) # 到達したので経路を返す
children = states[s]
if self.rev :
children=reversed(children)
adjacents = [x for x in children # 状態sに接続されているすべての状態を集める
if (x not in open) and (x not in closed)] # ただし open と closed に登録されているものを除く
open = open + adjacents # それらの状態をopenに入れる
for node in adjacents:
checked.append( (node,s) ) # checkedに(x,s)型のデータを記憶
return None # 到達しなければNoneを返す
def showRoute(self, result, start, goal):
""" 経路表示
パラメタ
-----
result : (node1, node2)型のリスト
start, goal : 状態
戻り値
-----
経路の状態のリスト
"""
node = goal
route = []
while (node != start):
route.insert(0,node)
for (x,y) in result :
if x == node :
node = y
break
# print ("next node is ",node)
route.insert(0, start)
#
if self.verbose :
print("Path : ", end = "" )
for x in route[:-1] :
print (x,' -> ',end = "" )
print(route[-1])
return route
In [6]:
dfs2 = dfSearch_R()
dfs2.search(states,'a','j')
Out[6]:
In [7]:
dfs2 = dfSearch_R(verbose=False)
dfs2.search(states,'a','j')
Out[7]:
経路のノードのリストが得られた
2.3.4 幅優先探索¶
Algorithm 2.2 1. 初期状態をオープンリストに入れる。クローズドリストをカラに初期化する 2. while オープンリストが空でない do 3. オープンリストから先頭の要素 s を取り出す。クローズドリストに s を追加する(sを探査することに相当) 4. s が目標状態ならば、解は発見されたとして探索を終了 5. s から接続していて、まだ追加していない状態をすべてオープンリストの末尾に追加する(キューにエンキューする) 6. end while 探索を終了
In [8]:
# 経路表示なし
class bfSearch(object):
""" 幅優先探索器
パラメタ
------
verbose : メッセージ表示ありかなしか
rev : 状態を逆順にするかどうか
"""
def __init__(self, verbose=True, rev=True):
self.verbose = verbose
self.rev = rev
def search(self, states, start, goal):
""" 幅優先探索
パラメタ
-----
states : 辞書 キーに対する値はそのキーに接続する状態のリスト
start : キー(状態)
goal : キー(状態)
戻り値:
goalに到達できれば True, そうでなければ False
"""
open = [start] # open は探索すべき状態のリスト
closed = [] # closedは探索済みの状態のリスト
while open : # 探索すべき状態がある限り
if self.verbose :
print ('open = ',list(reversed(open)), '\t closed =', closed) # openリストとclosedリストの表示
s = open.pop() # openから状態を取り出す
closed.append(s) # closedに入れる
if self.verbose :
print('\t', s,' is visited')
if (s == goal): # ゴールに到達した場合
if self.verbose :
print('reached the goal. closed = ',closed)
return True # ゴールに到達
children = states[s] # sに接続する状態のリスト
if self.rev :
children=reversed(children)
adjacents = [x for x in children if (x not in open) and (x not in closed) ] # step 5
open = adjacents + open # openに入れる
return False # ゴールに到達しない
In [9]:
# データは深さ優先探索と同じ
# 実行のためのデータ
states = {'a': ['b','c'], 'b': ['d','e'],
'c':['f','g','h'], 'd':['i'], 'e':[], 'f':[], 'g':['j'],
'h': [], 'i':[], 'j':[] }
bfs = bfSearch()
bfs.search(states,'a','j')
Out[9]:
In [10]:
# 経路表示あり
class bfSearch_R(object):
""" 幅優先探索器
パラメタ
------
verbose : メッセージ表示ありかなしか
rev : 状態を逆順にするかどうか
"""
def __init__(self, verbose=True, rev=True):
self.verbose = verbose
self.rev = rev
def search(self, states, start, goal):
""" 幅優先探索
パラメタ
-----
states : 辞書 キーに対する値はそのキーに接続する状態のリスト
start : キー(状態)
goal : キー(状態)
戻り値:
goalに到達できれば 経路のリスト, そうでなければ None
"""
open = [start] # open は探索すべき状態のリスト
closed = [] # closedは探索済みの状態のリスト
checked = []
while open : # 探索すべき状態がある限り
if self.verbose :
print ('open = ',list(reversed(open)), '\t closed =', closed) # openリストとclosedリストの表示
s = open.pop() # openから状態を取り出す
closed.append(s) # closedに入れる
if self.verbose :
print('\t', s,' is visited')
if (s == goal): # ゴールに到達した場合
if self.verbose :
print('reached the goal. closed = ',closed)
return self.showRoute(checked,start,goal) # 到達したので経路を返す
children = states[s] # sに接続する状態のリスト
if self.rev :
children=reversed(children)
adjacents = [x for x in children if (x not in open) and (x not in closed) ]
for node in adjacents:
checked.append( (node,s) ) # checkedに(x,s)型のデータを記憶
open = adjacents + open # openに入れる
return None # ゴールに到達しない
def showRoute(self, result, start, goal):
""" 経路表示
パラメタ
-----
result : (node1, node2)型のリスト
start, goal : 状態
戻り値
-----
経路の状態のリスト
"""
node = goal
route = []
while (node != start):
route.insert(0,node)
for (x,y) in result :
if x == node :
node = y
break
# print ("next node is ",node)
route.insert(0, start)
#
if self.verbose :
print("Path : ", end = "" )
for x in route[:-1] :
print (x,' -> ',end = "" )
print(route[-1])
return route
In [11]:
# 経路情報あり
bfs2 = bfSearch_R()
bfs2.search(states,'a','j')
Out[11]:
In [12]:
# 実行のためのデータ
states2 = {'S': ['A','B'], 'A': ['C','D','S'],
'B':['D','G','S'], 'C':[ 'A' ,'S'], 'D':['A','B','E','F'], 'E':['D','F'],
'F':['D','E', 'G'], 'G':['B','F'] }
図示すると:
In [17]:
# Open listでは左が「上」、スタックとしては後から積まれ、先に取り出される対象 (Last In First Out)
dfs.search(states2,'S','B') # SからBへ
Out[17]:
In [18]:
# Open listでは左が「先頭」右が『末尾」、キューとしては『左」の要素が先に取り出される対象 (First In First Out)
bfs2.search(states2,'S','F') # SからFへ
Out[18]:
In [20]:
# 統合バージョン
class classicSearch(object):
""" 経路探索器
パラメタ
------
verbose : メッセージ表示ありかなしか
rev : 状態を逆順にするかどうか
"""
def __init__(self, verbose=True, rev=True):
self.verbose = verbose
self.rev = rev
def BFsearch(self, states, start, goal):
""" 幅優先探索
パラメタ
-----
states : 辞書 キーに対する値はそのキーに接続する状態のリスト
start : キー(状態)
goal : キー(状態)
戻り値:
goalに到達できれば 経路のリスト, そうでなければ None
"""
return search(self, states, start, goal, method='B')
def DFsearch(self, states, start, goal):
""" 深さ優先探索
パラメタ
-----
states : 辞書 キーに対する値はそのキーに接続する状態のリスト
start : キー(状態)
goal : キー(状態)
戻り値:
goalに到達できれば 経路のリスト, そうでなければ None
"""
return search(self, states, start, goal, method='D')
def search(self, states, start, goal, method='B'):
open = [start] # open は探索すべき状態のリスト
closed = [] # closedは探索済みの状態のリスト
checked = []
while open : # 探索すべき状態がある限り
if self.verbose :
print ('open = ',list(reversed(open)), '\t closed =', closed) # openリストとclosedリストの表示
s = open.pop() # openから状態を取り出す
closed.append(s) # closedに入れる
if self.verbose :
print( '\t', s,' is visited')
if (s == goal): # ゴールに到達した場合
if self.verbose :
print('reached the goal. closed = ', closed)
return self.showRoute(checked,start,goal) # 到達したので経路を返す
children = states[s] # sに接続する状態のリスト
if self.rev :
children=reversed(children)
adjacents = [x for x in children if (x not in open) and (x not in closed) ]
for node in adjacents:
checked.append( (node,s) ) # checkedに(x,s)型のデータを記憶
if method == 'B' :
open = adjacents + open # openの方が取り出し口に近い
else : # method = 'D'
open = open + adjacents # adjacentsの方が取り出し口に近い
return None # ゴールに到達しない
def showRoute(self, result, start, goal):
""" 経路表示
パラメタ
-----
result : (node1, node2)型のリスト
start, goal : 状態
戻り値
-----
経路の状態のリスト
"""
node = goal
route = []
while (node != start):
route.insert(0,node)
for (x,y) in result :
if x == node :
node = y
break
# print ("next node is ",node)
route.insert(0, start)
#
if self.verbose :
print("Path : ", end = "" )
for x in route[:-1] :
print (x,' -> ',end = "" )
print(route[-1])
return route
In [21]:
states2 = {'S': ['A','B'], 'A': ['C','D','S'],
'B':['D','G','S'], 'C':[ 'A' ,'S'], 'D':['A','B','E','F'], 'E':['D','F'],
'F':['D','E', 'G'], 'G':['B','F'] }
cls = classicSearch()
print("幅優先")
cls.search(states2, 'S','F') # 幅優先
print("\n深さ優先")
cls.search(states2,'S','B',method='D')
Out[21]: