旅行商问题的人工智能算法应用研究

摘要：本文是用人工智能中的深度优先算法、宽度优先算法、A*算法、SMA*算法来解决N城市旅行商问题。通过解决路径、耗散值、运行时间等数据比较这几个算法在处理该问题上的优劣。

关键字：旅行商问题；深度优先算法；宽度优先算法；A*算法；SMA*算法

中图分类号：TP312文献标识码：A文章编号：1009-3044(2007)03-10817-02

1 引言

旅行商问题是图论中的一个重要的经典问题：任给一个城市与城市间的道路图，求一个旅行商访问每个城市并回到出发点的最短路程。

例如，城市间均有道路的五个城市的地图可以表示成下面的图1：

图1 城市间均有道路的五个城市的地图

在旅行商的地图中，五个城市用节点表示，两城市间的距离用弧线上的数字表示。设旅行商从A城市出发，到B、C、D、E等城市去推销商品，要寻找一条从A出发，包括B、C、D、E，且仅包含一次，最后回到A的一条最短路径。

为了比较人工智能中的深度优先算法、宽度优先算法、A*算法、SMA*算法在处理N城市旅行商问题上优劣，我们用编程实现这几种算法对N城市旅行商问题的运算，并且得出解决路径、耗散值、运行时间等输出结果。通过这些数据我们可以看出这几种算法在该问题上的表现，并从中比较这几个算法在该问题上的优劣。

2 算法的研究

2.1深度优先算法

深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。

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

以下图2中无向图G4为例，深度优先搜索遍历图的过程如图3所示：

假设从顶点v1出发进行搜索，在访问了顶点v1之后，选择邻接点v2。因为v2未曾访问，则从v2出发进行搜索。依次类推，接着从v4、v8、v5出发进行搜索。在访问了v5之后，由于v5的邻接点都已被访问，则搜索回到v8。由于同样的理由，搜索继续v4，v2直至v1，此时由于v1的另一个邻接点未被访问，则搜索又从v1到v3，再继续进行下去。由次，得到的顶点访问序列为：

显然这是一个递归的过程。

2.2宽度优先算法

宽度优先搜索遍历类似于树的按层次遍历的过程。

假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问他们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，宽度有限搜索遍历图的过程是以v为起始点，有近至远，依次访问和v有路径相通且路径长度为1，2，…的顶点。

例如对图G4进行宽度优先搜索遍历的过程如图4所示：

图4 宽度优先搜索遍历过程

首先访问v1和v2的邻接点v2和v1，然后依次访问v2的邻接点v4和v5及v3的邻接点v6和v7，最后访问v4的邻接点v8。由于这些顶点的邻接点均已被访问，并且图中所有顶点都被访问，由此完成了图的遍历。得到的顶点访问序列为：2.3 A*算法

A*算法是N.Nillson于1971年提出的一种有序搜索算法，该算法被认为是求解人工智

能问题的最成功的技术理论之一。

Nillson指:出对于某一已到达的现行状态，如已到达图中的n节点，它是否可能成为最佳路径上的一点的估价，应由估价函数f(n)值来决定。

假设g*(n)函数值表示从起始节点s到任意一个节点n的一条最佳路径上的实际耗散值。h*(n)函数值表示从任意节点n到目标节点ti的最佳路径的实际耗散值。其中ti是一个可能的目标节点。f*(n)函数值表示从起始s，通过某一指定的n到达目标节点ti的一条最佳路径的实际耗散值，并有 f*(n)=g*(n)+h*(n)。

假设f函数是对f*函数的一种估计，并有 f(n)=g(n)+h(n)，其中，g函数是对g*的估计，h函数是对h*的一种估计。f（n）包括两个部分，其中g(n)表示到达n节点时，已付出代价的估计；而h(n)表示从n节点到达目标节点ti将要付出代价的估计。

按f(n)=g*(n)+h*(n)的值来排序OPEN表的节点，f值小者优先。通常称这种算法为A

