TSP_旅行商问题 - 贪心算法

TSP_旅行商问题-贪心算法
TSP_旅行商问题-模拟退火算法
TSP_旅行商问题-遗传算法
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内数据格式为：序号 xixiyiyi

b、设置城市数量N、城市坐标数组citys[num] 

c、计算城市距离矩阵，dic[i][j]dic[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_旅行商问题 - 贪心算法

问题描述:

 

代码：1.

文章目录
一、TSP 概述
1. TSP
2. 数学模型
3. TSP分类
二、贪心算法
1. 算法思路
2. 算法框架
3. 问题
三、贪心算法求解 TSP


一、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~ij~= \begin{cases}
1，边(i, j)在最优路线上 \\
0，其他
\end{cases}$

则旅行商问题的数学模型可写成如下的线性规划形式：

$p = \sum_{i ≠ j} c_{ij}x_{ij}$

$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}$

K 为 V 的所有非空子集，|K| 为集合 K 中所含图 G 的顶点个数。前两个余数意味着对每个顶点而言，出度和入度都为1，后一约束则保证没有任何子回路解的产生，于是满足上述约束的解构成了一条 Hamilton 回路。
3. TSP分类
旅行商问题按把不同的分类方法可以分为不同的种类，这里只介绍距离矩阵划分： 当 cij = cji，(i, j ∈ V)时，问题被称为对称型旅行商问题，反之称为非对称型旅行商问题，非对称旅行商问题可以化为对称型旅行商问题，用对称型的方法求解。当对所有的 i, j, k ∈[1, n]，有不等式 cij + cjk ≥ cik，问题满足三角形不等式的，也称三角型旅行商问题。

旅行售货商问题(TSP)是组合优化领域的经典问题之一,而其中考虑多个旅行商的多旅行商问题(MTSP)是经典的旅行商问题的扩展，多种扩展形式如下：

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

二、贪心算法
贪心算法，又名贪婪算法，是一种常用的求解最优化问题的简单、迅速的算法。贪心算法总是做出在当前看来最好的选择，它所做的每一个在当前状态下某种意义上是最好的选择即贪心选择，并希望通过每次所作的贪心选择导致最终得到问题最优解。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
1. 算法思路
贪心算法以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯。



贪心算法求解具有以下性质：

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

2. 算法框架
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择，而贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
//问题随机初始解
while(能向总目标前进一步)
{
	//利用可行的决策，从候选集合中求出可行解的一个解元素；
}

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 问题。



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

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

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

