算法笔记 11_旅行售货员问题


问题重述:

   售货员要到若干城市去推销商品,已知各城市之间的路程(或旅费)。他要选定一条从驻地出发,经过每个城市一次,最后回到驻地的路线,使总的路程(或总旅费)最小。
   路线是一个带权图。图中各边的费用(权)为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。
   旅行售货员问题的解空间可以组织成一棵树,从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。
   设有p个城市,假设每两个城市之间都有直通通道,两个城市之间的路程已知,一个售货员要到每个城市推销产品,然后返回原出发地,问这个售货员应该如何选择路线,能使每个城市都经过一次且仅一次,并且行程最短,这就是著名的旅行售货员问题,也即货郎担问题。

算法思想:

   用图论的术语来描述旅行售货员问题:即在一个正权完全图中寻找一个具有最小权的哈密顿回路,对于此问题,由于完全图中必然存在哈密顿回路,那么目前可以用于求解的方法有枚举法,分枝限界法,这两种算法可以求得此问题的精确解,但到目前为止,还没有求解这一问题的有效算法,我们可以利用分支限界法,回溯法求解此问题的近似解,以求得与最优解最为接近的解。
   我们根据图的图生成了一棵2叉排列树,这样求最小路程就转换为如何解这棵空间树的问题。我们做过生成排列的题目如果我们穷举一遍,那么自然可以得到我们想要的解,但是这样时间复杂度O(n!),效率低得可怜,所以我们只有来优化他。
   首先我们可以用一个记录的方法,用bestc存放当前已经得到的最优解,那么只要我得到当前的解已经超过最优解了,那么剩下的我就可以不用算了;其次:如果对于任意两个城市是无边标记的(即两个城市之间是没有通路的)也不用考虑这个我们做了优化,具体的时间复杂度只能根据问题的规模而定了,接下来就是实现的问题了。(PS:这道题目还可以用记忆搜索,也就是搜索+DP,可以进一步提高效率,不过这里没有实现,转自百度文库)

C++ 代码如下:

#include<iostream>
using namespace std;

const int NoEdge=-1;
const int MAX=20;
int G[MAX][MAX];    // 用来存放所有的两个地点之间的距离
int ans[MAX],x[MAX];
int bestc,cc;       // 存放当前已经得到的最优解

void init(int n)    // 初始化、读取用户输入值函数
{
    int i,j,len;    
    memset(G,NoEdge,sizeof(G));     
    // memset是一个 C++ 函数:将 s 所指向的某一块内存中的前 n 个字节的内容全部设
    // 置为 ch 指定的ASCII值, 第一个值为指定的内存地址,块的大小由第三个参数指定,
    // 这个函数通常为新申请的内存做初始化工作, 其返回值为指向s的指针。
    // 作用是在一段内存块中填充某个给定的值,它是对较大的结构体或数组进行清零操作
    // 的一种最快方法。(因为主函数中要循环输入,所以在这里不可省略。额。。。应该如此)
    cout << "Please input the distance of every two cities(such as '1 2 54',that means you'll spend 54 arrving at city 2 from city 1. And the distance of the final two cities should be expressed like '0 0'.):  " << endl;    
    while(cin >> i >> j)    // 地点用数字编号来表示
    {
        if(i==0 && j==0) break; // 若输入的是同一个地点,中止程序,也就是最后输入 0 0 后,会输出结果
        cin >> len; // 读取某两个地点之间的距离
        G[i][j]=len;    // 存储这个距离
        G[j][i]=len;    // 城市一到城市二的距离和反过来是一样的
    }    
        
    for(i=1; i<=n; i++)
    { x[i]=i; }
    bestc = 0x3f3f3f3f; // 将最优值初始化为无穷大
    cc = 0;
}
    
void Swap(int& i,int& j)    // 交换 i、j 的值{ 
    int t = i; 
    i = j; 
    j = t; 
}

void Traveling(int i,int n)     // 计算函数,i 在主函数中初始化为 2
{ 
    int j; 
    if( i == n+1 )      // 也就是说 2 == n + 1,即用户只输入了一个城市
    {   
        if(G[ x[n-1] ][ x[n] ] != NoEdge && G[ x[n] ][ 1 ] != NoEdge && (cc + G[ x[n] ][ 1 ] < bestc ) )
        {  
            for(j=1; j<=n; j++)  
            { ans[j] = x[j]; } 
            bestc = cc + G[ x[n] ][ 1 ];  
        } 

    } 
    else 
    {  
        for(j=i; j<=n; j++) 
        {  
            if( G[ x[i-1] ][ x[j] ] != NoEdge && ( cc + G[ x[i-1] ][ x[j] ] < bestc) ) 
            {  
                Swap( x[i],x[j] ); 
                cc += G[ x[i-1] ][ x[i] ]; 
                Traveling(i+1,n); 
                cc -= G[ x[i-1] ][ x[i] ];
                Swap( x[i],x[j] ); 
            } 
        } 
    } 
}  

void print(int n)   // 输出打印结果函数
{  
    cout << "The idearest value is: " << bestc << endl; 
    cout << "The idearest routine is: "; 
    for(int i=1; i<=n; i++) 
    { cout << ans[i] <<" -> "; } 
    cout << ans[1] << endl; 
} 

int main() 
{ 
    int n;  
    while(1)
    {
        cout << "Please input the number of cities: ";        
        cin >> n;
        init(n); 
        Traveling(2,n);
        print(n);        
        cout << "---------------------------------------------------------------------" << endl;
    } 

    return 1;
}


happysneaker.com

Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论