《旅行售货员问题.docx》由会员分享，可在线阅读，更多相关《旅行售货员问题.docx（3页珍藏版）》请在三一办公上搜索。
1、旅行售货员问题旅行售货员问题 问题描述： 某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短 该问题是一个NP完全问题， 有(n-1)!条可选路线 最优解(1,3,2,4,1)，最优值25 问题具体描述： 某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。 路线是一个带权图。图中各边的费用为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。 旅行售货员问题的解空
2、间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。 算法描述： 旅行售货员问题的解空间是一棵排列树 x=1 2 3.n相应的排列树由x1:n的所有排列构成 在递归算法Backtrack中 当i=n时，当前扩展结点是排列树的叶节点的父结点 此时算法检测图G是否存在一条从顶点xn-1到顶点xn的边 算法： template void Traveling:Backtrack(int i) if (i = n) if (axn-1xn != NoEdge & axn1 != NoEdge & (cc + axn-1xn + axn
3、1 bestc | bestc = NoEdge) for (int j = 1; j = n; j+) bestxj = xj; bestc = cc + axn-1xn + axn1; else for (int j = i; j = n; j+) / 是否可进入xj子树? if (axi-1xj != NoEdge & (cc + axi-1xi bestc | bestc = NoEdge) / 搜索子树 Swap(xi, xj); cc += axi-1xi; Backtrack(i+1); cc -= axi-1xi; Swap(xi, xj); 复杂度分析 算法backtrack在最坏情况下可能需要更新当前最优解O(n-1)!)次，每次更新bestx需计算时间O(n)，从而整个算法的计算时间复杂性为O(n!)
