旅行商问题java代码（旅行商问题c语言）

本篇文章给大家谈谈旅行商问题java代码，以及旅行商问题c语言对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、什么是商旅问题啊？用c语言设计，是关于图的程序。最好能给出代码
• 2、可运行的c语言程序：旅行商求最短路径问题
• 3、蛮力法求解旅行商问题 求C++代码
• 4、最短路径

什么是商旅问题啊？用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语言程序：旅行商求最短路径问题

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

蛮力法求解旅行商问题 求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;

}

}

最短路径

// dijsktra.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#define N 12

#include iostream

using namespace std;

const static int soure[N][N] =

{

/*

这填邻接矩阵

*/

};

int min(int arr[N],bool bj[])

{

int tmp = 999;

int temp = 0;

for(int i=0; iN; i++)

{

if((arr[i]tmp)(bj[i]==true))

{

tmp = arr[i];

temp = i;

}

}

return temp;

}

class dijsktra

{

private:

int dist[N][N];

int path[N][N];

int final[N][N];

bool flag[N];

public:

void Doing()

{

for(int i=0; iN; i++)

{

int temp = 0;

for(int j=0; jN; j++)

{

flag[j] = true;

}

for(int j=0; jN; j++)

{

dist[i][j] = soure[i][j];

path[i][j] = i;

}

flag[i] = false;

temp = min(dist[i],flag);

flag[temp] = false;

for(int j=1; jN; j++)

{

for(int k=0; kN; k++)

{

if((flag[k] == true)((soure[temp][k]+dist[i][temp])dist[i][k]))

{

dist[i][k] = soure[temp][k]+dist[i][temp];

path[i][k] = temp;

}

}

temp = min(dist[i],flag);

flag[temp] = false;

}

}

}

void print()

{

for(int i=0; iN; i++)

{

for(int j=0; jN; j++)

{

coutdist[i][j]","path[i][j]" ";

}

coutendl;

}

}

void l_print()

{

int i,j;

cout"请输入i,j的值:";

cinij;

cout"最短路径长度为："dist[i][j]endl;

cout"路径为";

int temp = j;

while(path[i][temp]!=i)

{

couttemp"-";

temp = path[i][temp];

}

couttemp"-";

coutiendl;

}

};

int _tmain(int argc, _TCHAR* argv[])

{

dijsktra test;

test.Doing();

test.print();

test.l_print();

system("pause");

return 0;

}

旅行商问题java代码的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于旅行商问题c语言、旅行商问题java代码的信息别忘了在本站进行查找喔。