算法。在A算法的基础上，进一步限制h(n)函数，使得搜索图中的每一个节点n，能满足h(n)

2.4 SMA*算法

SMA*算法是建立在A*基础上的一种新算法，相对于A*算法而言，该算法的不同之处在于每次进入OPEN表只新增一个节点，优先扩展那些已经有子节点,且节点深度较小的节点，如果有扩展,记住被扩展节点的值。扩展一个点后重新计算父节点的估计值。由于该算法和A*算法原理相通，所以不再作进一步分析。

3 模型的建立

3.1 状态描述和状态空间

所谓状态，是指在一定的时空范围内，问题所涉及的人、物、时间等的布局关系。通常把问题的初始布局关系称为初始状态，问题解决时到达的状态叫目标状态。这两个状态之间存在差异，如何从初始状态到达目标状态就是对问题求解。

在求解过程中可能到达的所有状态统称为状态空间。包括初始状态、中间状态、目标状态。在状态空间法中问题的求解通常是从初始状态到达目标状态的一条最佳路径，这条路径依靠搜索算法在状态空间中寻找，这就是状态空间法的核心所在。

3.2 产生式系统是状态空间法的基本系统结构

一个产生式系统模型包括三个基本的组成部分，即一个综合数据库，一组产生式规则和一个控制系统，通常称为产生式系统的三个基本要素。产生式系统的工作过程如图5：

图5 产生式系统的工作过程

3.3 以A*算法为例对旅行商问题的解决方法

图6给出了旅行商问题的旅程表。两城市间的距离用数字表示，其中最小距离为5。

设旅行商已从A城市到达了C城市，现行状态描述为（A，C），即状态表中已有两个元素。下一步是到B、还是D、E则要看f(B)、f(D)、f(E)的大小，小者优先。

关键是各后继节点h函数的估价值如何计算。

从上图还可以看出，无论下一步是到B、到E还是到D，旅行商都是已到过三个城市，即现行状态表的元素数均为3，与目标状态相比，还有3个城市没有去，包括最后回到A城市。

如果我们假设剩下的3个城市间的平均距离等于最小距离5，则从B或从E、D到达目标状态将要付出的代价不会小于3*5=15，即至少还要走3*5=15的距离，这就是h函数的估价值，即 h(B)=15

由此得出，旅行商下一步由C城市走到E城市。所设置的h函数可用下式表示：

h=(目标状态表的元素数―现行状态表的元素数)*K

K是一个系数，如K取两城市间的最小问题。所设置的h，满足h

图8给出了五城市旅行商问题的一个部分搜索图：

图8 五城市旅行商问题的一个部分搜索图

(图中节点旁两个数字，前一个为f(n)估计值，后一个表示扩展的先后顺序)

其中K=6，仍能满足hB―>D―>C―>E―>A.该路径的f*=35。

4结果分析

分别以5城市、8城市、10城市输入数据进行运算，经过比较，可以发现以下几点：

(1)A*算法、宽度优先算法和SMA*算法在运算结果上是统一的。

以5城市原始数据为例，A*算法、宽度优先算法和SMA*算法结果都是

A―>B―>D―>C―>E―>A

耗散值也都为35。在其他城市数目下的结果也一样。

(2)宽度优先算法较另外3个算法耗时很长，效率不行。

那是因为宽度优先算法须对每个节点进行扩展，以10个城市为例，需扩展10的11次方。所以宽度优先算法耗时比较长，占用CPU资源很大，是一种全面但效率很低的算法，尤其在运行数据比较大的时候就会显示出来。

参考文献：

[1]周西苓.人工智能原理与应用[M].北京:航空工业出版社,1999.

[2]朱福喜.等.人工智能原理[M].武汉:武汉大学出版社,1998.

[3]吕义忠.等.图论与代数[M].北京:航空工业出版社,2000.

本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。