旅行商问题 订阅
旅行推销员问题(英语:Travelling salesman problem, TSP)是这样一个问题:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP难问题,在运筹学和理论计算机科学中非常重要。最早的旅行商问题的数学规划是由Dantzig(1959)等人提出,并且是在最优化领域中进行了深入研究。许多优化方法都用它作为一个测试基准。尽管问题在计算上很困难,但已经有了大量的启发式算法和精确方法来求解数量上万的实例,并且能将误差控制在1%内。 [1] 展开全文
旅行推销员问题(英语:Travelling salesman problem, TSP)是这样一个问题:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP难问题,在运筹学和理论计算机科学中非常重要。最早的旅行商问题的数学规划是由Dantzig(1959)等人提出,并且是在最优化领域中进行了深入研究。许多优化方法都用它作为一个测试基准。尽管问题在计算上很困难,但已经有了大量的启发式算法和精确方法来求解数量上万的实例,并且能将误差控制在1%内。 [1]
信息
提出时间
1959年
提出者
Dantzig
简    称
TSP
中文名
旅行商问题
外文名
Traveling Salesman Problem
又    称
货郎担问题
旅行商问题简介
旅行商问题(TravelingSalesmanProblem,TSP)是一个经典的组合优化问题。经典的TSP可以描述为:一个商品推销员要去若干个城市推销商品,该推销员从一个城市出发,需要经过所有城市后,回到出发地。应如何选择行进路线,以使总的行程最短。从图论的角度来看,该问题实质是在一个带权完全无向图中,找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列,随着顶点数的增加,会产生组合爆炸,它是一个NP完全问题。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用,国内外学者对其进行了大量的研究。早期的研究者使用精确算法求解该问题,常用的方法包括:分枝定界法、线性规划法、动态规划法等。但是,随着问题规模的增大,精确算法将变得无能为力,因此,在后来的研究中,国内外学者重点使用近似算法或启发式算法,主要有遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络等。 [2] 
收起全文
精华内容
下载资源
问答
  • 旅行商问题

    2018-12-22 17:02:20
    旅行商问题
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int n;
    int dist[15][15];//输入的距离矩阵
    int min_dist[15][15];//求出的最短路径距离矩阵
    int d[15][1<<15];//用于表示DP状态
    bool vis[15][1<<15];
    int dp(int i,int s){//记忆话搜索,这个dp函数不会计算dp(0,0)的切记
        if(vis[i][s])return d[i][s];//这个是结束条件,所以VIS[i][1<<i]与d[i][1<<i]都要预更新
        vis[i][s]=true;
        int &ans = d[i][s];//本次DP要更新的状态答案
        ans = 1e9;
        for(int j=0;j<=n;j++)//集合s中的一个节点号j
            if(s&(1<<j)&&j!=i)//假设是从点集的节点J走到当前点I
                if(ans>dp(j,s^(1<<i))+min_dist[j][i])//当前距离小于子集生成的距离
                    ans = dp(j,s^(1<<i))+min_dist[j][i];//递归求解,回溯更新答案
        return ans;
    }
    void floyd(){//计算最短路径距离
        for(int k=0;k<=n;k++)
            for(int i=0;i<=n;i++)
                for(int j=0;j<=n;j++)
                    if(min_dist[i][j]>min_dist[i][k]+min_dist[k][j])
                        min_dist[i][j] = min_dist[i][k]+min_dist[k][j];
    }
    int main(){
        while( scanf("%d",&n)==1&&n ){
            for(int i=0;i<=n;i++)
                for(int j=0;j<=n;j++){
                    scanf("%d",&dist[i][j]);
                    min_dist[i][j]= dist[i][j];
                }
            floyd();//计算最短路径距离
            memset(vis,0,sizeof(vis));
            for(int i=0;i<=n;i++){//注意这里一定要单独初始化,否则dp函数计算出来的结果错误
                vis[i][1<<i]=true;
                d[i][1<<i]=min_dist[0][i];
            }
            printf("%d\n",dp(0,(1<<(n+1))-1 ));
        }
        return 0;
    }
    旅行商问题
    POJ 3311 状态压缩
    Sample Input
    3
    0 1 10 10
    1 0 1 2
    10 1 0 10
    10 2 10 0
    0
    Sample Output
    8
    题意:求走过所有点并回到原点的最短路,可以走一个点多次.
    思路:
    因为可以走一个点多次,所以可以先求出每两个点之间的最短路,然后用经典的旅行商问题的状态压缩DP做法
    
    

     

    展开全文
  • 旅行商问题

    2009-02-16 14:18:06
    旅行商问题(Traveling Saleman Problem,TSP)是VRP的特例,由于Gaery[1]已证明TSP问题是NP难题,因此,VRP也属于NP难题。  旅行商问题(TSP)又译为旅行推销员问题、货郎担问题,简称为TSP问题,是最基本的路线...
    旅行商问题(Traveling Saleman Problem,TSP)是VRP的特例,由于Gaery[1]已证明TSP问题是NP难题,因此,VRP也属于NP难题。 
    
      旅行商问题(TSP)又译为旅行推销员问题、货郎担问题,简称为TSP问题,是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的需求点之后,最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig(1959)等人提出[2]。 
    
      TSP问题在物流中的描述是对应一个物流配送公司,欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。 
    
      TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间,搜索空间是n个点的所有排列的集合,大小为(n-1)。可以形象地把解空间看成是一个无穷大的丘陵地带,各山峰或山谷的高度即是问题的极值。求解TSP,则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。 
    [编辑] 
    旅行商问题的历史 
    
      旅行商问题字面上的理解是:有一个推销员,要到n个城市推销商品,他要找出一个包含所有n个城市的具有最短路程的环路。 
    
      TSP的历史很久,最早的描述是1759年欧拉研究的骑士周游问题,即对于国际象棋棋盘中的64个方格,走访64个方格一次且仅一次,并且最终返回到起始点。 
    
      TSP由美国RAND公司于1948年引入,该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。 
    [编辑] 
    旅行商问题的解法[2] 
    
      旅行推销员的问题,我们称之为巡行(Tour),此种问题属于NP-Complete的问题,所以旅行商问题大多集中在启发式解法。Bodin(1983)等人将旅行推销员问题的启发式解法分成三种: 
    
      1、途程建构法(Tour Construction Procedures) 
    
      从距离矩阵中产生一个近似最佳解的途径,有以下几种解法: 
    
      1)最近邻点法(Nearest Neighbor Procedure):一开始以寻找离场站最近的需求点为起始路线的第一个顾客,此后寻找离最后加入路线的顾客最近的需求点,直到最后。 
    
      2)节省法(Clark and Wright Saving):以服务每一个节点为起始解,根据三角不等式两边之和大于第三边之性质,其起始状况为每服务一个顾客后便回场站,而后计算路线间合并节省量,将节省量以降序排序而依次合并路线,直到最后。 
    
      3)插入法(Insertion procedures):如最近插入法、最省插入法、随意插入法、最远插入法、最大角度插入法等。 
    
      2、途程改善法(Tour Improvement Procedure) 
    
      先给定一个可行途程,然后进行改善,一直到不能改善为止。有以下几种解法: 
    
      1)K-Opt(2/3 Opt):把尚未加入路径的K条节线暂时取代目前路径中K条节线,并计算其成本(或距离),如果成本降低(距离减少),则取代之,直到无法改善为止,K通常为2或3。 
    
      2)Or-Opt:在相同路径上相邻的需求点,将之和本身或其它路径交换且仍保持路径方向性,并计算其成本(或距离),如果成本降低(距离减少),则取代之,直到无法改善为止。 
    
      3、合成启发法(Composite Procedure) 
    
      先由途程建构法产生起始途程,然后再使用途程改善法去寻求最佳解,又称为两段解法(two phase method)。有以下几种解法: 
    
      1)起始解求解+2-Opt:以途程建构法建立一个起始的解,再用2-Opt的方式改善途程,直到不能改善为止。 
    
      2)起始解求解+3-Opt:以途程建构法建立一个起始的解,再用3-Opt的方式改善途程,直到不能改善为止。  
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,704
精华内容 1,481
关键字:

旅行商问题