-
TSP_旅行商问题 - 贪心算法
2018-04-12 16:15:20TSP_旅行商问题 - 贪心算法 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内数据格式为:序号 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_旅行商问题 _贪心算法
2019-06-06 08:39:43 -
贪心算法求解 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),并设
则旅行商问题的数学模型可写成如下的线性规划形式:
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如下:- 最小哈密顿链的问题:起点和终点不同;
- 非对称旅行商问题(asymmetric TSP):距离矩阵非对称的旅行商问题;
- 多人旅行商问题(muti-person TSP):由多人完成旅行的旅行商问题;
- 多目标旅行商问题(multi-objective TSP);
- 依次排序问题(Sequence ordering problem ,SOP):这类问题是非对称旅行商问题,在给定一系列顶点和距离矩阵下,寻找最短从顶点 1 到顶点 n 哈密顿链,同时满足限制:某些顶点要在一些顶点之前被连接。
- 载货量受限制的车辆路径问题(Capacitated vehicle routing problem,CVRP):给定 n-1 个顶点和一个仓库,一直顶点和顶点、仓库和顶点的距离,卡车载货量受限制,卡车每次在部分顶点和仓库之间往返,寻求一条经过所有顶点的最短路线。
二、贪心算法
贪心算法,又名贪婪算法,是一种常用的求解最优化问题的简单、迅速的算法。贪心算法总是做出在当前看来最好的选择,它所做的每一个在当前状态下某种意义上是最好的选择即贪心选择,并希望通过每次所作的贪心选择导致最终得到问题最优解。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。
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 问题。
-
TSP旅行商问题算法.rar
2019-10-06 10:01:01TSP问题,旅行商问题算法求解,贪心算法,参数根据情况自己调整 -
贪心算法求解tsp(旅行商问题)
2014-07-09 21:47:56使用贪心算法求解tsp问题,使用vc实现,资源中包含有程序的文档,包含tsp问题说明、贪心算法分析和程序源码。 -
tsp java_基于贪心算法求解TSP问题(JAVA)
2021-02-12 15:24:58一、TPS问题TSP问题(Travelling Salesman Problem)即旅行商问题,又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市...前段时间在搞贪心算法,为了举例,故拿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大师发表,拒绝转载,转载需要作者授权
-
贪心算法之TSP(旅行商)问题C++实现
2020-04-26 23:17:16旅行商问题(TSP)又译为旅行推销员问题、货郎担问题,简称为TSP问题,是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的城市(不可重复)之后,最后再回到原点的最小路径成本。 贪心策略: ... -
TSP_旅行商问题-遗传算法
2018-04-13 16:03:04TSP_旅行商问题-贪心算法 TSP_旅行商问题-模拟退火算法 TSP_旅行商问题-遗传算法 TSP_旅行商问题-基本蚁群算法 问题描述 对于n组城市坐标,寻找最短路径使其经过所有城市并回到起点。 问题数据集:tsp.... -
贪心算法:旅行商问题(TSP)
2016-03-10 15:44:11TSP问题(Traveling Salesman Problem,旅行商问题),由威廉哈密顿爵士和英国数学家克克曼T.P.Kirkman于19世纪初提出。问题描述如下: 有若干个城市,任何两个城市之间的距离都是确定的,现要求一旅行商从某城市... -
java贪心算法旅行售货员问题_MAT之GA:遗传算法(GA)解决M-TSP多旅行商问题
2020-12-29 01:38:51MAT之GA:遗传算法(GA)解决M-TSP多旅行商问题导读 MTSP_GA Multiple Traveling Salesmen Problem (M-TSP) Genetic Algorithm (GA). Finds a (near) optimal solution to the M-TSP by setting up a GA to search ... -
旅行商问题——贪心算法
2018-03-06 14:01:50旅行商问题(TSP) 旅行商问题是一个经典的组合优化问题。 经典的TSP问题可以描述为:一个商品推销员要去若干个城市进行商品推销,该推销员从一个城市出发,需要经过所有城市,回到出发地。应如何选择行进路线,以... -
TSP_旅行商问题-模拟退火算法
2018-04-13 15:13:42TSP_旅行商问题-贪心算法 TSP_旅行商问题-模拟退火算法 TSP_旅行商问题-遗传算法 TSP_旅行商问题-基本蚁群算法 问题描述 对于n组城市坐标,寻找最短路径使其经过所有城市并回到起点。 问题数据集:tsp.... -
TSP_旅行商问题-基本蚁群算法
2018-04-14 15:57:19TSP_旅行商问题-贪心算法 TSP_旅行商问题-模拟退火算法 TSP_旅行商问题-遗传算法 TSP_旅行商问题-基本蚁群算法 基于基本蚁群算法解决连续优化问题 问题描述 对于n组城市坐标,寻找最短路径使其经过所有城市并... -
TSP问题——贪心算法
2018-02-19 21:26:57Written by Robert_Wang in Southwest University of Science And Technology.TSP问题(Traveling Salesman Problem,旅行商问题),由威廉哈密顿爵士和英国数学家克克曼T.P.Kirkman于19世纪初提出。问题描述如下... -
旅行商问题(TSP)三种解决算法 基于C++的编程
2020-12-14 08:30:52旅行商问题是一个经典的问题,此代码用三种方法(枚举法,回溯法,贪心法),并可以对这三种方法进行比较 旅行商问题是一个经典的问题,此代码用三种方法(枚举法,回溯法,贪心法),并可以对这三种方法进行比较 -
旅行商问题(TSP) --- 蛮力法(深度优先遍历算法DFS),贪心算法,动态规划
2019-04-12 09:47:38TSP问题(Traveling Salesman Problem,旅行商问题),由威廉哈密顿爵士和英国数学家克克曼T.P.Kirkman于19世纪初提出。问题描述如下: 有若干个城市,任何两个城市之间的距离都是确定的,现要求一旅行商从某城市... -
贪心算法求解TSP问题
2021-03-30 00:19:16定义:旅行商问题,即TSP问题(Traveling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能... -
贪心算法解决tsp问题
2016-12-05 14:46:24贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的...tsp 问题, 旅行商问题,即TSP问题(Travelling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设 -
贪心算法java_基于贪心算法求解TSP问题(JAVA)
2021-03-06 01:21:18一、TPS问题TSP问题(Travelling Salesman Problem)即旅行商问题,又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市... -
旅行商(TSP)问题,贪心法和动态规划法解答
2019-04-16 20:21:04# 贪心算法求解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问题
2009-09-20 08:14:45用贪心算法写的程序,求解旅行商问题,不错。 -
tsp的贪心算法
2012-10-28 12:13:51用贪心算法解决旅行商问题,有代码,讲解详细 -
python 动态规划 旅行商问题_关于旅行家TSP问题的几种算法 python
2020-12-21 18:29:32问题描述不展开了,感兴趣可以自己搜一下。csdn上这篇文章介绍的很详细,可以看一下 ,http://blog.csdn.net/q345852047/article/details/6626684 感谢作者辛勤码字,我就偷懒啦~1.贪心"""Functions:find_path:Data... -
利用贪心算法求解tsp问题
2017-05-15 19:31:45TSP问题(Travelling Salesman Problem)即旅行商问题,又译为旅行推销员问题、货郎担问题。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发...