旅行售货员问题.doc

1 一问题的重述售货员要到若干城市去推销商品,已知各城市之间的路程(或旅费)。他要选定一条从驻地出发,经过每个城市一次,最后回到驻地的路线,使总的路程(或总旅费)最小。路线是一个带权图。图中各边的费用(权)为正数。图的一条周游路线是包括V 中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。旅行售货员问题的解空间可以组织成一棵树,从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图 G 中找出费用最小的周游路线。设有 p个城市,假设每两个城市之间都有直通通道,两个城市之间的路程已知,一个售货员要到每个城市推销产品,然后返回原出发地,问这个售货员应该如何选择路线,能使每个城市都经过一次且仅一次,并且行程最短,这就是著名的旅行售货员问题,也即货郎担问题。用图论的术语来描述旅行售货员问题:即在一个正权完全图中寻找一个具有最小权的哈密顿回路,对于此问题,由于完全图中必然存在哈密顿回路,那么目前可以用于求解的方法有枚举法,分枝限界法,这两种算法可以求得此问题的精确解,但到目前为止,还没有求解这一问题的有效算法,我们可以利用分支限界法,回溯法求解此问题的近似解,以求得与最优解最为接近的解。二问题的求解方法 1 枚举法枚举法就是一一列出问题的所有解,然后进行比较,取权值最小的解为最优解,这种方法虽然可以求取问题的最优解,但是我们知道旅行售货员问题是对完全图而言的,对有 N 个结点的完全图,存在 2 )!1(?N 个不同的哈密顿回路,如果采用枚举法求解,则要对上述数目的不同的哈密顿回路一一进 2 行运算且需要相互之间比较,当N取值较小时,此种求解方法没有任何问题, 但若 N值较大时,计算量则以级数级别递增,况且没有有效的算法,所以在计算机中也较难实现,故枚举法在大多数的实际应用中是不可取的。 2 回溯法旅行售货员问题的解空间是一棵排列树。对于排列树的回溯搜索与生成 1,2,…,n 的所有排列的递归算法 perm 类似。开始时]n,,1,2 [??x ,相应的排列树由]:1[xn 的所有排列构成。在递归算法 backtrack 中,当 i=n 时, 当前的扩展结点是排列树的叶结点的父结点。此时算法检测图 G是否存在一条从顶点]1[?nx 到顶点][nx 的边和从顶点][nx 到顶点 1 的边。如果这两条边都存在,则找到一条旅行售货员回路。此时算法还需要判别这条回路的费用是否优于当前已经找到的最优回路的费用 bestc 。如果是,则必须更新当前的最优值 bestc 和当前的最优解 bestx 。当ni?时,当前的扩展结点位于排列树的第 1?i 层。图G中存在从顶点]1[?ix 到达顶点][ix 的边时,]:1[ix 构成图 G中的一条路径,且当]:1[ix 的费用小于当前最优值时算法进入排列树的第 i 层;否则,则剪去相应的子树。算法中记录当前路径]:1[ix 的费用。 3 分枝限界法分枝限界法的基本思想: 分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。问题的解空间树时表示问题解空间的一棵有序树,常见的由子集树和排列树。在搜索问题的解空间树时,分支限界法与回溯法的主要不同在于它们对当前扩展结点所采用的扩展方式。在分支限界法中,每一个活结点只有一次机会成为扩展检点。活结点一旦成为扩展结点,就一次性产生