前回の「幅優先探索」の続きです。

『Javaによる知能プログラミング入門』の「2.探索とパターン照合」にある深さ優先探索のソースコードをPythonで実装してみました。

有向グラフとして表現されている状態空間の、初期状態から目標状態までの探索を行います。

元のJavaのコードはSearchクラスのbreadthFirstメソッドとして実装されていますが、
今回は関数として実装しました。

実際に探索を行うのはdepth_first()関数です。
ポイントは隣接する状態を探索して、探索予定ノードリスト(変数open)に追加するところです。

j = 0
for m in node.children:
    if m in open or m in closed:
        continue
    m.pointer = node
    if m == goal:
        open.insert(0, m)
    else:
        open.insert(j, m)
    j += 1

探索予定ノードリスト(変数open)の先頭から隣接する状態を追加しているので、深さ優先探索になります。
ここを変えると幅優先探索になります。

#! /usr/bin/python
# -*- coding: Shift_JIS -*-

class Node:
    def __init__(self, name):
        """
        @param name: 都市名
        """
        self.name = name
        self.children = [] #遷移できるノードのリスト
        self.pointer = None #解表示のためのポインタ

    def __str__(self):
        return self.name

def nodes_str(nodes):
    """
    Nodeのリストの出力用文字列を作成する
    @param nodes: Nodeのリスト
    """
    return map(str, nodes)

def make_state_space():
    """
    状態空間の生成
    @return: ノードのリストを返す。
    """
    node = [Node("L.A.Airport"),
            Node("UCLA"),
            Node("Hoolywood"),
            Node("Anaheim"),
            Node("GrandCanyon"),
            Node("SanDiego"),
            Node("Downtown"),
            Node("Pasadena"),
            Node("DisneyLand"),
            Node("Las Vegas")]
    node[0].children = [node[1], node[2]]
    node[1].children = [node[2], node[6]]
    node[2].children = [node[3], node[6], node[7]]
    node[3].children = [node[4], node[7], node[8]]
    node[4].children = [node[8], node[9]]
    node[5].children = [node[1]]
    node[6].children = [node[5], node[7]]
    node[7].children = [node[8], node[9]]
    node[8].children = [node[9]]
    return node

def print_solution(node):
    """
    解の表示
    """
    if node.pointer == None:
        print node
    else:
        print node, "<-",
        print_solution(node.pointer)

def depth_first(start, goal):
    """
    深さ優先探索
    @param start: 探索開始ノード
    @param goal: 探索終了ノード
    """
    open = [start] #探索予定のノードのリスト
    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)
        j = 0
        for m in node.children:
            if m in open or m in closed:
                continue
            m.pointer = node
            if m == goal:
                open.insert(0, m)
            else:
                open.insert(j, m)
            j += 1
    if success:
        print "*** Solution ***"
        print_solution(goal)

if __name__ == "__main__":
    nodes = make_state_space()
    depth_first(nodes[0], nodes[-1])