Project 1: Search

前四问是依次实现 lecture 中讲过的depthFirstSearch，breadthFirstSearch, uniform cost search ，A* search。前两个差别只在于实现边界的数据结构一个是栈（先进后出）一个是队列（先进先出)。

def depthFirstSearch(problem: SearchProblem):
    fridge = util.Stack()
    fridge.push((problem.getStartState(), []))
    visited = set()
    while not fridge.isEmpty():
        curr_state, curr_path = fridge.pop()
        if problem.isGoalState(curr_state):
            return curr_path
        if curr_state not in visited:
            visited.add(curr_state)
            for next_state, action, cost in problem.getSuccessors(curr_state):
                new_path = curr_path + [action]
                fridge.push((next_state, new_path))
    return []

def breadthFirstSearch(problem: SearchProblem):
    fridge = util.Queue()
    fridge.push((problem.getStartState(), []))
    visited = set()
    while not fridge.isEmpty():
        curr_state, curr_path = fridge.pop()
        if problem.isGoalState(curr_state):
            return curr_path
        if curr_state not in visited:
            visited.add(curr_state)
            for next_state, action, cost in problem.getSuccessors(curr_state):
                new_path = curr_path + [action]
                fridge.push((next_state, new_path))
    return []

uos 是使用优先队列通过比较 priority 来选择谁先 pop 出队列。

def uniformCostSearch(problem: SearchProblem):
    fridge = util.PriorityQueueWithFunction(lambda a:problem.getCostOfActions(a[1]))
    fridge.push((problem.getStartState(), []))
    visited = set()
    while not fridge.isEmpty():
        curr_state, curr_path = fridge.pop()
        if problem.isGoalState(curr_state):
            return curr_path
        if curr_state not in visited:
            visited.add(curr_state)
            for next_state, action, cost in problem.getSuccessors(curr_state):
                new_path = curr_path + [action]
                fridge.push((next_state, new_path))
    return []

a* 则是在 uos 基础上 把 priority 替换为 f = g + h ，即已经走过路径的成本 加上 预估从此处到达目标路径的成本（通过启发式方法求得）。一个 admissible 的启发式方法，求得的 h 应该小于或等于实际成本，保证找到的解一定是最优解。同时，启发式方法还需要满足一致性，意思是 f 沿着路径应该不变或不断增大而不会减小，也就是每一步的预估成本都要小于或等于实际成本，保证第一次扩展某节点时，它的 g 已经最小。

def aStarSearch(problem: SearchProblem, heuristic=nullHeuristic):
    """Search the node that has the lowest combined cost and heuristic first."""
    fridge = util.PriorityQueueWithFunction(lambda a:problem.getCostOfActions(a[1]) + heuristic(a[0],problem))
    fridge.push((problem.getStartState(), []))
    visited = set()
    while not fridge.isEmpty():
        curr_state, curr_path = fridge.pop()
        if problem.isGoalState(curr_state):
            return curr_path
        if curr_state not in visited:
            visited.add(curr_state)
            for next_state, action, cost in problem.getSuccessors(curr_state):
                new_path = curr_path + [action]
                fridge.push((next_state, new_path))
    return []

后面几问主要考查的是目标状态函数、后继函数和启发式方法的编写，加深对 heuristic 的理解。通过不断接近真实成本，可以减少搜索中扩展的节点数量，提高效率。