算法介绍

算法 1：深度优先算法；
算法 2：宽度优先算法；
算法 3：代价一致算法；
算法 4：A* 算法；

通用搜索算法

算法1-4的不同之处在于用不同的数据结构进行排序。因此可以定义一个通用的搜索算法实现算法1-4，通过配置不同参数来实现DFS,BFS,UCS和A*搜索。

def genericSearchAlgorithm(problem, open_type):
    """
    param1: problem (搜索算法要解决的问题对象)
    param2: open_type (搜索算法中的open表采用的数据结构)
    return值: actions列表,即,吃豆人吃到豆子所执行的一个action序列
    """
    openTable = open_type()  # 数据结构
    # 将其实例化,创建open表
    openTable.push((problem.getStartState(), []))
    closed = []  # 初始化closed表为空表
    while True:
        if openTable.isEmpty():
            return []
        node,actions = openTable.pop()
        if problem.isGoalState(node):
            return actions
        if node not in closed:
            closed.append(node)
            for successor,action, stepCost in problem.getSuccessors(node):
                openTable.push((successor,actions+[action]))

DFS

深度优先搜索是最常见的搜索算法之一。DFS采用栈作为数据结构进行搜索路径，“先进后出”。

从起点出发，首先判断起点是否是目标节点，若是则返回目标节点。否则，搜索一条分支的所有结点，然后再去搜索其他分支。

首先判断节点是否是目标节点，若是则返回目标节点，否则压入栈中。若栈不为空，选择栈顶弹出的节点作为下一步的节点，依次类推，直至找到目标节点。若栈为空却未搜索到目标节点，则搜索失败。将通用搜索算法中的 open_type 设置为 util.Stack。

def depthFirstSearch(problem):
  return generalSearch(problem, util.Stack)

BFS

广度优先搜索是最常见的搜索算法之一。BFS采用队列作为数据结构进行搜索路径，“先进先出”。

从起点出发，首先判断起点是否是目标节点，若是则返回目标节点。否则，搜索该节点的邻居节点，
首先判断节点是否是目标节点，若是则返回目标节点，否则压入队列中。

若队列不为空，选择队列中的首节点作为下一步的节点，依次类推，直至找到目标节点。若队列为空却未搜索到目标节点，则搜索失败。将通用搜索算法中的 open_type 设置为 util.Queue。

def breadthFirstSearch(problem):
	return generalSearch(problem, util.Queue)

代价一致算法

代价一致搜索是宽度优先搜索的一种推广， 不是沿着等长度路径逐层进行扩展， 而是沿着等代价路径逐层进行扩展。

在代价树中，可以用g(n)表示从初始节点S0到节点 i的代价，用 c(i, n2)表示从父节点 i到 n2的代价,记g(n2) = g(i) + c(i, n2)。

把从起始节点S0到任一节点i的路径代价记为g(i)。从初始节点S0开始扩展，若没有得到目标节点，则优先扩展最少代价g(i)的节点，一直如此向下搜索。将通用搜索算法中的 open_type 设置为util.PriorityQueue。

def uniformCostSearch(problem):
	return generalSearch(problem, util.PriorityQueue, True)

A*算法

1. A*搜索是最佳优先搜索的一种形式，最先扩展f(n)最小的节点。

• f(n)是进过节点 n 的最小代价解的估计代价。

• A*算法的估算函数为 f(n) = g(n) + h(n)。g(n)是到达此节点花费的代价， h(n)是从该节点到目标节点需要花费的代价(的估计值)。

2. 将通用搜索算法的open_type设置为PriorityQueue,PriorityQueue设置为True,heuristic设置为heuristic，即可实现以曼哈顿距离为启发函数的A*算法。

def aStarSearch(problem, heuristic=nullHeuristic):
	return generalSearch(problem, util.PriorityQueue, True, heuristic)