用c语言实现旅行商问题的c

C++入门建议从C语言过渡，掌握基本语法后再学习面向对象编程 #生活技巧# #工作学习技巧# #编程语言学习路径#

5.2.4 旅行商问题

旅行商问题的介绍见4 . 2 . 4节，它的解空间是一个排列树。与在子集树中进行最大收益和最小耗费分枝定界搜索类似，该问题有两种实现的方法。第一种是只使用一个优先队列，队列中的每个元素中都包含到达根的路径。另一种是保留一个部分解空间树和一个优先队列，优先队列中的元素并不包含到达根的路径。本节只实现前一种方法。

由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝定界法。在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为M i n H e a p N o d e。每个节点包括如下区域： x（从1到n的整数排列，其中x [ 0 ] = 1 )，s（一个整数，使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s], 而剩余待访问的节点是x [ s + 1 : n - 1 ]），c c（旅行路径前缀，即解空间树中从根节点到当前节点的耗费），l c o s t（该节点子树中任意叶节点中的最小耗费）， r c o s t（从顶点x [ s : n - 1 ]出发的所有边的最小耗费之和）。当类型为M i n H e a p N o d e ( T )的数据被转换成为类型T时，其结果即为l c o s t的值。分枝定界算法的代码见程序1 7 - 9。

程序1 7 - 9首先生成一个容量为1 0 0 0的最小堆，用来表示活节点的最小优先队列。活节点按其l c o s t值从最小堆中取出。接下来，计算有向图中从每个顶点出发的边中耗费最小的边所具有的耗费M i n O u t。如果某些顶点没有出边，则有向图中没有旅行路径，搜索终止。如果所有的顶点都有出边，则可以启动最小耗费分枝定界搜索。根的孩子（图1 6 - 5的节点B）作为第一个E-节点，在此节点上，所生成的旅行路径前缀只有一个顶点1，因此s=0, x[0]=1, x[1:n-1]是剩余的顶点（即顶点2 ， 3 ，.， n ）。旅行路径前缀1 的开销为0 ，即c c = 0 ，并且，r c o st=n ?i=1M i n O u t [i]。在程序中，bestc 给出了当前能找到的最少的耗费值。初始时，由于没有找到任何旅行路径，因此b e s t c的值被设为N o E d g e。

程序17-9 旅行商问题的最小耗费分枝定界算法

template<class T>

T AdjacencyWDigraph<T>::BBTSP(int v[])

{// 旅行商问题的最小耗费分枝定界算法

// 定义一个最多可容纳1 0 0 0个活节点的最小堆

MinHeap<MinHeapNode<T> > H(1000);

T *MinOut = new T [n+1];

// 计算MinOut[i] = 离开顶点i的最小耗费边的耗费

T MinSum = 0; // 离开顶点i的最小耗费边的数目

for (int i = 1; i <= n; i++) {

T Min = NoEdge;

for (int j = 1; j <= n; j++)

if (a[i][j] != NoEdge &&

(a[i][j] < Min || Min == NoEdge))

Min = a[i][j];

if (Min == NoEdge) return NoEdge; // 此路不通

MinOut[i] = Min;

MinSum += Min;

}

// 把E-节点初始化为树根

MinHeapNode<T> E;

E.x = new int [n];

for (i = 0; i < n; i++)

E.x[i] = i + 1;

E.s = 0; // 局部旅行路径为x [ 1 : 0 ]

E.cc = 0; // 其耗费为0

E.rcost = MinSum;

T bestc = NoEdge; // 目前没有找到旅行路径

// 搜索排列树

while (E.s < n - 1) {// 不是叶子

if (E.s == n - 2) {// 叶子的父节点

// 通过添加两条边来完成旅行

// 检查新的旅行路径是不是更好

if (a[E.x[n-2]][E.x[n-1]] != NoEdge && a[E.x[n-1]][1] != NoEdge && (E.cc +

a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1] < bestc || bestc == NoEdge)) {

// 找到更优的旅行路径

bestc = E.cc + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1];

E.cc = bestc;

E.lcost = bestc;

E . s + + ;

H . I n s e r t ( E ) ; }

else delete [] E.x;}