前段时间在搞贪心算法，为了举例，故拿TSP来开刀，写了段求解算法代码以便有需之人，注意代码考虑可读性从最容易理解角度写，没有优化，有需要可以自行优化！
一、TPS问题
TSP问题(Travelling Salesman Problem)即旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。TSP问题可以分为两类，一类是对称TSP问题(Symmetric TSP)，另一类是非对称问题(Asymmetric TSP)。所有的TSP问题都可以用一个图(Graph)来描述：
V={c1, c2, …, ci, …, cn}，i = 1,2, …, n，是所有城市的集合.ci表示第i个城市，n为城市的数目；
E={(r, s): r,s∈ V}是所有城市之间连接的集合；
C = {crs: r,s∈ V}是所有城市之间连接的成本度量(一般为城市之间的距离)；
如果crs = csr, 那么该TSP问题为对称的，否则为非对称的。
一个TSP问题可以表达为：
求解遍历图G = (V, E, C)，所有的节点一次并且回到起始节点，使得连接这些节点的路径成本最低。
二、贪心算法
贪心算法，又名贪婪算法(学校里老教授都喜欢叫贪婪算法)，是一种常用的求解最优化问题的简单、迅速的算法。贪心算法总是做出在当前看来最好的选择，它所做的每一个在当前状态下某种意义上是最好的选择即贪心选择，并希望通过每次所作的贪心选择导致最终得到问题最优解。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
1、贪心算法的基本思路
从问题的某一个初始解触发逐步逼近给定的目标，以尽可能快地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。大致步骤如下：
1)建立数学模型来描述问题；
2)把求解的问题分成若干个子问题
3)对每一个子问题求解，得到子问题的局部最优解
4)把子问题的局部最优解合成原问题的一个解
2、贪心算法的实现框架
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择，而贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
从问题的某一初始解出发；
while (能朝给定总目标前进一步)
{
利用可行的决策，求出可行解的一个解元素；
}
由所有解元素组合成问题的一个可行解；
3、贪心算法存在的问题
1)不能保证求得的最后解是最佳的；
2)不能用来求最大最小解问题；
3)只能在某些特定条件约束的情况下使用，例如贪心策略必须具备无后效性等。
4、典型的贪心算法使用领域
马踏棋盘、背包、装箱等
三、贪心算法求解TSP问题
贪心策略：在当前节点下遍历所有能到达的下一节点，选择距离最近的节点作为下一节点。基本思路是，从一节点出发遍历所有能到达的下一节点，选择距离最近的节点作为下一节点，然后把当前节点标记已走过，下一节点作为当前节点，重复贪心策略，以此类推直至所有节点都标记为已走节点结束。
我们使用TSP问题依然来自于tsplib上的att48，这是一个对称TSP问题，城市规模为48，其最优值为10628.其距离计算方法下图所示：
好，下面是具体代码：
package noah;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
public class TxTsp {
private int cityNum; // 城市数量
private int[][] distance; // 距离矩阵
private int[] colable;//代表列，也表示是否走过，走过置0
private int[] row;//代表行，选过置0
public TxTsp(int n) {
cityNum = n;
}
private void init(String filename) throws IOException {
// 读取数据
int[] x;
int[] y;
String strbuff;
BufferedReader data = new BufferedReader(new InputStreamReader(
new FileInputStream(filename)));
distance = new int[cityNum][cityNum];
x = new int[cityNum];
y = new int[cityNum];
for (int i = 0; i < cityNum; i++) {
// 读取一行数据，数据格式1 6734 1453
strbuff = data.readLine();
// 字符分割
String[] strcol = strbuff.split(" ");
x[i] = Integer.valueOf(strcol[1]);// x坐标
y[i] = Integer.valueOf(strcol[2]);// y坐标
}
data.close();
// 计算距离矩阵
// ，针对具体问题，距离计算方法也不一样，此处用的是att48作为案例，它有48个城市，距离计算方法为伪欧氏距离，最优值为10628
for (int i = 0; i < cityNum - 1; i++) {
distance[i][i] = 0; // 对角线为0
for (int j = i + 1; j < cityNum; j++) {
double rij = Math
.sqrt(((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j])
* (y[i] - y[j])) / 10.0);
// 四舍五入，取整
int tij = (int) Math.round(rij);
if (tij < rij) {
distance[i][j] = tij + 1;
distance[j][i] = distance[i][j];
} else {
distance[i][j] = tij;
distance[j][i] = distance[i][j];
}
}
}
distance[cityNum - 1][cityNum - 1] = 0;
colable = new int[cityNum];
colable[0] = 0;
for (int i = 1; i < cityNum; i++) {
colable[i] = 1;
}
row = new int[cityNum];
for (int i = 0; i < cityNum; i++) {
row[i] = 1;
}
}
public void solve(){
int[] temp = new int[cityNum];
String path="0";
int s=0;//计算距离
int i=0;//当前节点
int j=0;//下一个节点
//默认从0开始
while(row[i]==1){
//复制一行
for (int k = 0; k < cityNum; k++) {
temp[k] = distance[i][k];
//System.out.print(temp[k]+" ");
}
//System.out.println();
//选择下一个节点，要求不是已经走过，并且与i不同
j = selectmin(temp);
//找出下一节点
row[i] = 0;//行置0，表示已经选过
colable[j] = 0;//列0，表示已经走过
path+="-->" + j;
//System.out.println(i + "-->" + j);
//System.out.println(distance[i][j]);
s = s + distance[i][j];
i = j;//当前节点指向下一节点
}
System.out.println("路径:" + path);
System.out.println("总距离为:" + s);
}
public int selectmin(int[] p){
int j = 0, m = p[0], k = 0;
//寻找第一个可用节点，注意最后一次寻找，没有可用节点
while (colable[j] == 0) {
j++;
//System.out.print(j+" ");
if(j>=cityNum){
//没有可用节点，说明已结束，最后一次为 *-->0
m = p[0];
break;
//或者直接return 0;
}
else{
m = p[j];
}
}
//从可用节点J开始往后扫描，找出距离最小节点
for (; j < cityNum; j++) {
if (colable[j] == 1) {
if (m >= p[j]) {
m = p[j];
k = j;
}
}
}
return k;
}
public void printinit() {
System.out.println("print begin....");
for (int i = 0; i < cityNum; i++) {
for (int j = 0; j < cityNum; j++) {
System.out.print(distance[i][j] + " ");
}
System.out.println();
}
System.out.println("print end....");
}
public static void main(String[] args) throws IOException {
System.out.println("Start....");
TxTsp ts = new TxTsp(48);
ts.init("c://data.txt");
//ts.printinit();
ts.solve();
}
}
四、项目运行介绍
下载项目后，导入eclipse，项目截图如下：
求解结果截图：
五、总结
单从求解结果来看，我个人其实还是能接受这个解，但仔细想想，实际上这个求解结果有太多运气成分在里面，贪心算法毕竟是贪心算法，只能缓一时，而不是长久之计，问题的模型、参数对贪心算法求解结果具有决定性作用，这在某种程度上是不能接受的，于是聪明的人类就发明了各种智能算法(也叫启发式算法)，但在我看来所谓的智能算法本质上就是贪心算法和随机化算法结合，例如传统遗传算法用的选择策略就是典型的贪心选择，正是这些贪心算法和随机算法的结合，我们才看到今天各种各样的智能算法。
注：本文著作权归作者，由demo大师发表，拒绝转载，转载需要作者授权