旅行商问题

现在的位置: 首页 > 综合 > 正文

RSS

2013年10月29日 ⁄ 综合 ⁄ 共 1513字 ⁄ 字号小中大 ⁄ 评论关闭

旅行商问题(TSP问题)就是一支销售商从n个城市中的某一城市出发，不重复地走完其余n-1个城市并且回到出发点，在所有可能的路线中求出路径长度最短的一条的问题。

输入：

第一行有两个整数，m和n,n是节点的个数，m是边数，接下来有m行，描述边的关系，每行三个整数(i,j),length表示节点ｉ到ｊ的长度为length．

算法分析：

这个问题的解空间是一颗排列树，对于排列数的回溯搜索与生成１,２,３．的全排列的算法类似。开始时ｘ＝［１，２，．．ｎ］则相应的排列树是由ｘ［１：ｎ］的所有排列组成的。

当i=n时，当前扩展节点是排列树的叶节点的父节点，此时检测是否存在

map[X[n-1]][X[n]],map[X[n]][1]着两条回路，如果这两条边存在，则构成一条旅行回路。然后再确定当前最优解。

当i<n时，当前扩展节点位于排列数的第i-1层。图G中存在从顶点X[i-1]
到X[i]
的边时，X[1:i]构成一条路径，且当X[1:i]的费用小于当前最优解时，算法进入排列数的第i层，否则剪去相应的子树。

代码如下：

#include<iostream>
using namespace std;
#define NUM 100
#define NoEdge -1
int map[NUM][NUM];
int X[NUM];          //记录解向量
int bestX[NUM];      //记录最优解
int current;        //记录当前最优解
int best;           //记录当前最优解
int n;                 //节点的个数
void BackTrack(int);
int main()
{
    int num;
    cin>>n>>num;  //n是节点的个数，num是边的数目
    for(int i=0;i<NUM;i++)
        for(int j=0;j<NUM;j++)
            map[i][j]=NoEdge;      //初始化数组
    int num1,num2,num3;
    for(int i=1;i<=num;i++)
    {
        cin>>num1>>num2>>num3;
        map[num1][num2]=num3;
        map[num2][num1]=num3;
    }
    for(int i=1;i<=n;i++)
        X[i]=i;
    best = NoEdge;
    current =0;
    BackTrack(2);
    for(int i=1;i<=n;i++)
        cout<<bestX[i]<<"  ";
    cout<<endl;
    cout<<best;
    return 0;
}


void BackTrack(int t)
{

    if(t==n)    //到达排列树的叶子节点的父节点
    {
        if((map[X[n-1]][X[n]]!=NoEdge)&&(map[X[n]][1]!=NoEdge)&&((current+map[X[n-1]][X[n]]+map[X[n]][1]<best)||best==NoEdge))
        {
            for(int j=1;j<=n;j++)
                 bestX[j]= X[j];
            best = current+map[X[n-1]][X[n]]+map[X[n]][1];
        }
    }
    else
    {
        for(int i=t;i<=n;i++)
        {
            if((map[X[t-1]][X[i]])!=NoEdge&&((current+map[X[t-1]][X[i]])<best||best==NoEdge))
            {
                swap(X[t],X[i]);
                current+=map[X[t-1]][X[t]];
                BackTrack(t+1);             //搜索下一层
                current-=map[X[t-1]][X[t]];     
                swap(X[t],X[i]);
            }
        }
    }
}

运行结果：