【人工智能】盲目搜索与启发式搜索

最开始，我们要讲清楚——搜索就是找到智能系统的动作序列的过程。我们把实际问题形式化为从起点寻找一条路径到达终点的问题，这就是搜索算法存在的意义。

如何形式化一个搜索问题

对于一个search problem，我们用下面五项形式化定义：
• 初始状态 initial state
• 行动 Actions
• 转移模型 transition model
• 目标测试 goal test
• 路径耗散 path cost

对于问题的解（solution），我们有如下定义：
A solution to a problem is an action sequence that leads from the initial state to a goal state.
也就是说，一个问题的解是一个行动序列。

盲目搜索

提到盲目搜索，我们常常会有：
• 宽度优先搜索
• 一致代价搜索
• 深度优先搜索
• 深度受限搜索
• 迭代加深搜索
• 双向搜索

深度优先搜索（DFS）通过栈实现，每次从栈顶取出状态，并出栈。每个状态拓展出的状态放入栈顶，直到找到目标状态。在DFS过程中，若新拓展的状态存在于当前路径中，则不需要拓展，称为路径检测。消耗的空间正比于路径长度，比BFS更优。
• 算法流程图

宽度优先搜索（BFS）通过队列实现。每次从队头取出状态，并出队。每个状态拓展出的状态放入队尾，直到找到目标状态，利用了队列先进先出的特性。状态转移代价都相同时能保证求出最优解。消耗的空间正比于拓展出的状态数。
• 算法流程图

迭代加深搜索的前提是题目要有解。它首先深度优先搜索k层，若没有找到可行解，再深度优先搜索k+1层，直到找到可行解为止。比较像DFS和BFS二者的融合。
• 算法伪代码

function Depth-Limited-Search(problem, limit)
 if problem.Goal-Test(node.State) then return Solution(node)
 if limit = 0 then return cutoff    //no solution
 cutoff_occurred? <- false
    for each action in problem.Action(node.State) do
     child <- Child-Node(problem, node, action)
        result <= Recusive-DLS(child, problem, limit - 1)
        if result = cutoff then cutoff_occurred ? <- true
        else if result ≠ failure then return result
    if cutoff_occurred ? then return cutoff    //no solution
 else return failure

fuction Iterative-Deepening-Search(problem, limit)
 for depth = 0 to ∞ do
     result <- Depth-Limited-Search(problem, limit)
        if result ≠ cutoff then return result

一致代价搜索指在BFS基础上，将队列改为优先队列，每次从队列中选出目前代价最小的节点拓展，在转移代价非负时能保证求出最短路径。一致代价搜索时，若拓展到的节点已经被拓展（即新子节点的最优代价更小）则该次拓展不会贡献答案，可以不执行，称为环检测。

启发式搜索

启发式搜索又叫有信息的搜索，它利用问题所拥有的启发信息来引导搜索，达到减少搜索范围，降低问题复杂度的目的。

无信息搜索对所有可能路径节点一视同仁，而启发式搜索可以指导搜索向最有希望的方向前进。

为了评估一个节点的重要性，我们有估价函数。设初始状态为S，目标状态为T。定义状态x的估计函数 f(x) = h(x) + g(x)。启发式函数h(x)为由x到T最短路径长度的估计值，g(x)为由S到x目前路径的长度。

在估价函数中，启发式函数h(x)的设计非常重要，它建模了启发式搜索问题中的启发信息，是算法的关键，合理的定义才能让搜索算法找到一个最优的问题解。

下面我们谈到A*搜索算法和IDA*（迭代加深A*）搜索算法。

A*算法可以看作是BFS算法的升级版，在原有的BFS算法的基础上加入了启发式信息。
• 算法描述
从起始节点开始，不断查询周围可到达节点的状态并计算它们的 f(x),h(x)与g(x)的值，选取估价函数f(x)最小的节点进行下一步扩展，并同时更新已经被访问过的节点的g(x)，直到找到目标节点。
• 算法优缺点
拥有BFS速度较快的优点，但是因为它要维护“开启列表”以及“关闭列表”，并且需要反复查询状态。因为它的时间复杂度是指数级的。
• 算法步骤
开始
1.从起点开始，把其当成待处理点存入一个“开启列表”。
2.搜寻起点周围可能通过的节点，也把它们加入开启列表，为这些节点计算f(x)，g(x)h(x)，并且将节点A存为“父节点”。
3.从开启列表中删除节点A，将其加入“关闭列表”(列表中保存所有不需要再次检查的节点)。
循环直到找到目标节点或者“开启列表”为空(无路径)
4.从“开启列表”中找到估价函数值最低的节点C，并将它从“开启列表”中删除，添加到“关闭列表”中。
5.检查C所有相邻节点，将其加入“开启列表”，将C作为它们的父节点。
6.如果新的相邻节点已经在“开启列表”，则更新它们的g(x)值
• 算法流程图

IDA算法是迭代加深深度优先算法（IDS）的扩展。因为它不需要去维护表，因此它的空间复杂度远远小于A。在搜索图为稀疏有向图的时候，它的性能会比A*更好。
• 算法描述
在算法迭代的每一步，IDA*都进行深度优先搜索，在某一步所有可访问节点对应的最小可估价函数值大于某个给定的阈值的时候，将会剪枝。
• 算法优点
当问题要求空间复杂度比较低的时候，IDA*更有优势。
• 算法步骤
对于给定的阈值bound，定义递归过程
1.从开始节点C，计算所有邻居节点的估价函数，选取估价函数最小的节点作为下一个访问节点。
2.对于某个节点，如果估价函数大于阈值，则返回当前节点的估值函数值。
3.对于某个节点，如果是目标节点，则返回状态"到达”。
• 算法伪代码

function h():  //启发式函数

function IDA_search(node, g, bound):  //node为当前节点，g为当前节点的路径消耗，bound为阈值
    f = g + h(node)
    if f > bound:
        return f
    if node == E:  //E为终点
        return FOUND
    min = r
    for succ in successors(node) do:
        t = search(succ, g + cost(node, succ), bound)
    if t == FOUND:
        return FOUND
    if t < min: 
        min = t
    return min

bound = h(A)
while(True):
    t = IDA_search(root, 0, bound)
    if t == FOUND:
        return bound
    if t = ∞:
        return NOT_FOUND
    bound := t

【编程任务一】盲目搜索算法实现

以下类型一两种都要实现，类型二选择一个实现。
类型一： BFS、 DFS
类型二：一致代价、迭代加深、双向搜索
• 报告要求：报告中①需要有对实现的策略的原理解释，②需要策略的实验效果（四个方面的算法性能）的对比和分析，③以及自己对不同策略优缺点，适用场景的理解和认识。

S表示起点，E表示终点。1表示墙，0是可通行。
参考代码

【编程任务二】启发式搜索算法实现

使用A与IDA算法解决15-Puzzle问题，启发式函数可以自己选取，最好多尝试几种不同的启发式函数
• 报告要求
①报告中需要包含对两个算法的原理解释
②需要包含性能和结果的对比和分析
③如果使用了多种启发式函数，最好进行对比和分析
④（可选）分情况分析估价值和真实值的差距会造成算法性能差距的原因
基本样例：

启发式搜索基本样例1

启发式搜索基本样例2

启发式搜索基本样例3

启发式搜索基本样例4
挑战性样例：

启发式搜索挑战样例1

启发式搜索挑战样例2
参考代码