展开查看详情
2 .问题的描述 售货员要到若干城市去推销商品，已知各城市之间的路程 ( 或旅费 ) 。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程 ( 或总旅费 ) 最小。 旅行售货员问题虽然易于被人理解，但其计算复杂度却是问题的输入规模的指数函数。是一个 NP 完全问题 路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括 V 中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。
3 .问题的描述 旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图 G 中找出费用最小的周游路线。设有 p 个城市，假设每两个城市之间都有直通通道，两个城市之间的路程已知，一个售货员要到每个城市推销产品，然后返回原出发地，问这个售货员应该如何选择路线，能使每个城市都经过一次且仅一次，并且行程最短，这就是著名的旅行售货员问题，也即货郎担问题。
4 .问题的重述 用图论的术语来描述旅行售货员问题：即在一个正权完全图中寻找一个具有最小权的哈密顿回路，对于此问题，由于完全图中必然存在哈密顿回路，那么目前可以用于求解的方法有枚举法，分枝限界法，这两种算法可以求得此问题的精确解，但到目前为止，还没有求解这一问题的有效算法，我们可以利用分支限界法，回溯法求解此问题的近似解，以求得与最优解最为接近的解。
5 .旅行售货员问题 枚举法 复杂度极高，可以求出精确解 通过对问题的排列树的合理剪枝，大大缩减了问题需要求解的时间。可以求出精确解 基于三角不等式性质等，进一步抽象求解过程，可以求出近似解，复杂度为多项式级别 问题的精确解和近似解 分支限界法 NP 问题近似算法 回溯法 同样通过对排列树的剪枝，缩减问题需要的求解时间。可求精确解及近似解
6 .枚举法 枚举法就是一一列出问题的所有解，然后进行比较，取权值最小的解为最优解，这种方法虽然可以求取问题的最优解，但是我们知道旅行售货员问题是对完全图而言的，对有 N 个结点的完全图，存在 (N-1)!/2 个不同的哈密顿回路，如果采用枚举法求解，则要对上述数目的不同的哈密顿回路一一进行运算且需要相互之间比较，当 N 取值较小时，此种求解方法没有任何问题，但若 N 值较大时，计算量则以级数级别递增，况且没有有效的算法，所以在计算机中也较难实现，故枚举法在大多数的实际应用中是不可取的。
7 .回溯法 旅行售货员问题的解空间是一棵排列树。开始时， x=[1,2,…,n] 相应的排列树由 x=[1:n] 的所有排列构成。书 P166 页 在递归算法 Backtrack 中，当 i =n 时，当前扩展节点是排列树的叶节点的父节点。此时算法 检测图 G 是否存在一条从顶点 x[n-1] 到顶点 x[n] 的边和一条从顶点 x[n] 到顶点 1 的边 。如果这两条边都存在，则找到一条旅行员售货回路。此时，算法还需要判断这条回路的费用是否优于已找到的当前最优回流的费用 bestc 。如果是，则必须更新当前最优值 bestc 和当前最优解 bestx 。
8 .回溯法 当 i <n 时，当前扩展节点位于排列树的第 i-1 层。 图 G 中存在从顶点 x[i-1] 到顶点 x[ i ] 的边时， x[1:i] 构成图 G 的一条路径，且当 x[1:i] 的费用小于当前最优值时算法进入树的第 i 层 ，否则将剪去相应的子树。
9 .分支限界法 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。书 P213 页 算法开始时创建一个最小堆，表示活结点优先队列。堆中每个结点的子树费用的下界 lcost 值是优先队列的优先级。接着算法计算出图中每个顶点的最小费用出边并用 minout 记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。如果每个顶点都有出边，则根据计算出的 minout 作算法初始化。
10 .分支限界法 算法的 while 循环体完成对排列树内部结点的扩展。对于当前扩展结点，算法分 2 种情况进行处理： 1 、首先考虑 s=n-2 的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。 2 、当 s<n-2 时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是 x[0:s] ，其可行儿子结点是从剩余顶点 x[s+1:n-1] 中选取的顶点 x[ i ] ，且 (x[s] ， x[ i ]) 是所给有向图 G 中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀 (x[0:s] ， x[ i ]) 的费用 cc 和相应的下界 lcost 。当 lcost < bestc 时，将这个可行儿子结点插入到活结点优先队列中。
11 .分支限界法 算法中 while 循环的终止条件是排列树的一个叶结点成为当前扩展结点。当 s=n-1 时，已找到的回路前缀是 x[0:n-1] ，它已包含图 G 的所有 n 个顶点。因此，当 s=n-1 时，相应的扩展结点表示一个叶结点。此时该叶结点所相应的回路的费用等于 cc 和 lcost 的值。剩余的活结点的 lcost 值不小于已找到的回路的费用。它们都不可能导致费用更小的回路。因此已找到的叶结点所相应的回路是一个最小费用旅行售货员回路，算法可以结束。 算法结束时返回找到的最小费用，相应的最优解由数组 v 给出。
12 .NP 问题 多项式时间 ：在计算复杂度理论中，指的是一个问题的计算时间 m(n) 不大于问题大小 n 的多项式倍数。通俗点来说，多项式时间就是指时间复杂度是个多项式。举个例子，现在从 n 阶图中找两点的最短路径，复杂度为 O(n^2) 级别，而 n^2 对于 n 是多项式（单项式当然也算），这就称为是多项式复杂度，或者多项式时间。如果某一个算法的规模是 n ，但是复杂度比如是 2^n ，写不成 n 的多项式，那就不是多项式时间。 P 类问题 ：所有可以在多项式时间内求解的判定问题构成 P 类问题。 NP 类问题 ：所有的非确定性多项式时间可解的判定问题构成 NP 类问题。
13 .NP 问题 非确定性算法 ：非确定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的，算法的验证阶段是确定性的，它验证猜测阶段给出解的正确性。设算法 A 是解一个判定问题 Q 的非确定性算法，如果 A 的验证阶段能在多项式时间内完成，则称 A 是一个多项式时间非确定性算法。有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，就可以得到结果。如果是找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。而这类问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，
14 .NP 问题 NPC 问题 ： NP 中的某些问题的复杂性与整个类的复杂性相关联 . 这些问题中任何一个如果存在多项式时间的算法 , 那么所有 NP 问题都是多项式时间可解的 . 这些问题被称为 NP- 完全问题 (NPC 问题 ) 。
15 .NP 问题近似算法 书 P356 页。从实际应用中抽象出的旅行售货员问题具有一些特殊性质。比如，费用函数 c 往往具有三角不等式性质，即对任意 3 个顶点 u,v,w 有 c( u,v )<=c( u,v )+c( v,w ) 。当图 G 的顶点是平面上的点，且任意两顶点间的费用是这两点间的欧氏距离时，费用函数 c 具有三角不等式性质。 可以证明，即使费用函数具有三角不等式性质，旅行售货员问题仍为 NP 完全问题。所以设计一个近似算法。当费用函数满足三角不等式时，该算法不会超过最优旅行售货员回路费用的 2 倍。
16 .NP 问题近似算法 void approxTSP ( Gragh g) { (1) 选择 g 的任意顶点 r ； (2) 用 Prim 算法找出带权图 g 的一颗以 r 为根的最小生成树 T ； (3) 前序遍历树 T 得到顶点表 L ； (4) 将 r 加入到表 L 的末尾，按表 L 中顶点次序组成回路 H ，作为计算结果返回； }
18 .NP 问题近似算法 其中， a 表示所给的图 G 顶点集； b 表示由算法找到的一颗最小生成树 T ； c 表示对树 T 所做的前序遍历访问各顶点的次序； d 表示由 T 的前序遍历顶点表示 L 产生的哈密顿回路 H ； e 表示图 G 的一个最小费用旅行售货员回路。 在 b 时，对 T 的完全遍历 W={ abcbhbadefegeda } ，还不是一个旅行售货员回路，它访问了图 G 中某些顶点多次。由于费用函数满足三角不等式，可以在 W 的基础上，从中删去已访问过的顶点，而不会增加旅行费用。若在 W 中删去顶点 u 和 w 间的一个顶点 v ，就用边 ( u,w ) 代替原来从 u 到 w 的一条路。反复用这个办法删去 W 中多次访问的顶点，可得到图 G 的一条旅行售货员回路 H={ abchdefga } 。
19 .算法分析 (1) 枚举法 枚举法是最差的一种算法，即将所有可能的结果都排列一次，并比较解与当前最优解的大小，因此其时间复杂度很高（ O(n!) ） ，在实际应用中当结点数很多时不可取。 (2) 回溯法 如果不考虑更新 bestx 所需的计算时间，则算法 backtrack 需要 O((n-1)!) 计算时间。由于算法 backtrack 在最坏的情况下可能需要更新当前最优解 O((n-1)!) 次，每次更新 bestx 需 O(n) 计算时间，从而整个算法的计算时间复杂性为 O(n!) 。
20 .算法分析 (3) 分支限界法 由于是 NP 问题，其时间复杂度很高，当相对于回溯法而言，分支限界法剪掉了一些不必要的计算，效率有很大的提高，但是在最坏的情况下可能需要满历所有的结点。此时的时间复杂度也是很高的。 (4)NP 问题近似算法 作为 NP 完全问题，相对于其他算法，基于三角不等式性质的旅行售货员近似算法，效率有很大的提高。其不存在最坏的情况，算法稳定性较好，且性价比在常数级别。在采用朴素 Prim 算法时算法复杂度为 O(n^2) ，还可以使用二叉堆优化 Prim 算法达到 O( Elog (V)) 。
热门城市
