search.py

from Queue import PriorityQueue

def backtrack(node, parent_map):
    """
    Accepts a search node and a map from nodes to nodes representing the parent node
    Returns a list of nodes that correspond to a path starting at start node and ending at given node
    """
    parent = parent_map[node]
    path = [node, parent] # assumes parent is not None
    while True:
        parent = parent_map.get(parent)
        if not parent:
            break
        path.append(parent)
    path.reverse()
    return path


def backtrack(node, parent_map):
    """
    Accepts a search node and a map from nodes to nodes representing the parent node
    Returns a list of nodes that correspond to a path starting at start node and ending at given node
    """
    path = [node] 
    while True:
        node = parent_map.get(node)
        if not parent:
            break
        path.append(node)
    path.reverse()
    return path



def ucs(problem):
    """
    Accepts a search problem ( https://gist.github.com/stuntgoat/5044357), 
    
    Returns a path to goal
    """
    pq = PriorityQueue()
    # step 1: start a initial state, put start state on the priority queue
    initial_state = problem.initial_state()
    pq.put((0, initial_state))

    parent_map = {}
    explored_nodes = set()    

    # while pq is not empty
    while not pq.empty():
        # remove an item from the queue
        priority_node, cur_node = pq.get()    
        if problem.goal_test(cur_node):
            return backtrack(cur_node, parent_map)

        # if not, acquire the list of actions for that state.
        actions = problem.actions(cur_node)  # [(2, node1), (4, node2)]
        # put them on the pqueue
        for action in actions:
            transition_cost, node = action
            parent_map[node] = cur_node
            if node in explored_nodes:
                continue
            pq.put((priority_node + transition_cost, node))
        # put state on the list of explored states    
        explored_nodes.add(cur_node)
    return "goal not found"
    
    
    
def a_star(problem, heuristic):
    """
    Accepts a search problem ( https://gist.github.com/stuntgoat/5044357), 
    and a heuristic function which is a function from nodes to real values
    
    Returns a path to goal
    """
    pq = PriorityQueue()
    # step 1: start a initial state, put start state on the priority queue
    initial_state = problem.initial_state()
    pq.put((0, initial_state))

    parent_map = {}
    explored_nodes = set()
    

    # while pq is not empty
    while not pq.empty():
        # remove an item from the queue
        cur_node = pq.get()
        # priority f(n) = g(n) + h(n)
        # h(n) = forward cost = heuristic(n)
        
        # suppose m is a child of n
        # f(n) = g(n) + h(n)  implies  g(n) = f(n) - h(n)
        # g(m) = g(n) + transition_cost(n, m)
        # f(m) = g(m) + h(m) = [g(n) + transition_cost(n, m)] + h(m)
        #->    f(m) = [[f(n) - h(n)] + transition_cost(n, m)] + h(m)
        # f is the priority on the pq
        # h is the heursitc function applied to a given node
        # transition_cost is given by the search problem
        priority_node = heuristic(cur_node)
        if problem.goal_test(cur_node):
            return backtrack(cur_node, parent_map)

        # if not, acquire the list of actions for that state.
        actions = problem.actions(cur_node)  # [(2, node1), (4, node2)]
        # put them on the pqueue
        for action in actions:
            transition_cost, node = action
            parent_map[node] = cur_node
            if node in explored_nodes:
                continue
            pq.put((priority_node + transition_cost, node))
        # put state on the list of explored states    
        explored_nodes.add(cur_node)
    return "goal not found"