第1个回答 2011-07-01
一 问题的重述
售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。
路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。
旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。设有p个城市，假设每两个城市之间都有直通通道，两个城市之间的路程已知，一个售货员要到每个城市推销产品，然后返回原出发地，问这个售货员应该如何选择路线，能使每个城市都经过一次且仅一次，并且行程最短，这就是著名的旅行售货员问题，也即货郎担问题。
用图论的术语来描述旅行售货员问题：即在一个正权完全图中寻找一个具有最小权的哈密顿回路，对于此问题，由于完全图中必然存在哈密顿回路，那么目前可以用于求解的方法有枚举法，分枝限界法，这两种算法可以求得此问题的精确解，但到目前为止，还没有求解这一问题的有效算法，我们可以利用分支限界法，回溯法求解此问题的近似解，以求得与最优解最为接近的解。
二问题的求解方法
1枚举法
枚举法就是一一列出问题的所有解，然后进行比较，取权值最小的解为最优解，这种方法虽然可以求取问题的最优解，但是我们知道旅行售货员问题是对完全图而言的，对有N个结点的完全图，存在 个不同的哈密顿回路，如果采用枚举法求解，则要对上述数目的不同的哈密顿回路一一进行运算且需要相互之间比较，当N取值较小时，此种求解方法没有任何问题，但若N值较大时，计算量则以级数级别递增，况且没有有效的算法，所以在计算机中也较难实现，故枚举法在大多数的实际应用中是不可取的。
2回溯法
旅行售货员问题的解空间是一棵排列树。对于排列树的回溯搜索与生成1，2，…，n的所有排列的递归算法perm类似。开始时 ，相应的排列树由 的所有排列构成。
在递归算法backtrack中，当i=n时，当前的扩展结点是排列树的叶结点的父结点。此时算法检测图G是否存在一条从顶点 到顶点 的边和从顶点 到顶点1的边。如果这两条边都存在，则找到一条旅行售货员回路。此时算法还需要判别这条回路的费用是否优于当前已经找到的最优回路的费用bestc。如果是，则必须更新当前的最优值bestc和当前的最优解bestx。
当 时，当前的扩展结点位于排列树的第 层。图G中存在从顶点 到达顶点 的边时， 构成图G中的一条路径，且当 的费用小于当前最优值时算法进入排列树的第i层；否则，则剪去相应的子树。算法中用变量cc记录当前路径 的费用。
3 分枝限界法
分枝限界法的基本思想：
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树时表示问题解空间的一棵有序树，常见的由子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法的主要不同在于它们对当前扩展结点所采用的扩展方式。在分支限界法中，每一个活结点只有一次机会成为扩展检点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点总，导致不可行的解或者非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后从活结点表中取下一结点成为当前扩展结点，并重复上述扩展过程。这个过程一直持续到找到所需的解或活结点表空为止。
从活结点表中选择下一扩展结点的不同方式将导致不同的分支限界法。最常见的有以下两种方式。
（1）队列式（FIFO）分支限界法
队列式分支限界法将活结点表组织成一个队列，并按照队列的先进先出FIFO(first in first out )原则选取下一个结点为当前扩展结点。
（2） 优先队列式分支限界法
优先队列式的分支限界法将活结点表组织成一个优先队列，并按照优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。
优先队列中规定的结点优先级常用一个与该结点相关的数值p表示。结点优先级的高低与p值的大小相关。最大优先队列规定p值较大的结点优先级较高。在算法是现实通常用最大堆来实现最大优先队列，用最大堆的removeMax运算抽取堆中下一个结点成为当前扩展结点，体现最大效益优先的原则。类似的，最小优先队列规定p值较小的结点优先级较高。在算法实现时通常用最小堆来实现最小优先队列，用最小堆的removeMin运算抽取堆中下一个结点成为当前的扩展结点，体现最小费用优先的原则。用优先队列式分支限界法解具体问题式，应该根据具体问题的特点确定选用最大优先队列或者最小优先队列表示解空间的活结点表。
考察4城市旅行售货员的例子，如图3-1所示。该问题的解空间树一棵排列树。解此问题的队列式分支限界法以排列树中结点B作为初始扩展结点。此时，活结点队列为空。由于从图G的顶点1到顶点2，3，4均有边相连，所以结点B的儿子结点C，D，E均为可行结点，它们被加入到活结点队列中，并舍去当前扩展结点B。当前活结点队列中的队首结点C成为下一个扩展结点。由于图G的顶点2到顶点3和4有边相连，故结点C的2个儿子结点F和G均为可行结点，从而被加入到活结点队列中。接下来，结点D和结点E相继成为扩展结点而被扩展。此时，活结点队列中的结点为F，G，H，I，J，K。
结点F成为下一个扩展结点，其儿子结点L是一个叶结点。找到了一条旅行售货员回路，其费用为59。从下一个扩展结点G得到叶结点M，它相应的旅行售货员回路的费用为66。结点H依次成为扩展结点，得到结点N相应的旅行售货员回路，其费用为25。这已经时最好的一条回路。下一个扩展结点时结点I。以结点I为根的子树被剪去。最后，结点J，K被依次扩展，活结点队列成为空，算法终止。算法搜索得到最优值为25，相应的最优解时从根结点到结点N的路径（1，3，2，4，1）。
解同一问题的优先队列式分支限界法用一极小堆来存储活结点表，。其优先级是结点的当前费用。算法还是从排列树的结点B和空优先队列开始。结点B被扩展后，它的3个儿子结点C，D和E被一次插入堆中。此时，由于E是堆中具有最小当前费用的节点，所以处于堆顶位置，它自然成为下一个扩展结点。结点E被扩展后，其儿子结点J和K被插入当前堆中，它们的费用分别为14和24。此时堆顶元素是结点D，它成为下一个结点。如此，它的两个儿子结点H和I被插入堆中。此时，堆中含有结点C，H，I，J，K。在这些结点中，结点H具有最小费用，从而它成为下一个扩展结点。扩展结点H后得到一条旅行售货员回路（1，3，2，4，1），相应的最小费用为25。接下来结点J成为扩展结点，由此得到另外一条旅行售货员回路（1，4，2，3，1），相应的费用为25。此后的扩展结点为K，I。由结点K得到的可行解费用高于当前最优解。结点I本身的费用已高于当前最优解。从而它们都不是最好的解。最后，优先队列为空，算法终止。
图2-1
三 问题的求解结果与算法分析
1问题的求解结果
(1)当结点数为N=4，其各个点之间的边的权矩阵为 时，其最优解为：
图3-1
即其解为(1,4,2,3,1)，最优解值为13。
(2)当结点数为N=5，其各个点之间的边的权矩阵为 时，其最优解为：
图3-2
则其解为（1,5,4,2,3,1），最优解值为18。
(3)当结点数为N=6，其各个点之间的边的权矩阵为 时，其解为：
图3-3
则其解为（1，2，3，4，5，6，1），最优解值为20。
(4)当其结点数为N=7时，其各个点之间的边的权矩阵为 时，其解为：
图3-4
则其解为（1，6，2，7，3，5，4，1）,最优解值为23。
(5)当其结点数为N=8时，其相应的各个点之间的边的权矩阵为 时，
其解为：
图3-5
则其最优解为（1，7，3，5，6，8，2，4，1），最优解值为19。
2算法分析
(1)枚举法
枚举法是最差的一种算法，即将所有可能的结果都排列一次，并比较解与当前最优解的大小，因此其时间复杂度很高，在实际应用中当结点数很多时不可取。
(2)回溯法
如果不考虑更新bestx所需的计算时间，则算法backtrack需要 计算时间。由于算法backtrack在最坏的情况下可能需要更新当前最优解 次，每次更新bestx需 计算时间，从而整个算法的计算时间复杂性为 。
(3)分支限界法
由于是NP问题，其时间复杂度很高，当相对于回溯法而言，分支限界法剪掉了一些不必要的计算，效率有很大的提高，但是在最坏的情况下可能需要满历所有的结点。此时的时间复杂度也是很高的。
四心得体会
课程设计是对于知识的综合运用，通过学习算法分析也设计了解了一些关于实际问题的解决办法。还有一点就是在学习过程中只停留在书本，只是知道书中某一算法的几个应用的例子。知识面很窄，考虑问题也只会从书本出发。想在例题中是如何解决问题的。其实我们在平常的学习中应该多研究一些实际问题，扩展视野。这样就可以用不同的办法解决同一问题，使用同一方法解决不同问题，也可以使复杂问题简单化。