摘要：本文简单阐述了人工智能中的智能搜索技术的概念以及启发式搜索算法，介绍了几种启发式搜索函数的选择及其研究中遇到的难题，并从中求解来探讨解决问题的思路。

关键词：智能搜索；状态空间；与/或树；博弈树；启发式搜索

1.搜索的含义

人工智能研究的对象大多是属于结构不良或非结构化的问题。对于这些问题，一般很难获得其全部信息，更没有现成的算法可供求解使用，因此只能依靠经验，利用已有知识逐步摸索求解。像这种根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索。

搜索算法可根据其是否采用智能方法分为盲目搜索算法和智能搜索算法，本文重点讲述的是智能搜索算法。

智能搜索算法是指可以利用搜索过程得到的中间信息来引导搜索过程向最优方向发展的算法。根据基于的搜索机理，这种算法可以分为多种类型。例如，基于搜索空间的状态空间启发式搜索、与/或树启发式搜索及博弈树启发式搜索，基于生物演化过程的进化搜索算法，基于物理退火过程的模拟退火算法等。[1]

2.启发式搜索

2.1状态空间的启发式搜索

       基于状态空间的路径搜索,即将问题求解过程表现为从初始状态到目标状态寻找路径的过程,普通应用于各个领域。基于状态空间的路径搜索算法通常可分为3类:深度优先搜索算法、宽度优先搜索算法(或称广度优先搜索算法)和启发式搜索算法。前两种算法均需在给定的状态空间中穷举,以求解中最佳路径,其非常适合状态空间不大时的求解,但当状态空间十分大,且不预测的情况下,他们的效率极低,甚至不可完成。而启发式搜索算法在状态空间搜索时,对每一个搜索的节点进行评估,得到最佳的节点,再从这个节点进行搜索直到目标节点,可省略大量无谓的搜索路径,极大提到效率,这使得其在状态空间较大的领域得到了广泛应用,如自驾车路线、网络传输路径、游戏中角色行走路线等。[2]

      A*搜索算法是一种加上一些约束条件的最好优先的算法。当状态空间较大时,希望能够求解出状态空间搜索的最短路径,即用最快的方法求解问题,A*搜索算法正是基于这种思想。

如果一个估价函数可以找出最短的路径,称之为可采纳性。A*搜索算法是一个可采纳的最好优先算法。A*搜索算法的估价函数可表示为:

这里面的的附加条件为为n到目标的直线最短距离，也就说A*算法中挑选的启发函数是最优的，也正是如此，所找到的路径是最短路径。[3]

2.2与/或树启发式搜索

       希望树是指搜索过程中最有可能成为最优解树的那棵树。与/或树的启发式搜索过程就是不断地选择、修正希望树的过程，在该过程中，希望树是不断变化的。它需要符合以下三个条件：

1.初始结点S0在希望树T

2.如果是具有子结点, , … , 的或结点，则n的某个子结点在希望树T中的充分必要条件是如果是与结点，则n的全部子结点都在希望树T中。

3. 如果n是与结点，则n的全部子结点都在希望树T中。

2.3博弈树启发式搜索

       博弈是一类具有智能行为的竞争活动，如下棋、战争等。双人完备信息博弈就是两位选手（例如MAX和MIN ）对垒，轮流走步，每一方不仅知道对方已经走过的棋步，而且还能估计出对方未来的走步。若把双人完备信息博弈过程用图表示出来，就得到一棵与/或树，这种与/或树被称为博弈树。在博弈树中，那些下一步该MAX走步的结点称为MAX结点，下一步该MIN走步的结点称为MIN 结点。博弈树的特点是

（1）博弈的初始状态是初始结点；

（2）博弈树中的“或”结点和“与”结点是逐层交替出现的；

（3）整个博弈过程始终站在某一方的立场上，例如MAX方。所有能使自己一方获胜的终局都是本原问题，相应的结点是可解结点；所有使对方获胜的终局都是不可解结点。[4]

3.问题实现：滑动积木游戏启发式搜索函数

滑动积木块游戏的棋盘结构及某一种将牌的初始排列结构如下:

其中B表示黑色将牌，W表示白色将牌，E表示空格。游戏的规定走法是:

(1)任意一个将牌可以移入相邻的空格，规定其耗散值为1;

(2)任意一个将牌可相隔1个或2个其他的将牌跳入空格，规定其耗散值等于跳过将牌的数目;游戏要达到的目标是使所有白将牌都处在黑将牌的左边(左边有无空格均可)。对这个问题，定义一个启发函数h(n),并给出利用这个启发函数用算法A求解时所产生的搜索树。可定义h为: h= B右边的W的数目

很多知识对求解问题有好处，这些知识并不一定要写成启发函数的形式， 很多情况下，也不一定能清晰的写成一个函数的形式。由题意，在目标状态下，一个扇区的数字之和等于12，一个相对扇区的数字之和等于24，而一个阴影扇区或者非阴影扇区的数字之和为48。

为此，我们可以将目标进行分解，首先满足阴影扇区的数字之和为48。为了这个目标我们可以通过每次转动圆盘45o实现。在第一个目标被满足的情况下， 我们再考虑第二个目标:每个相对扇区的数字和为24。在实现这个目标的过程中，我们希望不破坏第一个目标。 为此我们采用转动90o的方式实现，这样即可以调整相对扇区的数字和，又不破坏第一个目标。 在第二个目标实现之后，我们就可以实现最终目标:扇区内的数字和为12。同样我们希望在实现这个目标的时候，不破坏前两个目标。为此我们采用转动180o的方式实现。这样同样是即可以保证前两个目标不被破坏，又可以实现第三个目标。

经过这样的分析以后，我们发现该问题就清晰多了。当然，是否每一个第一、第二个目标的实现，都能够实现第三个目标呢?有可能不一定。在这种情况下，就需要在发现第三个目标不能实现时，重新试探其他的第一、第二个目标。

参考文献：

[1] 曹松.基于两种智能搜索算法的无线传感器网络节点定位技术[C].华东理工大学,2013.

[2] 张胜.一种基于状态空间的启发式搜索算法及其实现[J].现代电子技术,2008,(16):79-80+83.

[3] 胡书丽.启发式搜索算法求解组合优化问题的研究[C].东北师范大学,2019.

[4] 张聪品;刘春红;徐久成.博弈树启发式搜索的α-β剪枝技术研究[J].计算机工程与应用,2008,(16):54-55+97.