search.py 文件源码

def breadthFirstSearch(problem):
    """Search the shallowest nodes in the search tree first."""

    loc_queue = Queue()
    visited_node = {}
    parent_child_map = {}
    direction_list = [] 

    start_node = problem.getStartState()
    parent_child_map[start_node] = []
    loc_queue.push(start_node)

    def traverse_path(parent_node):
        while True:
            map_row = parent_child_map[parent_node]
            if (len(map_row) == 2):
                parent_node = map_row[0]
                direction = map_row[1]
                direction_list.append(direction)
            else:
                break       
        return direction_list

    while (loc_queue.isEmpty() == False):

        parent_node = loc_queue.pop()

        if (problem.isGoalState(parent_node)):
            pathlist = traverse_path(parent_node)
            pathlist.reverse()
            return pathlist

        elif (visited_node.has_key(parent_node) == False):
            visited_node[parent_node] = []            
            sucessor_list = problem.getSuccessors(parent_node)
            no_of_child = len(sucessor_list)
            if (no_of_child > 0):          
                temp = 0
                while (temp < no_of_child):
                    child_nodes = sucessor_list[temp]
                    child_state = child_nodes[0];
                    child_action = child_nodes[1];
                    if (visited_node.has_key(child_state) == False):
                        loc_queue.push(child_state)
                    if (parent_child_map.has_key(child_state) == False):
                        parent_child_map[child_state] = [parent_node,child_action]
                    temp = temp + 1