2023年8月1日发(作者：)
旅行售货员问题
问题描述：
某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短 该问题是一个NP完全问题， 有(n-1)!条可选路线
最优解(1,3,2,4,1)，最优值25
问题具体描述：
某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。
路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。
旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。
/retype/zoom/ae9a5b75f46527d3240ce072?pn=1&x=0&y=0&raww=489&rawh=175&o=png_6_0_0_135_635_550_196_892.979_1262.879&type=pic&aimh=171.779&md5sum=4ced18926fc1df50fb21611e730b7292&sign=9f67dccda7&zoom=&png=0-6122&jpg=0-0
算法描述：
旅行售货员问题的解空间是一棵排列树
x=[1 2 3…..n]——>相应的排列树由x[1:n]的所有排列构成
① 在递归算法Backtrack中
② 当i=n时，当前扩展结点是排列树的叶节点的父结点
③ 此时算法检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边 ………
算法：
template
void Traveling
{
if (i == n) {
if (a[x[n-1]][x[n]] != NoEdge && a[x[n]][1] != NoEdge && (cc + a[x[n-1]][x[n]] +
a[x[n]][1] < bestc || bestc == NoEdge)) {
for (int j = 1; j <= n; j++) bestx[j] = x[j];
bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1];}
}
else {
for (int j = i; j <= n; j++)
// 是否可进入x[j]子树?
if (a[x[i-1]][x[j]] != NoEdge &&
(cc + a[x[i-1]][x[i]] < bestc || bestc == NoEdge)) { // 搜索子树
Swap(x[i], x[j]);
cc += a[x[i-1]][x[i]];
Backtrack(i+1);
cc -= a[x[i-1]][x[i]];
Swap(x[i], x[j]);}
}
}
复杂度分析
算法backtrack在最坏情况下可能需要更新当前最优解O((n-1)!)次，每次更新bestx需计算时间O(n)，从而整个算法的计算时间复杂性为O(n!)
2023年8月1日发(作者：)
旅行售货员问题
问题描述：
某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短 该问题是一个NP完全问题， 有(n-1)!条可选路线
最优解(1,3,2,4,1)，最优值25
问题具体描述：
某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。
路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。
旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。
/retype/zoom/ae9a5b75f46527d3240ce072?pn=1&x=0&y=0&raww=489&rawh=175&o=png_6_0_0_135_635_550_196_892.979_1262.879&type=pic&aimh=171.779&md5sum=4ced18926fc1df50fb21611e730b7292&sign=9f67dccda7&zoom=&png=0-6122&jpg=0-0
算法描述：
旅行售货员问题的解空间是一棵排列树
x=[1 2 3…..n]——>相应的排列树由x[1:n]的所有排列构成
① 在递归算法Backtrack中
② 当i=n时，当前扩展结点是排列树的叶节点的父结点
③ 此时算法检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边 ………
算法：
template
void Traveling
{
if (i == n) {
if (a[x[n-1]][x[n]] != NoEdge && a[x[n]][1] != NoEdge && (cc + a[x[n-1]][x[n]] +
a[x[n]][1] < bestc || bestc == NoEdge)) {
for (int j = 1; j <= n; j++) bestx[j] = x[j];
bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1];}
}
else {
for (int j = i; j <= n; j++)
// 是否可进入x[j]子树?
if (a[x[i-1]][x[j]] != NoEdge &&
(cc + a[x[i-1]][x[i]] < bestc || bestc == NoEdge)) { // 搜索子树
Swap(x[i], x[j]);
cc += a[x[i-1]][x[i]];
Backtrack(i+1);
cc -= a[x[i-1]][x[i]];
Swap(x[i], x[j]);}
}
}
复杂度分析
算法backtrack在最坏情况下可能需要更新当前最优解O((n-1)!)次，每次更新bestx需计算时间O(n)，从而整个算法的计算时间复杂性为O(n!)
发布评论