人工智能中启发式搜索研究综述
DOI:10.11907/rjdk.191017 开放科学(资源服务)标识码(OSID):
人工智能诞生于20世纪中期，曾经历两起两落的重要历程。
人工智能技术作为21世纪最前沿技术之一，其重大突破必将影响新一轮产业革命，目前它已在医学、教育、研究等领域得到了深远应用。
目前，人工智能面临的问题越来越复杂，其中以非结构化问题居多，以往盲目搜索需要搜索所有节点消耗了大量时间，这种弊病将会严重限制搜索能力，究其原因在于顾及了所有可能性，即一个一个盲目搜索。
针对该问题，人们需要运用有知识的生成器避免走一些明显不可能搜索到正确答案的路径，即启发式搜索。
启发式搜索已成为实际中求解智能规划问题的重要工具，特别是不确定性规划问题。
近年来，放松规划在图规划问题中的探究、基于单值变量的启发式研究等均推动着对启发式搜索的探索。
用启发式搜索思维构建问题解成为一种常用的思考方式，比如最大权独立集问题、普遍共享骑行问题等。
启发式搜索结合模糊逻辑、频谱频率分配等领域技术更是加快了众多领域搜索发展的进程。
归根究底，人们还是希望搜索路径沿着自己认为有希望的方向前进，这样就可以大大减少搜索时间。
本文首先追溯研究起点，再从源头到人机大战应用对启发式搜索及其启发能力等进行探讨。
启发式搜索，简而言之，即一种运用启发先验知识或者信息引导搜索方向的方法。
为了评价启发式搜索的质量和效率，文中给出如下几个定义:
定义1搜索代价函数
指算法在一次启发式搜索过程中，从搜索起点S(Start.point)到达目标点D(Destination)所耗费的代价(如距离等)。
如果H*(p)的值与真实值存在较大偏差，可能引导节点向相对错误的方向搜索。
于是给出如下定义:
定义2可被接受的启发搜索
由此继续给出如下定义:
定义3搜索算法单调
算法单调虽然是理想目标，但是现实问题中一般较难达到这样苛刻的条件。
以下围绕搜索代价函数阐述几种不同的启发式搜索算法。
2 启发式搜索算法
2.1分支定界法
首先讨论一种特殊且简单的情况。
这种方法每次都会优先选择当前距离最短的路径前进，以最少距离为目标进行节点扩展。
这种方法也会抛弃一些不可能得到最优解的节点，以此达到缩短搜索路径距离的目标。
因为还可能存在其它路径的距离比16更小，于是继续扩展当前距离花费最小的C点(相等花费条件下遵守从右边开始扩展的规则)。
2.2 两种分支定界法改进方法
易知上述简单纯粹的分支定界法对H(p)处理上存在缺陷，故采用对H(p)低估值的方法改进分支定界法，即H*(p)=underestimate(H(p))。
显然，这种启发也是可以被接受的，同时比没有启发搜索能力的分支定界更强。
如图2所示，设矩形内的值表示该节点到目的地Goal的低估计值。
采用低估值的方法有效提高了搜索质量，更加符合实际情况，但是就其搜索速度而论并没有明显改观。
由现实生活经验可知，如果两条或多条路径到达同一节点，只需要存储距离消费最小的那条路径的距离即可。
通过一个抽象处理后的实例对原理加以说明。
这类似于动态规划，要记录下已经访问的节点，下次继续访问相同节点时，只需要在已经被访问的节点中查找到达某点的最小花费取出来使用即可。
虽然这种方法仅仅对到达同一节点的情况进行了优化，但也已在许多相关路径问题解决中见到它的缩影，如快递物流优选路径问题、城市路径规划问题等。
3 A*算法
上文对简单的分支定界法提出了两种优化策略，如果将两者优点结合起来就是A*算法。
另外，*号数码块与起点数码块状态相同，因此通过比较存储最短距离对路径进行优化。
由此还可以观察到，用曼哈顿距离作为搜索低估值时，有时收敛会更加快速。
其实，空格的上下左右移动类似于走弯弯折折似正方胡同的小巷，因此曼哈顿路径又称为出租车路径。
尽管A*算法已然是启发搜索能力较强的一种方法，但是在面对多条最小路径选择时有时也会存在因为搜索范围过大而导致搜索时间过长的缺点。
4 蒙特卡洛树搜索
人和机器在围棋中的较量比拼已是试验机器的试金石，其中核心部分便是蒙特卡洛树搜索。
该搜索建立于二人零和博弈基础上，其搜索基础是最大最小搜索。
最大最小搜索的中心思想是轮到我方搜索扩展时选择最有利于我方的扩展;轮到对方搜索扩展时选择最不利于我方的扩展。
最大最小搜索有两大明显缺点:①搜索树宽度太广，导致该树非常“胖”;②搜索树深度太深，导致该树非常长。
蒙特卡洛树搜索便是一种解决这两个问题的有效方法。
蒙特卡洛树中每个节点表示一种棋面，其搜索步骤如下:
启发函数:
选择启发函数最大值的点simax扩展。
从simax开始模拟接下来的输出，一直到零和博弈结束为止。
(4)回溯。
也称反向传播，用模拟的结果更新节点参数信息。
以上4个步骤反复迭代，一直到结束。
蒙特卡洛树搜索所用的启发知识不是固定的先验知识，而是通过搜索过程中模拟反向传播得到的带有概率的知识，具有及时性特征，非常符合围棋这一类多可能性且实时的特征，然而对于搜索树不是非常庞大的情况，比如象棋路径搜索，其效果就不如围棋好。
可以预见，有了更加高效且相对低成本的搜索策略，将对许多领域起到巨大推动作用。