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