精华内容
下载资源
问答
  • 贪心算法求解 TSP 旅行商问题及其实现

    千次阅读 多人点赞 2020-07-09 21:54:54
    贪心算法求解 TSP 问题得到局部最优解的具体实现,数据集来自 TSPLIB 的 att48 数据集。旅行商问题TSP(Traveling Salesman Problem),又称为货郎担问题,是数学领域中著名问题之一。


    一、TSP 概述

    1. TSP

    旅行商问题即 TSP(Traveling Salesman Problem),又称为货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
    TSP问题是一个组合优化问题,该问题可以被证明具有NPC计算复杂性。从图论的角度来看,该问题实质是给定一个带权完全无向图(顶点表示城市,边表示道路,权重是道路的成本或距离),找一个权值最小的 Hamilton 回路。

    2. 数学模型

    记 G = (V, E) 为赋权图,V = {1, 2 , ……,n} 为顶点集,E 为边集,各顶点间距离为 Cij,已知(Cij > 0,Cij = +∞,i,j ∈ V),并设
    x   i j   = { 1 , 边 ( i , j ) 在 最 优 路 线 上 0 , 其 他 x~ij~= \begin{cases} 1,边(i, j)在最优路线上 \\ 0,其他 \end{cases} x ij ={1(i,j)线0
    则旅行商问题的数学模型可写成如下的线性规划形式:
    p = ∑ i ≠ j c i j x i j p = \sum_{i ≠ j} c_{ij}x_{ij} p=i=jcijxij
    s . t . = { ∑ j ≠ i c i j = 1 , i ∈ V ∑ i ≠ j c i j = 1 , j ∈ V ∑ i , j ∈ S x i j ≤ ∣ K ∣ − 1 , K ⊂ V x i j ∈ { 0 , 1 } i , j ∈ V s.t.=\begin{cases} \sum_{j ≠ i} c_{ij} = 1 ,& i∈V \\ \sum_{i ≠ j} c_{ij} = 1 ,& j∈V \\ \sum_{i,j∈S} x_{ij} ≤|K|-1 ,& K ⊂V \\ x_{ij}∈\{0, 1\} & i,j∈V\\ \end{cases} s.t.=j=icij=1,i=jcij=1,i,jSxijK1,xij{0,1}iVjVKVi,jV
    K 为 V 的所有非空子集,|K| 为集合 K 中所含图 G 的顶点个数。前两个余数意味着对每个顶点而言,出度和入度都为1,后一约束则保证没有任何子回路解的产生,于是满足上述约束的解构成了一条 Hamilton 回路。

    3. TSP分类

    旅行商问题按把不同的分类方法可以分为不同的种类,这里只介绍距离矩阵划分: 当 cij = cji,(i, j ∈ V)时,问题被称为对称型旅行商问题,反之称为非对称型旅行商问题,非对称旅行商问题可以化为对称型旅行商问题,用对称型的方法求解。当对所有的 i, j, k ∈[1, n],有不等式 cij + cjk ≥ cik,问题满足三角形不等式的,也称三角型旅行商问题。
    旅行售货商问题(TSP)是组合优化领域的经典问题之一,而其中考虑多个旅行商的多旅行商问题(MTSP)是经典的旅行商问题的扩展,多种扩展形式1如下:

    1. 最小哈密顿链的问题:起点和终点不同;
    2. 非对称旅行商问题(asymmetric TSP):距离矩阵非对称的旅行商问题;
    3. 多人旅行商问题(muti-person TSP):由多人完成旅行的旅行商问题;
    4. 多目标旅行商问题(multi-objective TSP);
    5. 依次排序问题(Sequence ordering problem ,SOP):这类问题是非对称旅行商问题,在给定一系列顶点和距离矩阵下,寻找最短从顶点 1 到顶点 n 哈密顿链,同时满足限制:某些顶点要在一些顶点之前被连接。
    6. 载货量受限制的车辆路径问题(Capacitated vehicle routing problem,CVRP):给定 n-1 个顶点和一个仓库,一直顶点和顶点、仓库和顶点的距离,卡车载货量受限制,卡车每次在部分顶点和仓库之间往返,寻求一条经过所有顶点的最短路线。

    二、贪心算法

    贪心算法,又名贪婪算法,是一种常用的求解最优化问题的简单、迅速的算法。贪心算法总是做出在当前看来最好的选择,它所做的每一个在当前状态下某种意义上是最好的选择即贪心选择,并希望通过每次所作的贪心选择导致最终得到问题最优解。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。

    1. 算法思路

    贪心算法以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择,就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪心算法不要回溯。
    贪心算法
    贪心算法求解具有以下性质2

    1. 贪心选择性质:一个问题的整体最优解可通过一系列局部的最优解的选择达到,并且每次的选择可以依赖以前作出的选择,但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解
    2. 最优子结构性质:当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。

    2. 算法框架

    贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择,而贪心策略适用的前提是:局部最优策略能导致产生全局最优解。

    //问题随机初始解
    while(能向总目标前进一步)
    {
    	//利用可行的决策,从候选集合中求出可行解的一个解元素;
    }
    

    3. 问题

    贪心算法也存在如下问题3

    • 不能保证求得的最后解是最佳的;
    • 不能用来求最大最小解问题;
    • 只能在某些特定条件约束的情况下使用,例如贪心策略必须具备无后效性等。

    三、贪心算法求解 TSP

    贪心策略基本思路:从一节点出发遍历所有能到达的下一节点,选择距离最近的节点作为下一节点,然后把当前节点标记已走过,下一节点作为当前节点,重复贪心策略,以此类推直至所有节点都标记为已走节点结束。
    TSP 数据集来自于 TSPLIB 上的 att48.tsp,这是一个对称 TSP 问题,城市规模为48,其最优值为10628。其距离计算方法如下:

    The edge weight type ATT corresponds to a special “pseudo-Euclidean” distance function. Let x[ i ] and y[ i ] be the coordinates of node i. The distance between two points i and j is computed as follows:
    double dis = sqrt((pow((double)x[i] - x[j], 2) / 10 + pow((double)y[i] - y[j], 2) / 10 ));
    int disInt = (int)dis;
    if(disInt < dis) dis = disInt + 1;
    else dis = disInt;

    具体代码如下:

    /*********************************************************************************************************************
     * TSP 算例来自TSPLIB,att48.tsp 数据集,其中有 48 个城市,距离为伪欧式距离
     * TSPLIB is a library of sample instances for the TSP (and related problems)from various sources and of various types.
     * 目前最佳解总距离为 10628,其中距离的计算方式为 sqrt((x*x + y*y)/10)
     * 使用贪心策略求解,解集总距离为 12861,可见贪心策略只是局部最优解
    **********************************************************************************************************************/
    #define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<math.h>
    #include<stdlib.h>
    #include<time.h>
    
    // 城市数量 N
    #define N 48
    // 城市距离矩阵
    int distance[N][N];
    
    /***********************************************************************
     * Function   :init()
     * Description:从文件中读取城市坐标,并计算城市之间的距离 distance[N][N] 
     * Input      :void
     * Output     :void
     * Return     :void
     ***********************************************************************/
    void init()
    {
    	//城市的 x 和 y 坐标
    	int x[N] = { 0 };
    	int y[N] = { 0 };
    	//从 data.txt 文件读取数据
    	FILE* fp;
    	if ((fp = fopen("..//att48.txt", "r")) == NULL)
    		//if ((fp = fopen("..//kroB100.txt", "r")) == NULL)
    	{
    		printf("can not open the file!");
    		exit(0);
    	}
    	while (!feof(fp))
    	{
    		int count;
    		fscanf(fp, "%d", &count);
    		fscanf(fp, "%d%d", &x[count - 1], &y[count - 1]);
    	}
    	fclose(fp);
    	//计算城市之间距离
    	for (int i = 0; i < N - 1; i++)
    	{
    		distance[i][i] = 0;				// 对角线为0
    		for (int j = i + 1; j < N; j++)
    		{
    			double dis = sqrt((pow((double)x[i] - x[j], 2) / 10 + pow((double)y[i] - y[j], 2) / 10));
    			int disInt = (int)dis;
    			distance[i][j] = dis == disInt ? disInt : disInt + 1;
    			distance[j][i] = distance[i][j];
    		}
    	}
    	distance[N - 1][N - 1] = 0;
    }
    
    /***********************************************************************
     * Function   :TSPGreedyAlgorithm()
     * Description:贪心策略求解 TSP 问题
     * Input      :void
     * Output     :TSP 路径和对应的总距离
     * Return     :void
     ***********************************************************************/
    void TSPGreedyAlgorithm()
    {
    	//总路程
    	int totalDistance = 0;		
    	//默认从 0 开始遍历
    	int current = 0;	
    	//标识城市是否被访问,访问过置为 1
    	bool visit[N] = { false };
    	visit[0] = 1;
    	printf("TSP 路径为:%d ->", 1);
    
    	//遍历 N - 1 次
    	for (int i = 1; i < N; i++)
    	{
    		//设置较大的距离初始值用来选取最近邻
    		int min_distance = 0x7fffffff;
    		//保存当前最近邻城市
    		int temp;
    		//循环选取城市
    		for (int j = 1; j < N; j++)
    		{
    			if (!visit[j] && distance[current][j] < min_distance)
    			{
    				min_distance = distance[current][j];
    				temp = j;
    			}
    		}
    		visit[temp] = 1;
    		current = temp;
    		totalDistance += min_distance;
    		printf(" %d ->", temp + 1);
    	}
    	totalDistance += distance[current][0];
    	printf(" %d\n", 1);
    	printf("TSP 总距离为:%d\n", totalDistance);
    }
    
    int main()
    {
    	init();
    	TSPGreedyAlgorithm();
    	return 0;
    }
    

    结果如下:
    结果截图
    可见,贪心算法求解 TSP 问题只能得到局部最优解,如果需要得到最优解,需要采用局部搜索算法等非精确性算法,作者将在后文中继续介绍其他方法求解 TSP 问题。


    1. The multiple traveling salesman problem: an overview of formulations and solution procedures. ↩︎

    2. 计算机算法设计与分析研究,新华出版社,2015.09. ↩︎

    3. 计算机算法基础,西南交通大学出版社,2015.02. ↩︎

    展开全文
  • 使用贪心算法求解tsp问题,使用vc实现,资源中包含有程序的文档,包含tsp问题说明、贪心算法分析和程序源码。
  • TSP_旅行商问题 - 贪心算法

    万次阅读 多人点赞 2018-04-12 16:15:20
    TSP_旅行商问题 - 贪心算法 TSP_旅行商问题-贪心算法 TSP_旅行商问题-模拟退火算法 TSP_旅行商问题-遗传算法 TSP_旅行商问题-基本蚁群算法 问题描述 寻找最短路径使得其经过所有城市 测试数据集:tsp.eil51...

    TSP_旅行商问题 - 贪心算法

    问题描述

    寻找最短路径使得其经过所有城市
    测试数据集:tsp.eil51问题

    1 37 52
    2 49 49
    3 52 64
    4 20 26
    5 40 30
    6 21 47
    7 17 63
    8 31 62
    9 52 33
    10 51 21
    11 42 41
    12 31 32
    13 5 25
    14 12 42
    15 36 16
    16 52 41
    17 27 23
    18 17 33
    19 13 13
    20 57 58
    21 62 42
    22 42 57
    23 16 57
    24 8 52
    25 7 38
    26 27 68
    27 30 48
    28 43 67
    29 58 48
    30 58 27
    31 37 69
    32 38 46
    33 46 10
    34 61 33
    35 62 63
    36 63 69
    37 32 22
    38 45 35
    39 59 15
    40 5 6
    41 10 17
    42 21 10
    43 5 64
    44 30 15
    45 39 10
    46 32 39
    47 25 32
    48 25 55
    49 48 28
    50 56 37
    51 30 40

    最优解:426

    算法思想

    选择下一城市的策略为
    距当前城市最近且未被访问过的城市

    算法流程

    准备工作(初始化)

    a、读取数据,txt内数据格式为:序号 xi x i yi y i
    b、设置城市数量N、城市坐标数组citys[num]
    c、计算城市距离矩阵, dic[i][j] d i c [ i ] [ j ] 为第i个城市到第j个城市的距离

    开始模拟算法流程
    seq[num]记录路径,
    visit[num]标记是否已访问,

    a、初始化visit数组为false未访问;
    b、随机选择起点城市,记录路径,标记visit[seq[0]]为true已访问;

    进入循环体
    循环N-1次

    a、遍历所有城市,寻找未访问且与上一城市seq[i-1]距离最近的城市mini;
    b、记录路径,标记visit[mini]为true已访问;

    结束循环

    计算路径能量值

    测试结果

    当前结果
    当前结果
    最优结果
    最优结果

    算法代码

    #include<iostream>
    #include<ctime>
    #include<cmath>
    #include<fstream>
    #include<algorithm>
    using namespace std;
    const int num = 1000;//city number
    const int width = 100;
    const int height = 100;
    
    typedef struct node {
        int x;
        int y;
    }city;
    city citys[num];//citys
    double dic[num][num];//distance from two citys;
    bool visit[num];//visited
    int N;//real citys
    int seq[num];//
    double answer;
    void init() {//set N&&x-y设置N和citys[num]
        N = 51;
        citys[0].x = 37; citys[0].y = 52;
        citys[1].x = 49; citys[1].y = 49;
        citys[2].x = 52; citys[2].y = 64;
        citys[3].x = 20; citys[3].y = 26;
        citys[4].x = 40; citys[4].y = 30;
        citys[5].x = 21; citys[5].y = 47;
        citys[6].x = 17; citys[6].y = 63;
        citys[7].x = 31; citys[7].y = 62;
        citys[8].x = 52; citys[8].y = 33;
        citys[9].x = 51; citys[9].y = 21;
        citys[10].x = 42; citys[10].y = 41;
        citys[11].x = 31; citys[11].y = 32;
        citys[12].x = 5; citys[12].y = 25;
        citys[13].x = 12; citys[13].y = 42;
        citys[14].x = 36; citys[14].y = 16;
        citys[15].x = 52; citys[15].y = 41;
        citys[16].x = 27; citys[16].y = 23;
        citys[17].x = 17; citys[17].y = 33;
        citys[18].x = 13; citys[18].y = 13;
        citys[19].x = 57; citys[19].y = 58;
        citys[20].x = 62; citys[20].y = 42;
        citys[21].x = 42; citys[21].y = 57;
        citys[22].x = 16; citys[22].y = 57;
        citys[23].x = 8; citys[23].y = 52;
        citys[24].x = 7; citys[24].y = 38;
        citys[25].x = 27; citys[25].y = 68;
        citys[26].x = 30; citys[26].y = 48;
        citys[27].x = 43; citys[27].y = 67;
        citys[28].x = 58; citys[28].y = 48;
        citys[29].x = 58; citys[29].y = 27;
        citys[30].x = 37; citys[30].y = 69;
        citys[31].x = 38; citys[31].y = 46;
        citys[32].x = 46; citys[32].y = 10;
        citys[33].x = 61; citys[33].y = 33;
        citys[34].x = 62; citys[34].y = 63;
        citys[35].x = 63; citys[35].y = 69;
        citys[36].x = 32; citys[36].y = 22;
        citys[37].x = 45; citys[37].y = 35;
        citys[38].x = 59; citys[38].y = 15;
        citys[39].x = 5; citys[39].y = 6;
        citys[40].x = 10; citys[40].y = 17;
        citys[41].x = 21; citys[41].y = 10;
        citys[42].x = 5; citys[42].y = 64;
        citys[43].x = 30; citys[43].y = 15;
        citys[44].x = 39; citys[44].y = 10;
        citys[45].x = 32; citys[45].y = 39;
        citys[46].x = 25; citys[46].y = 32;
        citys[47].x = 25; citys[47].y = 55;
        citys[48].x = 48; citys[48].y = 28;
        citys[49].x = 56; citys[49].y = 37;
        citys[50].x = 30; citys[50].y = 40;
    }
    void set_dic() {//set distance
        for (int i = 0; i<N; ++i) {
            for (int j = 0; j<N; ++j) {
                dic[i][j] = sqrt(pow(citys[i].x - citys[j].x, 2) + pow(citys[i].y - citys[j].y, 2));
            }
        }
    }
    double dic_two_point(city a, city b) {
        return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
    }
    double count_energy(int* conf) {
        double temp = 0;
        for(int i = 1; i<N; ++i){
        temp += dic_two_point(citys[conf[i]], citys[conf[i - 1]]);
        }
        temp += dic_two_point(citys[conf[0]], citys[conf[N - 1]]);
        return temp;
    }
    void moni() {
        memset(visit, false, sizeof(visit));
        int temp = rand() % N;
        seq[0] = temp;
        visit[temp] = true;
        int mini = -1;
        int ans = 1e9;
        for (int i = 1; i < N; ++i) {//第i位应该经过的点
            ans = 1e9;
            mini = -1;
            for (int j = 0; j < N; ++j) {
                if (!visit[j] && ans > dic[seq[i - 1]][j]) {
                    ans = dic[seq[i - 1]][j];
                    mini = j;
                }
            }
            seq[i] = mini;
            visit[mini] = true;
        }
        answer=count_energy(seq);
    }
    void test() {//读取数据,设置N和citys[num]
        ifstream ifile("data.txt");
        if (!ifile) {
            cout << "open field\n";
            return;
        }
        while(!ifile.eof()){
            int te = 0;
            ifile >> te;
            ifile >> citys[te - 1].x >> citys[te - 1].y;
            N = te;
        }
    }
    void output() {
        cout << "the best road is : \n";
        for (int i = 0; i < N; ++i) {
            cout << seq[i];
            if (i == N - 1)
                cout << endl;
            else
                cout << " -> ";
        }
        cout << "the length of the road is " << answer << endl;
    }
    int main(){
        srand(time(nullptr));
        int t;
        while (cin >> t) {//仅作为重启算法开关使用,无意义
            init();//使用程序内置数据使用init()函数,
            //test();//使用文件读取数据使用test()函数,
            set_dic();
            moni();
            output();
        }
        return 0;
    }
    展开全文
  • tsp问题贪心算法求解

    热门讨论 2011-12-25 23:38:25
    任意输入城市数目,然后输入各城市间距离,运行显示各条旅行路线 使用贪心算法,找出次优解
  • TSP旅行商问题算法.rar

    2019-10-06 10:01:01
    TSP问题旅行商问题算法求解,贪心算法,参数根据情况自己调整
  • 贪心算法TSP(旅行商)问题C++实现

    千次阅读 2020-04-26 23:17:16
    旅行商问题TSP)又译为旅行推销员问题、货郎担问题,简称为TSP问题,是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的城市(不可重复)之后,最后再回到原点的最小路径成本。 贪心策略: ...

    贪心算法之TSP问题

    贪心算法
    贪心算法(又称贪婪算法)是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。 所以不能保证最后结果是最优解,一般是最优解的近似解,但是贪心算法的效率高。

    问题描述
    旅行商问题(TSP)又译为旅行推销员问题、货郎担问题,简称为TSP问题,是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的城市(不可重复)之后,最后再回到原点的最小路径成本。

    贪心策略
    1.从某一个城市开始,每次选择一个城市,直到所有的城市被走完。
    2.每次在选择下一个城市的时候,只考虑当前情况,保证迄今为止经过的路径总距离最小。通过该算法求得的解并不一定是最优的,只是最优解的近似解。传统的贪心算法虽然能求得最优解,但是时间空间性能太差,所以一般采用改良的贪心算法。

    应用领域

    1、如何规划最合理高效的道路交通,以减少拥堵;

    2、如何更好地规划物流,以减少运营成本;

    3、在互联网环境中如何更好地设置节点,以更好地让信息流动等。

    代码实现

    #include<iostream>
    #define n 4
    using namespace std;
    int s[n] = {-1,-1,-1,-1} ;// 记录已经访问过的城市, 初始化为-1,表示未访问
    int distance[n][n] = {{10000,3,6,5},// 城市间距离数组,10000表示自己到自己的距离
                          {3,10000,5,4},
                          {6,5,10000,2},
                          {5,4,2,10000}};
                                      
    bool visit(int k) {//判断城市k是否被访问过 
        for (int i = 0; i < n ; i++) 
            if (s[i] == k) return 1 ;
            	return 0;
    }
    
    void clostCityDistance(int currentCity) { //查找距离当前城市最近的下一个城市       
    	int Dtemp = 10000;//Dtemp暂时存储当前最小路径的值 
        for (int i = 0; i < n; i++) 
    	{        
            if ( visit(i) == 0 && ::distance[i][s[currentCity]] <Dtemp ) 
    		{
                Dtemp = ::distance[i][s[currentCity]] ;
                s[currentCity+1] = i ;//若该城市没有被访问过,且距离当前城市最短,则将访问该城市,存入s[]数组中 
            }
       }
            
    for (int i = 0; i < n; i++) 
    {//查找是否还有未访问的城市 
        if ( s[i] == -1 )              
            clostCityDistance(s[currentCity+1]);         
        }
    } 
    void TSP() {
    int sum = 0 ;// 最短路径之和 
    s[0] = 2;//从第2个城市出发 ,初始化出发的城市,可在0,1,2,3中任意一个 
    clostCityDistance(s[0]) ;//寻找距离2城市最近的城市   
        for (int i=0; i < n ; i++) {            
            if (i == n -1) {
                printf("%d",s[i] );
                printf("->%d 距离为:%d\n",s[0],::distance [ s[n-1] ] [s[0]]);
                printf("总距离是  %d\n",sum += ::distance [ s[n-1] ] [s[0]] );
                break ;
            }
                
                printf("%d->%d 距离为:%d \n",s[i],s[i+1], ::distance[ s[i] ][ s[i+1] ]  );
                sum += ::distance[ s[i] ][ s[i+1] ] ;
            }
         
        }
    
    int main() {    
        TSP() ;
        return 0;
    }
    

    运行结果

    在这里插入图片描述

    展开全文
  • 旅行商问题是一个经典的问题,此代码用三种方法(枚举法,回溯法,贪心法),并可以对这三种方法进行比较 旅行商问题是一个经典的问题,此代码用三种方法(枚举法,回溯法,贪心法),并可以对这三种方法进行比较
  • TSP旅行商问题分支限界法和回溯法源码 旅行商(TSP)问题 计算复杂性高,NP-hard问题,无有效的(复杂性为多项式级别)的解法 Metric TSP 欧式空间满足三角形关系 应用: 军事、通信、电路板设计、大规模集成...
  • TSP_旅行商问题 _贪心算法

    千次阅读 2019-06-06 08:39:43
    TSP_旅行商问题 - 贪心算法 问题描述: 代码:1.

    TSP_旅行商问题 - 贪心算法

    问题描述:

     

    代码:1.

    展开全文
  • 旅行商问题 贪心算法

    千次阅读 2019-07-23 09:22:39
    问题描述 这个问题要求找出一条n个给定的城市间的最短路径,使我们在回到触发的城市之前,对每个城市都只访问一次。 解决方法 ... 贪心算法 */ #include <stdio.h> # include <stdlib.h&...
  • 贪心算法旅行商问题TSP

    万次阅读 多人点赞 2016-03-10 15:44:11
    TSP问题(Traveling Salesman Problem,旅行商问题),由威廉哈密顿爵士和英国数学家克克曼T.P.Kirkman于19世纪初提出。问题描述如下: 有若干个城市,任何两个城市之间的距离都是确定的,现要求一旅行商从某城市...
  • 利用贪心算法求解TSP问题(C语言实现)

    千次阅读 多人点赞 2020-05-05 23:11:20
    旅行商问题,即TSP问题(Traveling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次...
  • 贪心算法解决TSP问题

    热门讨论 2009-09-20 08:14:45
    贪心算法写的程序,求解旅行商问题,不错。
  • 文章目录前言一、TSP旅行商是什么?二、各种算法求解TSP问题1.遗传算法2.蚁群算法3.禁忌搜索算法4.模拟退火算法总结 前言 旅行推销员问题(英语:Travelling salesman problem, TSP)是这样一个问题:给定一系列...
  • 贪心算法解决TSP问题

    万次阅读 2018-06-19 23:55:11
    旅行商问题,即TSP问题(Traveling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次...
  • # 贪心算法求解TSP,得到的为局部最优解 # 需要提前给出path_length, path_vertexs = [],[] def find_path(start, n, end): path_vertexs.append(start) row = C[start] # C为代价矩阵 copy_row = row[:] for i ....
  • TSP问题的python简单解决方案(贪婪、爬山、退火) *该方案中使用直角坐标系来表示各个城市的位置,...贪心算法:从起点(0, 0)出发,选择最近的点;再从该点出发,选择最近的点;重复执行该步骤,直到没有点时返回起点
  • 本文主要是用以下方法解决旅行商问题TSP问题) 详情见:https://blog.csdn.net/weixin_42715356/article/details/83089108 穷举策略 自顶向下的算法:深度优先搜索算法->回溯法 :广度优先搜索算法->分支限界...
  • 用Python解决TSP问题(1)——贪心算法

    万次阅读 多人点赞 2018-06-25 20:27:28
    旅行商问题(TravelingSalesmanProblem,TSP)一个商品推销员要去若干个城市推销商品,该推销员从一个城市出发,需要遍历所有城市一次且只能一次,回到出发地。应如何选择行进路线,以使总的行程最短。目前解决TSP问题...
  • 旅行商问题——贪心算法

    千次阅读 2018-03-06 14:01:50
    旅行商问题TSP旅行商问题是一个经典的组合优化问题。 经典的TSP问题可以描述为:一个商品推销员要去若干个城市进行商品推销,该推销员从一个城市出发,需要经过所有城市,回到出发地。应如何选择行进路线,以...
  • 贪心算法求解TSP问题

    2021-03-30 00:19:16
    定义:旅行商问题,即TSP问题(Traveling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能...
  • 贪心算法求解TSP问题(python)

    千次阅读 2020-06-13 16:49:56
    这里使用贪心算法求解TSP问题的python版本 # dist 为距离矩阵,start_index 为起始位置 def tsp_quick(dist: list, start_index: int): sum_distance, seq_result, n = 0, [start_index, ], len(dist) for path_...
  • 本报告仅供参考,不足之处请指正,版权由博主所有,未经同意禁止应用于非法用途,请下载者自觉。
  • TSP问题(Traveling Salesman Problem,旅行商问题),由威廉哈密顿爵士和英国数学家克克曼T.P.Kirkman于19世纪初提出。问题描述如下: 有若干个城市,任何两个城市之间的距离都是确定的,现要求一旅行商从某城市...
  • * 贪心算法求解TSP问题 * 按照贪心算法的思想每次选取距离当前城市距离最近的城市,直到所有城市选取完毕 */ public class GreedyAlgorithm { double s=0;//总距离值 private int citynumbers;//城市数目 ...
  • 一、TPS问题TSP问题(Travelling Salesman Problem)即旅行商问题,又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市...
  • 本文用贪婪算法和最小路径算法解决TSP问题,包含源代码,并且已经调试过了,可以使用
  • TSP问题——贪心算法

    千次阅读 2018-02-19 21:26:57
    Written by Robert_Wang in Southwest University of Science And Technology.TSP问题(Traveling Salesman Problem,旅行商问题),由威廉哈密顿爵士和英国数学家克克曼T.P.Kirkman于19世纪初提出。问题描述如下...
  • 旅行商问题(TSP)的启发式求解算法

    万次阅读 2018-03-02 22:25:40
    TSP问题(Travelling Salesman Problem)即旅行商问题,又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 692
精华内容 276
关键字:

tsp旅行商问题贪心算法