《人工智能》搜索技术迷宫问题搜索的挑战—组合爆炸数码问题4.1状态图概念农夫过河问题农夫过河问题状态空间法表示（1，0，0，1）4.2状态空间法状态空间表示的概念三数码难题1状态图搜索状态图搜索—相关问题图搜索策略OPEN表CLOSED表开始按搜索轨迹分类搜索树的概念（1，0，0，1）由于搜索具有探索性，所以要提高搜索效率(尽快地找到目标节点)，或要找最佳路径(最佳解)就必须注意搜索策略。对于状态图搜索，已经提出了许多策略，它们大体可分为盲目搜索（blandsearch)和启发式搜索（heuristicsearch）两大类。盲目搜索是无向导搜索。启发式搜索是有向导搜索，即利用启发信息（函数）引导去寻找问题解。盲目搜索图搜索策略宽度优先搜索策略开始宽度优先搜索算法例子八数码难题（8-puzzleproblem）1宽度优先搜索(Breadth-FirstStrategy)宽度优先搜索(Breadth-FirstStrategy)宽度优先搜索(Breadth-FirstStrategy)宽度优先搜索(Breadth-FirstStrategy)宽度优先搜索(Breadth-FirstStrategy)宽度优先搜索(Breadth-FirstStrategy)宽度优先搜索(Breadth-FirstStrategy)深度优先搜索策略深度优先算法框图深度优先搜索算法深度优先搜索(Depth-FirstStrategy)Depth-FirstStrategyDepth-FirstStrategyDepth-FirstStrategyDepth-FirstStrategyDepth-FirstStrategyDepth-FirstStrategyDepth-FirstStrategyDepth-FirstStrategyDepth-FirstStrategyDepth-FirstStrategy代价树搜索算法使用符号开始等代价搜索算法宽度优先等代价搜索算法启发式搜索启发信息启发式搜索就是利用启发性信息进行制导的搜索。启发性信息就是有利于尽快找到问题之解的信息。按其用途划分，启发性信息一般可分为以下三类：(1)用于扩展节点的选择，即用于决定应先扩展哪一个节点，以免盲目扩展。(2)用于生成节点的选择，即用于决定应生成哪些后续节点，以免盲目地生成过多无用节点。(3)用于删除节点的选择，即用于决定应删除哪些无用节点，以免造成进一步的时空浪费。重排OPEN表，使搜索沿某个被认为最有希望的路径扩展。应用这种排序过程，需要某些估算节点“希望”的量度。用来估算节点希望程度的量度，叫做估价函数（evaluationfunction），有时也叫作启发函数。一个节点的“希望”（promise）有几种不同的定义方法。在状态空间问题中，一种方法是估算目标节点到此节点的距离；估算全路径的长度或难度（包括此节点）。我们用符号f来标记估价函数，用f（n）表示节点n的估价函数值。如何定义一个估价（启发）函数呢？估价（启发）函数并无固定的模式，需要具体问题具体分析。通常可以参考的思路有：（1）一个节点到目标节点的距离或差异的度量；（2）一个节点处在最佳路径上的概率；（3）或者根据经验的主观打分。八数码难题（8-puzzle）f3(T)=不在目标位置的字码距离目标位置水平距离和垂直距离之和。该函数给出了一个更好的距离评估启发式搜索算法启发式搜索要用启发函数来导航，其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。两种策略:局部择优搜索扩展节点N后仅对N的子节点按启发函数值大小以升序排序，再将它们依次放入OPEN表的首部。全局择优搜索在OPEN表中保留所有已生成而未考察的节点，并用启发函数h(x)对它们全部进行估价，从中选出最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。全局择优搜索算法全局择优搜索例子局部择优搜索算法局部搜索算法爬山法（Hillclimbing）启发式搜索:A算法启发式搜索:A算法启发式搜索:A算法启发式搜索:A算法八数码难题（8-puzzleproblem）八数码难题:评价函数5启发式搜索:A*算法启发式搜索:A*算法A*算法的定义具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件为什么A*算法低估h值为什么A*算法低估h值为什么A*算法低估h值f1启发式搜索算法A*八数码难题:八数码难题举例RobotnavigationRobotNavigationRobotNavigationRobotNavigationRobotNavigation搜索算法小结复习讨论八数码难题（8-puzzleproblem）用