启发式搜索

启发式搜索是人工智能一种搜索技术。启发式是一个经验法则，它可能导致一个解决方案。启发式在搜索策略中起着重要的作用，因为大多数问题都具有指数增长得性质。启发式有助于减少从指数数到多项式数的备选方案的数量。在人工智能中，启发式搜索具有普适化得意义，具有更具体的技术含义。在普适化意义上，术语“启发式”用于任何通常有效的建议，但不能保证在任何情况下都有效。然而，在启发式搜索体系结构中，启发式这个术语通常是指一个启发式评价函数的特殊情况。

为了解决较大的问题，必须增加特定领域的知识以提高搜索效率。关于这个问题的信息包括原始状态、从一个状态转变到另一个状态的成本以及目标节点。这些信息通常用启发式评价函数的形式表示，如f（n，G），节点n和/或目标g的函数。

下面是启发式算法例子.

• Pure Heuristic Search
• A* algorithm
• Iterative-Deepening A*
• Depth-First Branch-And-Bound
• Heuristic Path Algorithm
• Recursive Best-First Search

所有的搜索方法在前面的部分是未知的,他们不知道目标是哪一个。他们不使用任何关于要去哪里得信息，除非他们碰巧偶然遇到一个目标。一种关于启发式信息的启发式函数h(n)，它用来评价哪些节点最有希望的是一个我们要找的节点,这里n为节点,h(n)会返回一个非负实数,也可以认为是从节点n的目标节点路径的估计成本。如果h(n)是小于或等于实际成本最低成本路径节点n的目标，那么函数h(n)是低估了的，也是可用的（h函数一定要小于等于实际成本）。启发式函数是一种告知搜索方向的方法。它提供了一种明智的方法来猜测哪个邻居节点会导向一个目标。

启发式函数没有什么神奇之处。它必须只使用可以容易获得的关于节点的信息。通常情况下，为一个节点推导一个启发式值所需的工作量和一个节点的启发式值如何从节点到目标的实际路径开销是需要权衡的。推导启发式函数的一种标准方法是求解一个简单的问题，并将简化问题中的实际成本作为原问题的启发函数。

启发式搜索算法的时间复杂度取决于启发式函数的准确性。例如，如果启发式评价函数是一个精确估计，那么A*搜索算法在线性时间内运行，只在最优解路径上扩展这些节点。相反，用启发式算法返回零，A*算法成为统一的成本搜索，具有指数复杂性。

一般来说，A*搜索和IDA *搜索的时间复杂度是启发式函数中误差的指数函数。例如，如果启发式具有恒定的绝对误差，也就是说，无论估计值的大小如何，它都不会超过一个常量，那么，A*的运行时间与求解成本是线性的。更现实的假设是恒定相对误差，这意味着误差是估计量的固定百分比。然而，启发式搜索的指数的基数小于暴力搜索指数因子，减少了渐近复杂性，并允许解决更大的问题。例如，使用适当的启发函数，IDA *可以最佳地解决二十四个谜题和魔方的随机例子。

例题分析

对于图3.2，可以用节点与目标位置之间的直线距离作为启发函数。

下面的示例假定如上启发式函数：

这个h函数是低估的，因为h值小于或等于从节点到目标的最低成本路径的精确成本。节点O123确切的成本。节点b1非常低估，这似乎是接近，但只有一个漫长的路线的目标。这对c1很有误导性，它似乎也接近目标，但是从那个节点到目标并没有路径。

例题分析

考虑示例3.2的运送机器人，其中状态空间包括要递送的包裹。假设成本函数是机器人传送所有包裹的总距离。一个可能的启发式函数是包裹从目的地到目的地的最大距离。如果机器人只能携带一个包裹，那么一个可能的启发函数是包裹必须携带时的距离之和。如果机器人能同时携带多个包裹，这可能就不是一个低估实际成本。

h函数可以扩展到适用于（非空）路径。路径的启发式值是路径末端的节点的启发式值。就是：

启发式函数的简单用法是，将排序的邻居节点依次添加到堆栈中，这表示深度优先搜索的边界。可以将邻居添加到边界，以便首先选择最佳邻居。这就是所谓的启发式深度优先搜索。此搜索选择局部最佳路径，但它在选择其他路径之前从所选路径中探索所有路径。

