tsp旅行商问题c代码（tsp旅行商问题不返回起点）

今天给各位分享tsp旅行商问题c代码的知识，其中也会对tsp旅行商问题不返回起点进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

• 1、蛮力法求解旅行商问题 求C++代码
• 2、已知12个地点间的距离，每个地点都要去一次，最后回到起点。求最短距离。TSP旅行商问题。
• 3、什么是商旅问题啊？用c语言设计，是关于图的程序。最好能给出代码
• 4、C++算法，动态规划法实现TSP问题
• 5、可运行的c语言程序：旅行商求最短路径问题
• 6、C语言遗传算法在求解TSP问题 毕业论文+源代码

蛮力法求解旅行商问题 求C++代码

#includestdlib.h

#includecmath

#includealgorithm

using namespace std;

static double Tmax = 10, Tmin = 0.1, r = 0.999999;

static int k = 100;

inline void random_sele(int fl, int fp, int arr[], int n)

{

do

{

fl = rand() % n;

fp = rand() % n;

} while (fl == arr[fp] || arr[fl] == arr[fp]);

};

inline bool accept(double r1, double r2, double T)

{

const unsigned int MASK((1 30) - 1);

double p = 1.0 / (1.0 + exp((r2 - r1) / T));

unsigned int temp1=((rand()20)^(rand()10)^rand())MASK;

unsigned int temp2=((rand()20)^(rand()10)^rand())MASK;

double res=(1.0*temp1+1.0*temp2/MASK);

return res p*MASK;

}

void set_SA()

{

printf(" Tmax Tmin r k\n");

printf(" %.8f %.8f %.8f %d \n",Tmax,Tmin,r,k);

printf("Input Tmax,Tmin,r,k:\n");

scanf("%lf%lf%lf%d",Tmax,Tmin,r,k);

}

void TSP_SA(int arr[], double evl, int n, double map[][2000])

{

double r1, r2, T = Tmax;

int i, fl, sl, fp, sp;

int show_s=0;

srand(11827);

while (T = Tmin)

{

for (i = 0; i k; i++)

{

random_sele(fl, fp, arr, n);

sl = arr[fl], sp = arr[fp];

r1 = map[fl][sl] + map[fp][sp] + map[sp][arr[sp]];

r2 = map[fl][sp] + map[sp][sl] + map[fp][arr[sp]];

if (accept(r1, r2, T))

{

arr[fp] = arr[sp];

arr[fl] = sp;

arr[sp] = sl;

sl = sp;

evl = evl + r2 - r1;

}

}

if(++show_s==1000000/k)

{

printf("T=%f evl=%f\n",T,evl);

show_s=0;

}

T *= r;

}

}

已知12个地点间的距离，每个地点都要去一次，最后回到起点。求最短距离。TSP旅行商问题。

这个是NP完全问题，只能求近似解,目前没有简单又高效的方法，最简单的就是穷举算法和最邻近算法了,其它的可以考虑插入算法，回溯法，遗传算法，蚁群算法，模拟退火算法等。。。

什么是商旅问题啊？用c语言设计，是关于图的程序。最好能给出代码

旅行商问题（Traveling Saleman Problem，TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。

解决TSP问题的思想有回溯法、贪心法、动态规划法等。

如果动态规划法解决TSP问题，可以参考程序代码：

#include list

#include iostream

using namespace std ;

typedef listint LISTINT;

LISTINT listAnother;

LISTINT list_result;

int d[4][4]={{-1,3,6,7},{2,-1,8,6},{7,3,-1,5,},{7,3,7,-1}};

int matrix_length=4;

int getPath(int n,LISTINT list_org)

{

LISTINT::iterator i;

int minValue;

if(n==1)

{

i=list_org.begin();

minValue= d[*i-1][0];

if(list_org.size()==matrix_length-1)

{

list_result=list_org;

}

}

else

{

int temp;

i=list_org.begin();

temp=*i;

list_org.erase(i);

i=list_org.begin();

minValue=d[temp-1][*(i)-1]+getPath(n-1,list_org);

if(list_org.size()==matrix_length-1)

{

list_result=list_org;

}

for(int j=2;jn;j++)

{

i=list_org.begin();

for(int k=1;kj;k++)

{

i++;

}

int tempvalue=*i;

list_org.erase(i);

list_org.push_front(tempvalue);

i=list_org.begin();

tempvalue=d[temp-1][*(i)-1]+getPath(n-1,list_org);

if(tempvalueminValue)

{

if(list_org.size()==matrix_length-1)

{

list_result=list_org;

}

minValue=tempvalue;

}

}

}

return minValue;

}

int main(int argc, char* argv[])

{

LISTINT list_org;

LISTINT::iterator h;

list_org.push_front(4);

list_org.push_front(3);

list_org.push_front(2);

list_org.push_front(1);

cout"旅行商问题动态规划算法"endl;

cout"路线长度的矩阵表示如下 （-1表示无限大）"endl;

for(int j=0;jmatrix_length;j++){

coutendl;

for(int k=0;kmatrix_length;k++){

cout" "d[j][k];

}

}

coutendl;

cout"计算结果:"getPath(4,list_org)endl;

list_result.push_front(1);

list_result.push_back(1);

cout"要走的路径:----:";

for (h = list_result.begin(); h != list_result.end(); ++h)

cout *h " ";

cout endl;

int i;

cini;

return 0;

}

