图搜索策略与深度优先搜索的实现

摘要： 本文通过实例分析，指出，将智能控制学科中的图搜索策略与数据结构中深度优先搜索算法相结合，能够得到计算机完成图搜索过程的方法。

关键词： 智能控制 图搜索策略 深度优先搜索

智能控制是驱动智能机器自主地实现其目标的过程，或者说智能控制是一类无需人的干预就能够独立驱动智能机器实现其目标的自动控制。

每种以知识和符号作为基础的智能系统，其问题求解方法都需要某种对解答的搜索。在这一过程中，采用适当的搜索技术，包括各种规则、过程和算法等推理技术，力求找到问题的解答方法。

一、图搜索策略

要研究如何通过网络寻找路径，进而求解问题，首先介绍一下图搜索的一般策略，它给出图搜索过程的一般步骤，并可从中看出无信息搜索和启发式搜索的区别。

可把图搜索策略看成是一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。

图搜索（Graph Search）的一般过程如下：

1.建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中。

2.建立一个叫做CLOSED的已扩展节点表，其初始为空表。

3.LOOP：若OPEN表是空表，则失败退出。

4.选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。

5.若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的。

6.扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。

7.对那些未曾在G中出现过的（即未曾在OPEN表上或CLOSED表上出现过的）M成员设置一个通向n的指针。把M的这些成员加入OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。

8.按某一任意方式或按某个探试值重排OPEN表。

9.GO LOOP。以上搜索过程可用如下程序流程图来表示：

从图搜索过程可以看出，是否重新安排OPEN表，即是否按照某个试探值重新对未扩展节点进行排序，将决定该图搜索过程是无信息搜索或启发式搜索。

二、盲目搜索之深度优先搜索

不需要重排OPEN表的搜索叫做盲目搜索，深度优先搜索就是其中之一，下面介绍一下深度优先搜索：

假设初始状态是图中所有节点未曾被访问，则深度优先搜索可从图中某顶点v出发，在访问了v之后，依次从v的各个未曾访问过的邻接点进行深度优先遍历，直至图中所有和v有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的节点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。

例如，使用深度优先搜索来遍历图2，若出发点为v1，所得深度优先搜索序列为：v1，v2，v4，v8，v5，v3，v6，v7。

深度优先遍历的算法如下：

int visited［N］；

dfstraverse（list g，int ve）

{struct node*p；

visited［ve］=1；

printf（“%d”，ve）；

p=g［v］.next；

while（p）

{if（visited［p-＞vertex］==0）

dfstraverse（g，p-＞vertex）

p=p-＞next；

}

}

由此可见，深度优先搜索方法能够保证我们在搜索树中找到一条通向目标节点的最短路径，从而为解决图搜索问题提供了方法。

参考文献：

［1］蔡自兴.智能控制.电子工业出版社，2004.

［2］严蔚敏，吴伟民.数据结构.清华大学出版社，1997.

［3］秦玉平，马靖善.数据结构.清华大学出版社，2005.