旅行售货员问题.ppt

旅行售货员问题 计算复杂性理论介绍 问题的描述 售货员要到若干城市去推销商品 已知各城市之间的路程 或旅费 他要选定一条从驻地出发 经过每个城市一次 最后回到驻地的路线 使总的路程 或总旅费 最小 旅行售货员问题虽然易于被人理解 但其计算复杂度却是问题的输入规模的指数函数 是一个NP完全问题 问题的描述 路线是一个带权图 图中各边的费用 权 为正数 图的一条周游路线是包括V中的每个顶点在内的一条回路 周游路线的费用是这条路线上所有边的费用之和 用图论的术语来描述旅行售货员问题 即在一个正权完全图中寻找一个具有最小权的哈密顿回路 对于此问题 由于完全图中必然存在哈密顿回路 目前可以用于求解的方法有枚举法 分枝限界法 这两种算法可以求得此问题的精确解 但到目前为止 还没有求解这一问题的有效算法 我们可以利用分支限界法 回溯法求解此问题的近似解 以求得与最优解最为接近的解 旅行售货员问题 枚举法 复杂度极高 可以求出精确解 通过对问题的排列树的合理剪枝 大大缩减了问题需要求解的时间 可以求出精确解 基于三角不等式性质等 进一步抽象求解过程 可以求出近似解 复杂度为多项式级别 问题的精确解和近似解 分支限界法 NP问题近似算法 回溯法 通过对排列树的剪枝 缩减问题需要的求解时间 可求精确解及近似解 共有6条周游路线 1 2 4 3 1 66 1 2 3 4 1 59 1 3 2 4 1 25 1 3 4 2 1 66 1 4 2 3 1 25 1 4 3 2 1 59 设G V E 是一个带权图 图中各边的权值为正数 图的一条周游路线是包括V中的每个顶点在内的一条回路 旅行售货员问题的解空间可以组织成一棵树 从树的根结点到任一叶结点的路径定义了图G的一条周游路线 周游路线的费用是这条路线上所有边的费用之和 旅行售货员问题要找出费用最小的周游路线 实例 4个城市n 4叶节点个数 周游线路 n 1 枚举法 665925662559 从第一个城市到第二个城市有n 1种走法 从第二个城市到第三个城市有n 2种走法 因而共有 n 1 种走法 若考虑v1v2 vnv1和v1vnvn 1 v2v1是同一条回路 还共有 1 2 n 1 条不同的哈密顿回路 为了比较权的大小 对每条哈密顿回路要做n 1次加法 故加法的总数为 1 2 n 1 n 1 时间复杂度O n 例如当有40个城市时 1 2 n 1 n 1 的近似值为3 77 10 47 假设一台计算机每秒完成1011次 百亿 次加法 将需要超过1 19 1029年才能完成所需的加法次数 显然是不可能的 算法效率 1 有许多问题 当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时 往往要使用回溯法 2 回溯法的基本做法是搜索 或是一种组织得井井有条的 能避免不必要搜索的穷举式搜索法 这种方法适用于解一些组合数相当大的问题 3 回溯法在问题的解空间树中 按深度优先策略 从根结点出发搜索解空间树 算法搜索至解空间树的任意一点时 先判断该结点是否包含问题的解 如果肯定不包含 剪枝过程 则跳过对该结点为根的子树的搜索 逐层向其祖先结点回溯 否则 进入该子树 继续按深度优先策略搜索 生成问题状态的基本方法扩展结点 一个正在产生儿子的结点活结点 一个自身已生成但其儿子还没有全部生成的结点死结点 一个所有儿子已经产生的结点深度优先的问题状态生成法 如果对一个扩展结点R 一旦产生了它的一个儿子C 就把C当做新的扩展结点 在完成对子树C 以C为根的子树 的穷尽搜索之后 将R重新变成扩展结点 继续生成R的下一个儿子 如果存在 回溯法 基本思想 一 解空间树的动态搜索回溯法从根结点出发 按照深度优先策略遍历解空间树 搜索满足约束条件的解 初始时 根结点成为一个活结点 同时也称为当前的扩展结点 在当前扩展结点处 搜索向纵深方向移至一个新结点 这个新结点成为一个新的活结点 并成为当前的扩展结点 如果在当前的扩展结点处不能再向深方向移动 则当前的扩展结点就成为一个死结点 此时 应往回移动回溯至最近的一个活结点处 并使这个活结点成为当前的扩展结点 回溯法以这种工作方式递归地在解空间中搜索 直至找到所要求的解或解空间中已无活结点时为止 二 常用剪枝函数 用约束函数在扩展结点处剪去不满足约束的子树 用限界函数剪去得不到最优解的子树 为了避免生成那些不可能产生最佳解的问题状态 要不断地利用限界函数 boundingfunction 来处死 剪枝 那些实际上不可能产生所需解的活结点 以减少问题的计算量 具有限界函数的深度优先生成法称为回溯法 回溯法 穷举 剪枝 解空间树的动态搜索 将图中n个顶点编号为1 2 n 以顶点1为起点 旅行回路描述为1 x1 x2 xn 1 其中x1 x2 xn为顶点2 3 4 n的1个排列 因此解空间大小为 n 1 A B D H N 剪枝 算法描述 旅行售货员问题的解空间是一棵排列树 开始时 x 1 2 n 相应的排列树由x 1 n 的所有排列构成 在递归算法Backtrack中 1 当i n时 当前扩展节点是排列树的叶节点的父节点 检测图G是否存在一条从顶点x n 1 到顶点x n 的边和一条从顶点x n 到顶点1的边 如果这两条边都存在 则找到一条旅行员售货回路 此时 算法还需要判断这条回路的费用是否优于已找到的当前最优回流的费用bestc 如果是 则必须更新当前最优值bestc和当前最优解bestx 2 当i n时 当前扩展节点位于排列树的第i 1层 图G中存在从顶点x i 1 到顶点x i 的边时 x 1 i 构成图G的一条路径 且当x 1 i 的费用小于当前最优值时算法进入树的第i层 否则将剪去相应的子树 13 privatestaticvoidbacktrack inti if i n 当前扩展结点是排列树的叶结点的父结点if a x n 1 x n max value 得到最优值 else i n 当前扩展结点位于第i 1层 cc 记录当前路径x 1 i 的费用a 图G的邻接矩阵 14 for intj i j n j 搜索第i层的所有子树 是否可进入x j 子树 if a x i 1 x j max value 还原x i x j 的值 Backtrack最坏情况下时间复杂度O n 1 更新bestx时间复杂度O n 时间复杂度很高O n 算法效率 1 分支限界法基本思想分支限界法常以广度优先或以最小耗费 最大效益 优先的方式搜索问题的解空间树 在分支限界法中 每一个活结点只有一次机会成为扩展结点 活结点一旦成为扩展结点 就一次性产生其所有儿子结点 在这些儿子结点中 导致不可行解或导致非最优解的儿子结点被舍弃 其余儿子结点被加入活结点表中 此后 从活结点表中取下一结点成为当前扩展结点 并重复上述结点扩展过程 这个过程一直持续到找到所需的解或活结点表为空时为止 2 常见的两种分支限界法从活结点表中选择下一扩展结点的不同方式导致不同的 1 队列式 FIFO 分支限界法将活结点表组织成一个队列 并按队列的先进先出原则选取下一个结点为当前扩展结点 2 优先队列式分支限界法将活结点表组织成一个优先队列 并按优先队列中规定的结点优先级选取优先级最高的下一个结点为当前扩展结点最大优先队列 使用最大堆 体现最大效益优先最小优先队列 使用最小堆 体现最小费用优先 分支限界法 1 求解目标 回溯法 找出解空间中满足约束条件的所有解 分支限界法 找出满足约束条件的一个解 在满足约束条件的解中找出使某一目标函数值极大或极小的解 分支限界法和回溯法一样都是在解空间上搜索问题解的算法 2 搜索方式 深度优先DFS 回溯法 分支限界法 广度优先BFS或最小损耗优先 C 30 11 4 26 6 25 14 59 25 24 算法描述 准备工作 建立小根堆 用于存储活动节点 计算每个顶点的最小出边 若存在某个顶点没有出边 则算法终止 初始化树根 顶点1 为第一个活动节点 判断节点是否是叶结点的父节点 是的话 则检查是否一定有最低耗费 若是加入小根堆 不是叶结点的父节点 则生成子节点 并判断子节点是否有可能取得最低耗费 若可能则加入小根堆 取出下一个节点作为活动节点 若该节点已经是叶结点 返回当前最低耗费值 即为最优旅行 若不是叶结点则循环2 3步 邻接矩阵 优先队列式分支限界法用极小堆存储活结点表 B被扩展后 它的三个儿子结点C D E被依次插入堆中 E被扩展后 它的儿子结点J K被依次插入当前堆中 D被扩展后 它的儿子结点H I被依次插入当前堆中 初始扩展结点为B 优先队列为空 B E D C E D J K C D H J K I C H J K I C J K I C K I C I C C K被扩展后 得到可行解费用为59 高于当前最优解25 NP问题近似算法 从实际应用中抽象出的旅行售货员问题具有一些特殊性质 比如 费用函数c往往具有三角不等式性质 即对任意3个顶点u v w有c u v 1 不存在性能比为 的解旅行售货员问题的多项式时间近似算法 NP问题近似算法 voidapproxTSP Graghg 1 选择g的任意顶点r 2 用Prim算法找出带权图g的一颗以r为根的最小生成树T 3 前序遍历树T得到顶点表L 4 将r加入到表L的末尾 按表L中顶点次序组成回路H 作为计算结果返回 NP问题近似算法 a 图G顶点集 abcdefgh b 找到的最小生成树 MST T完全遍历DFSabcbhbadefegeda c 对T作前序遍历的顺序abchdefga d L产生的哈密顿回路H取捷径生成解 e G的一个最小费用旅行售货员回路 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 总结 1 枚举法枚举法是最差的一种算法 即将所有可能的结果都排列一次 并比较解与当前最优解的大小 因此其时间复杂度很高O n 在实际应用中当结点数很多时不可取 2 回溯法如果不考虑更新bestx所需的计算时间 则算法backtrack需要O n 1 计算时间 由于算法backtrack在最坏的情况下可能需要更新当前最优解O n 1 次 每次更新bestx需O n 计算时间 从而整个算法的计算时间复杂性为O n 3 分支限界法由于是NP问题 其时间复杂度很高 当相对于回溯法而言 分支限界法剪掉了一些不必要的计算 效率有很大的提高 但是在最坏的情况下可能需要满历所有的结点 此时的时间复杂度也是很高的 O 2n 搜索状态空间O 2 指数时间对每个结点的计算O n 4 NP问题近似算法作为NP完全问题 相对于其他算法 基于三角不等式性质的旅行售货员近似算法 效率有很大的提高 其不存在最坏的情况 算法稳定性较好 且性价比在常数级别 在采用朴素Pri