C++算法，动态规划法实现TSP问题

c++listmatrixiteratoriostream算法

[cpp] view plaincopyprint?

#include

#include

using namespace std ;

typedef list/SPANint LISTINT;

LISTINT listAnother;

LISTINT list_result;

int d[4][4]={{-1,3,6,7},{2,-1,8,6},{7,3,-1,5,},{7,3,7,-1}}; //路径权值

int matrix_length=4;

int getPath(int n,LISTINT list_org)

{

LISTINT::iterator i;

int minValue;

if(n==1)

{

i=list_org.begin();

minValue= d[*i-1][0];

if(list_org.size()==matrix_length-1)

{

list_result=list_org;

}

}

else

{

int temp;

i=list_org.begin();

temp=*i;

list_org.erase(i);

i=list_org.begin();

minValue=d[temp-1][*(i)-1]+getPath(n-1,list_org);

if(list_org.size()==matrix_length-1)

{

list_result=list_org;

}

for(int j=2;j

{

i=list_org.begin();

for(int k=1;k

{

i++;

}

int tempvalue=*i;

list_org.erase(i);

list_org.push_front(tempvalue);

i=list_org.begin();

tempvalue=d[temp-1][*(i)-1]+getPath(n-1,list_org);

if(tempvalue

{

if(list_org.size()==matrix_length-1)

{

list_result=list_org;

}

minValue=tempvalue;

}

}

}

return minValue;

}

int main(int argc, char* argv[])

{

LISTINT list_org;

LISTINT::iterator h;

list_org.push_front(4);

list_org.push_front(3);

list_org.push_front(2);

list_org.push_front(1);

cout"旅行商问题动态规划算法"endl;

cout"路线长度的矩阵表示如下 （-1表示无限大）"endl;

for(int j=0;j

coutendl;

for(int k=0;k

cout" "d[j][k];

}

}

coutendl;

cout"计算结果:"getPath(4,list_org)endl;

list_result.push_front(1);

list_result.push_back(1);

cout"要走的路径:----:";

for (h = list_result.begin(); h != list_result.end(); ++h)

cout *h " ";

cout endl;

int i;

cini;

return 0;

}

可运行的c语言程序：旅行商求最短路径问题

在无向完全图中，对于任意两个顶点vi和vj，我们可以在多项式时间内找到vi和vj这两个顶点之间的所有路径，选择其中路程最短的一条，令S[i,j]表示vi和vj这两个顶点之间最短距离的那条路径。搜索路径S[i,j]，找到vi到达的在S[i,j]上的第一个顶点，记该顶点为vk，将其记录在数组中R[][]，递归查找vi到vk和vk到vj的最短路径及其相应权值，最后将数组D[]中的顶点和权值之和打印出来即为所求，并用画图函数将行经过程画出。

C语言遗传算法在求解TSP问题 毕业论文+源代码

目

录

摘要

I

Abstract

II

引

言

1

第一章

基本遗传算法

2

1.1

遗传算法的产生及发展

3

1.2

基本原理

3

1.3

遗传算法的特点

3

1.4

基本遗传算法描述

5

1.5

遗传算法构造流程

6

第二章

遗传算法的实现技术

6

2.1

编码方法

7

2.1.1

二进制编码

7

2.1.2

格雷码编码

7

2.1.3

符点数编码

8

2.1.4

参数编码

8

2.2

适应度函数

10

2.3

选择算子

10

2.4

交叉算子

10

2.4.1

单点交叉算子

10

2.4.2

双点交叉算子

11

2.4.3

均匀交叉算子

11

2.4.4

部分映射交叉

11

2.4.5

顺序交叉

12

2.5

变异算子

12

2.6

运行参数

12

2.7

约束条件的处理方法

13

2.8

遗传算法流程图

14

第三章

遗传算法在TSP上的应用

15

3.1

TSP问题的建模与描述

15

3.2

对TSP的遗传基因编码方法

16

3.3

针对TSP的遗传操作算子

17

3.3.1

选择算子

17

3.3.1.1

轮盘赌选择

17

3.3.1.2

最优保存策略选择

17

3.3.2

交叉算子

20

3.3.2.1

单点交叉

20

3.3.2.2

部分映射交叉

21

3.3.3

变异算子

23

3.4

TSP的混和遗传算法

26

第四章

实例分析

27

4.1

测试数据

27

4.2

测试结果

27

4.3

结果分析

27

摘

要

TSP

(Traveling

Salesman

Problem)旅行商问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。文章首先介绍了基本遗传算法的基本原理、特点及其基本实现技术；接着针对TSP

问题，论述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子变异算子这三种算子）等方面的应用情况，分别指出几种常用的编码方法的优点和缺点，并且结合TSP的运行实例详细分析了基本遗传算法的4个运行参数群体大小、遗传算法的终止进化代数、交叉概率、变异概率，对遗传算法的求解结果和求解效率的影响，经过多次的测试设定出了它们一组比较合理的取值。最后，简单说明了混合遗传算法在求解TSP问题中的应用并对遗传算法解决TSP问题的前景提出了展望。

关键词：TSP

遗传算法

遗传算子

编码

@@@需要的话按我的名字找我吧

关于tsp旅行商问题c代码和tsp旅行商问题不返回起点的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。