回溯算法 --- 例题8.旅行售货员问题

一.问题描述

某售货员要到若干城市去推销商品, 已知各城市之间的路程（旅费）, 他要选定一条从驻地出发, 经过每个城市一遍, 最后回到驻地的路线, 使总的路程（总旅费）最小。

二.解题思路

旅行售货员问题的解空间是一棵排列树。对于排列树的回溯法与生成1, 2, ……n的所有排列的递归算法Perm类似。开始时x=[1, 2, ……n], 则相应的排列树有x[1:n]的所有排列构成。

在递归算法Backtrack中, 当i=n时, 当前扩展节点是排列树的叶节点的父节点。此时算法检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边。如果这两条边都存在, 则找到一条旅行员售货回路。此时, 算法还需要判断这条回路的费用是否优于已找到的当前最优回流的费用bestc。如果是, 则必须更新当前最优值bestc和当前最优解bestx。

当i

代码如下:

// 旅行售货员问题
#include
using namespace std;
class Traveling
{
    friend int TSP(int **, int *, int , int);
    private:
        void Backtrack(int i);
        int n,      //图G的顶点个数
            *x,     //当前解
            *bestx; //当前最优解
        int **a,   //图G的邻接矩阵
            cc,     //当前费用
            bestc,  //当前最优值
            NoEdge; //无边标记
};
void Traveling::Backtrack(int i)
{
    if(i == n)
    {
        cout<<"当前第"<>n && n)
    {
        cout<<"请输入邻接矩阵"<>a[i][j];
        int NoEdge = 0;
        int *v = new int[n+1];
        for(int i=0; i<=n; i++) v[i] = 0;
        int ans = TSP(a, v, n, NoEdge);
        cout<<"旅行路费最少为:"<