旅行商问题算法代码（旅行商问题算法复杂度）

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

本文目录一览：

• 1、什么是商旅问题啊？用c语言设计，是关于图的程序。最好能给出代码
• 2、急！！！求用Matlab解决旅行商问题的源代码
• 3、求货郎担问题的matlab算法

什么是商旅问题啊？用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;

}

急！！！求用Matlab解决旅行商问题的源代码

Matlab程序没有，有lingo程序。lingo软件百度一下就有，才几十兆

model:

sets:

city/1..6/:u;

link(city,city):dist,x;

endsets

data:

dist=0 702 454 842 2396 1196

702 0 324 1093 2136 764

454 324 0 1137 2180 798

842 1093 1137 0 1616 1857

2396 2136 2180 1616 0 2900

1196 764 798 1857 2900 0;

enddata

n=@size(city);

min=@sum(link:dist*x);

@for(city(k):@sum(city(i)|i#ne#k:x(i,k))=1;

@sum(city(j)|j#ne#k:x(k,j))=1;);

@for(city(i):@for(city(j)|j#gt#1 #and# i#ne#j:u(i)-u(j)+n*x(i,j)=n-1););!此项约束用于防止出现子巡回路线;

@for(city(i):u(i)=n-1);

@for(link:@bin(x));

end

求货郎担问题的matlab算法

货郎担问题有很多解法，模拟退火，遗传算法，动态规划等。

基于matlab TSP问题遗传算法的实现

%TSP问题（又名：旅行商问题，货郎担问题）遗传算法通用matlab程序

%D是距离矩阵，n为种群个数,建议取为城市个数的1~2倍，

%C为停止代数，遗传到第 C代时程序停止,C的具体取值视问题的规模和耗费的时间而定

%m为适应值归一化淘汰加速指数 ,最好取为1,2,3,4 ,不宜太大

%alpha为淘汰保护指数,可取为0~1之间任意小数,取1时关闭保护功能,最好取为0.8~1.0

%R为最短路径,Rlength为路径长度

function [R,Rlength]=geneticTSP(D,n,C,m,alpha)

[N,NN]=size(D);

farm=zeros(n,N);%用于存储种群

for i=1:n

farm(i,:)=randperm(N);%随机生成初始种群

end

R=farm(1,:);%存储最优种群

len=zeros(n,1);%存储路径长度

fitness=zeros(n,1);%存储归一化适应值

counter=0;

while counterc

for i=1:n

len(i,1)=myLength(D,farm(i,:));%计算路径长度

end

maxlen=max(len);

minlen=min(len);

fitness=fit(len,m,maxlen,minlen);%计算归一化适应值

rr=find(len==minlen);

R=farm(rr(1,1),:);%更新最短路径

FARM=farm;%优胜劣汰，nn记录了复制的个数

nn=0;

for i=1:n

if fitness(i,1)=alpha*rand

nn=nn+1;

FARM(nn,:)=farm(i,:);

end

end

FARM=FARM(1:nn,:);

[aa,bb]=size(FARM);%交叉和变异

while aan

if nn=2

nnper=randperm(2);

else

nnper=randperm(nn);

end

A=FARM(nnper(1),:);

B=FARM(nnper(2),:);

[A,B]=intercross(A,B);

FARM=[FARM;A;B];

[aa,bb]=size(FARM);

end

if aan

FARM=FARM(1:n,:);%保持种群规模为n

end

farm=FARM;

clear FARM

counter=counter+1

end

Rlength=myLength(D,R);

function [a,b]=intercross(a,b)

L=length(a);

if L=10%确定交叉宽度

W=1;

elseif ((L/10)-floor(L/10))=randL10

W=ceil(L/10);

else

W

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