else {// 产生孩子

for (int i = E.s + 1; i < n; i++)

if (a[E.x[E.s]][E.x[i]] != NoEdge) {

// 可行的孩子, 限定了路径的耗费

T cc = E.cc + a[E.x[E.s]][E.x[i]];

T rcost = E.rcost - MinOut[E.x[E.s]];

T b = cc + rcost; //下限

if (b < bestc || bestc == NoEdge) {

// 子树可能有更好的叶子

// 把根保存到最大堆中

MinHeapNode<T> N;

N.x = new int [n];

for (int j = 0; j < n; j++)

N.x[j] = E.x[j];

N.x[E.s+1] = E.x[i];

N.x[i] = E.x[E.s+1];

N.cc = cc;

N.s = E.s + 1;

N.lcost = b;

N.rcost = rcost;

H . I n s e r t ( N ) ; }

} // 结束可行的孩子

delete [] E.x;} // 对本节点的处理结束

try {H.DeleteMin(E);} // 取下一个E-节点

catch (OutOfBounds) {break;} // 没有未处理的节点

}

if (bestc == NoEdge) return NoEdge; // 没有旅行路径

// 将最优路径复制到v[1:n] 中

for (i = 0; i < n; i++)

v[i+1] = E.x[i];

while (true) {// 释放最小堆中的所有节点

delete [] E.x;

try {H.DeleteMin(E);}

catch (OutOfBounds) {break;}

}

return bestc;

}

while 循环不断地展开E-节点，直到找到一个叶节点。当s = n - 1时即可说明找到了一个叶节点。旅行路径前缀是x [ 0 : n - 1 ]，这个前缀中包含了有向图中所有的n个顶点。因此s = n - 1的活节点即为一个叶节点。由于算法本身的性质，在叶节点上lcost 和cc 恰好等于叶节点对应的旅行路径的耗费。由于所有剩余的活节点的lcost 值都大于等于从最小堆中取出的第一个叶节点的lcost 值，所以它们并不能帮助我们找到更好的叶节点，因此，当某个叶节点成为E-节点后，搜索过程即终止。

while 循环体被分别按两种情况处理，一种是处理s = n - 2的E-节点，这时，E-节点是某个单独叶节点的父节点。如果这个叶节点对应的是一个可行的旅行路径，并且此旅行路径的耗费小于当前所能找到的最小耗费，则此叶节点被插入最小堆中，否则叶节点被删除，并开始处理下一个E-节点。

其余的E-节点都放在while 循环的第二种情况中处理。首先，为每个E-节点生成它的两个子节点，由于每个E-节点代表着一条可行的路径x [ 0 : s ]，因此当且仅当< x[s],x[i] > 是有向图的边且x [ i ]是路径x [ s + 1 : n - 1 ]上的顶点时，它的子节点可行。对于每个可行的孩子节点，将边<x[s],x[i] > 的耗费加上E.cc 即可得到此孩子节点的路径前缀( x [ 0 : s ]，x[i]) 的耗费c c。由于每个包含此前缀的旅行路径都必须包含离开每个剩余顶点的出边，因此任何叶节点对应的耗费都不可能小于cc 加上离开各剩余顶点的出边耗费的最小值之和，因而可以把这个下限值作为E-节点所生成孩子的lcost 值。如果新生成孩子的lcost 值小于目前找到的最优旅行路径的耗费b e s t c，则把新生成的孩子加入活节点队列（即最小堆）中。

如果有向图没有旅行路径，程序1 7 - 9返回N o E d g e；否则，返回最优旅行路径的耗费，而最优旅行路径的顶点序列存储在数组v 中。

网址：用c语言实现旅行商问题的c https://www.yuejiaxmz.com/news/view/190009

相关内容

C语言学习错题集（一）
剖析C语言中a=a+++++a的无聊问题
C语言学习
旅行商问题+背包问题
语言C++之循环结构
c语言printf输出格式
c语言原程序如下intx=496;printf('*%
50个常见的C#面试问题和答案合集和详解
【python】使用C
C语言个人财务管理示例

随便看看