使用启发式函数的另一种方法是总是在具有最低启发式值的边界上选择一条路径。这叫做最佳优先搜索。它通常不太好；它可以遵循看似有希望的路径，因为它们接近目标，但路径的成本可能会不断增加。

示例如下：考虑图3.8所示的曲线，其中弧的成本是其长度。其目的是找到最短路径从S到G。假设欧氏距离目标G被用作启发函数。启发式深度优先搜索将选择s以下的节点，并且永远不会终止。类似地，因为s下面的所有节点看起来都很好（红色的节点），最好的第一个搜索将在它们之间循环，从不尝试从S的备用路径。而比较好的搜索方式是绿色的节点。

【出处：Atificial Intelligence，URL：http://artint.info/html/ArtInt_56.html]

发展历史

描述

19世纪，法国数学家查尔斯·皮埃尔·特雷莫(Charles Pierre Tremaux)对深度优先搜索Depth-first search (DFS)的一个版本进行了研究，认为这是一种解决迷宫的策略。BFS( Breadth-first search )和它在寻找图形的连接部分的应用是由Michael Burke和Konrad Zuse在1945年发明的。Edsger Dijkstra在1959年在ARMAC计算机上写出了Dijkstra算法，它来搜索最短路径的算法，只使用f(p)=cost(p)。

在1968年，人工智能研究员尼尔斯·尼尔森(Nils Nilsson)试图改进机器人Shakey所做的路径规划，这个机器人原型可以通过在一个包含障碍物的房间进行导航。这种寻路算法，Nilsson称之为A1，是当时最著名的Hans Berliner于1979算法的更快版本，用于在图中找到最短路径。Bertram Raphael建议对这个算法进行一些重要的改进，并调用了修改后的A2。然后Peter E. Hart引入了一个论证，建立了A2，只有微小的变化，才能成为寻找最短路径的最佳算法。此时A星算法使用的评价函数是f(p)=cost(p)+h(p).

B*(发音为“B星”)是一种最佳的图形搜索算法，它从给定的初始节点到任何目标节点(在一个或多个可能的目标中)找到最小成本路径。由Hans Berliner于1979年首次出版。

1985 Richard Korf Iterative deepening A* (IDA*)是一种图遍历和路径搜索算法，它可以在一个加权图中找到指定的起始节点和一组目标节点的任何成员之间的最短路径。它是迭代深化深度优先搜索的一个变体，它借用了一个启发函数来评估剩余的成本，以从a *搜索算法获得目标。由于它是深度优先的搜索算法，它的内存使用率低于A*，但与普通的迭代深化搜索不同，它专注于探索最有希望的节点，因此不会访问。与A*不同，IDA*不使用动态编程，因此经常会多次访问相同的节点。

Russell, S. (1992)SMA*Simplified Memory Bounded A*或简化内存有界A*是基于A*算法的最短路径算法。SMA的主要优点是它使用有界内存，而a *算法可能需要指数内存。SMA的所有其他特征都是从一个A*继承的。

下图是对经典的搜索算法进行总结：

深度优先法在空间上与探索的路径长度成线性关系，但如果存在，则不保证找到解决方案。宽度优先算法，成本最低第一，A*可能是在空间和时间是指数，但他们保证找到一个解决方案，如果存在，即使图是无限的。

Lowest-cost-first和A*搜索保证找到第一个解决方案的最低成本解决方案。

主要事件

发展分析

瓶颈

一个正确的贪心算法拥有很多优点，比如思维复杂度低、代码量小、运行效率高、空间复杂度低等，是信息学竞赛中的一个有力武器。缺点：贪心法的缺点集中表现在他的“非完美性”。通常我们很难找到一个简单可行并且保证正确的贪心思路，即使我们找到一个看上去很正确的贪心思路，也需要严格的正确性证明。这往往给我们直接使用贪心算法带来了巨大的困难。

未来发展方向

其实搜索算法一直是最优值和复杂度之间的权衡，也是大家一直研究的问题。目前也已经有很多成熟的搜索算法可以直接运用。搜索算法可以分为四类，大家可以根据不同的类型对它们进行研究：1.为了虚拟搜索空间的算法，比如 minimax algorithm, alpha–beta pruning；2.对于给定结构的子结构，如Dijkstra's algorithm, Kruskal's algorithm, the nearest neighbour algorithm, and Prim's algorithm；3.搜索功能的最大值；4.量子计算机, 比如 Grover's algorithm。

Contributor: Ruiying Cai