深さ優先探索

経路をスタックに順次保存していくことで、次に選択する経路を深くしていくことができる

派生アルゴリズム

code:python

def depth_first_search(first_node, is_goal, get_successors):

frontiers = Stack()

frontiers.push(first_node)

explored = {first_node}

while not successors.is_empty():

node = frontiers.pop()

if is_goal(node):

return node

for child in get_successors(node):

if child in explored:

continue

frontiers.push(child) # 最後に追加されたnodeが優先されて選ばれていく

explored.add(child)

return None