呵呵，好有钱，给了100块呢，我就给了5块，哈哈~~
追问：如何用MATLAB解决旅行商问题？请附详细资料
function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q) %%========================================================================= %% ACATSP.m %% Ant colony Algorithm for Traveling Salesman Problem %% ChengAihua,PLA Information Engineering University,ZhengZhou,China %% Email:aihuacheng@gmail.com %% All rights reserved %%------------------------------------------------------------------------- %% 主要符号说明 %% C n个城市的坐标，n×2的矩阵 %% NC_max 最大迭代次数 %% m 蚂蚁个数 %% Alpha 表征信息素重要程度的参数 %% Beta 表征启发式因子重要程度的参数 %% Rho 信息素蒸发系数 %% Q 信息素增加强度系数 %% R_best 各代最佳路线 %% L_best 各代最佳路线的长度 %%========================================================================= %%第一步：变量初始化 n=size(C,1);%n表示问题的规模（城市个数） D=zeros(n,n);%D表示完全图的赋权邻接矩阵 for i=1:n for j=1:n if i~=j D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5; else D(i,j)=ePS; end D(j,i)=D(i,j); end end Eta=1./D;%Eta为启发因子，这里设为距离的倒数 Tau=ones(n,n);%Tau为信息素矩阵 Tabu=zeros(m,n);%存储并记录路径的生成 NC=1;%迭代计数器 R_best=zeros(NC_max,n);%各代最佳路线 L_best=inf.*ones(NC_max,1);%各代最佳路线的长度 L_ave=zeros(NC_max,1);%各代路线的平均长度 while NC<=NC_max%停止条件之一：达到最大迭代次数 %%第二步：将m只蚂蚁放到n个城市上 Randpos=[]; for i=1:(ceil(m/n)) Randpos=[Randpos,randPErm(n)]; end Tabu(:,1)=(Randpos(1,1:m))'; %%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游 for j=2:n for i=1:m visited=Tabu(i,1:(j-1));%已访问的城市 J=zeros(1,(n-j+1));%待访问的城市 P=J;%待访问城市的选择概率分布 Jc=1; for k=1:n if length(find(visited==k))==0 J(Jc)=k; Jc=Jc+1; end end %下面计算待选城市的概率分布 for k=1:length(J) P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta); end P=P/(sum(P)); %按概率原则选取下一个城市 PCum=cumsum(P); Select=find(Pcum>=rand); to_visit=J(selec(1)); Tabu(i,j)=to_visit; end end if NC>=2 Tabu(1,:)=R_best(NC-1,:); end %%第四步：记录本次迭代最佳路线 L=zeros(m,1); for i=1:m R=Tabu(i,:); for j=1:(n-1) L(i)=L(i)+D(R(j),R(j+1)); end L(i)=L(i)+D(R(1),R(n)); end L_best(NC)=min(L); pos=find(L==L_best(NC)); R_best(NC,:)=Tabu(pos(1),:); L_ave(NC)=mean(L); NC=NC+1 %%第五步：更新信息素 Delta_Tau=zeros(n,n); for i=1:m for j=1:(n-1) Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i); end Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i); end Tau=(1-Rho).*Tau+Delta_Tau; %%第六步：禁忌表清零 Tabu=zeros(m,n); end %%第七步：输出结果 Pos=find(L_best==min(L_best)); Shortest_Route=R_best(Pos(1),:) Shortest_Length=L_best(Pos(1)) subplot(1,2,1) DrawRoute(C,Shortest_Route) subplot(1,2,2) plot(L_best) hold on plot(L_ave) function DrawRoute(C,R) %%========================================================================= %% DrawRoute.m %% 画路线图的子函数 %%------------------------------------------------------------------------- %% C Coordinate 节点坐标，由一个N×2的矩阵存储 %% R Route 路线 %%========================================================================= N=length(R); scatter(C(:,1),C(:,2)); hold on plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)]) hold on for ii=2:N plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)]) hold on end 设置初始参数如下： m=31;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100; 31城市坐标为： 1304 2312 3639 1315 4177 2244 3712 1399 3488 1535 3326 1556 3238 1229 4196 1004 4312 790 4386 570 3007 1970 2562 1756 2788 1491 2381 1676 1332 695 3715 1678 3918 2179 4061 2370 3780 2212 3676 2578 4029 2838 4263 2931 3429 1908 3507 2367 3394 2643 3439 3201 2935 3240 3140 3550 2545 2357 2778 2826 2370 2975
补充：
多旅行商问题matlab程序
[code]function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)
%%=========================================================================
%% ACATSP.m
%% Ant colony Algorithm for Traveling Salesman Problem
%% ChengAihua,PLA Information Engineering University,ZhengZhou,China
%% Email:aihuacheng@gmail.com
%% All rights reserved
%%-------------------------------------------------------------------------
%% 主要符号说明
%% C n个城市的坐标，n×2的矩阵
%% NC_max 最大迭代次数
%% m 蚂蚁个数
%% Alpha 表征信息素重要程度的参数
%% Beta 表征启发式因子重要程度的参数
%% Rho 信息素蒸发系数
%% Q 信息素增加强度系数
%% R_best 各代最佳路线
%% L_best 各代最佳路线的长度
%%=========================================================================
%%第一步：变量初始化
n=size(C,1);%n表示问题的规模（城市个数）
D=zeros(n,n);%D表示完全图的赋权邻接矩阵
for i=1:n
for j=1:n
if i~=j
D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
else
D(i,j)=eps;
end
D(j,i)=D(i,j);
end
end
Eta=1./D;%Eta为启发因子，这里设为距离的倒数
Tau=ones(n,n);%Tau为信息素矩阵
Tabu=zeros(m,n);%存储并记录路径的生成
NC=1;%迭代计数器
R_best=zeros(NC_max,n);%各代最佳路线
L_best=inf.*ones(NC_max,1);%各代最佳路线的长度
L_ave=zeros(NC_max,1);%各代路线的平均长度
while NC<=NC_max%停止条件之一：达到最大迭代次数
%%第二步：将m只蚂蚁放到n个城市上
Randpos=[];
for i=1:(ceil(m/n))
Randpos=[Randpos,randperm(n)];
end
Tabu(:,1)=(Randpos(1,1:m))';
%%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游
for j=2:n
for i=1:m
visited=Tabu(i,1:(j-1));%已访问的城市
J=zeros(1,(n-j+1));%待访问的城市
P=J;%待访问城市的选择概率分布
Jc=1;
for k=1:n
if length(find(visited==k))==0
J(Jc)=k;
Jc=Jc+1;
end
end
%下面计算待选城市的概率分布
for k=1:length(J)
P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);
end
P=P/(sum(P));
%按概率原则选取下一个城市
Pcum=cumsum(P);
Select=find(Pcum>=rand);
to_visit=J(selec(1));
Tabu(i,j)=to_visit;
end
end
if NC>=2
Tabu(1,:)=R_best(NC-1,:);
end
%%第四步：记录本次迭代最佳路线
L=zeros(m,1);
for i=1:m
R=Tabu(i,:);
for j=1:(n-1)
L(i)=L(i)+D(R(j),R(j+1));
end
L(i)=L(i)+D(R(1),R(n));
end
L_best(NC)=min(L);
pos=find(L==L_best(NC));
R_best(NC,:)=Tabu(pos(1),:);
L_ave(NC)=mean(L);
NC=NC+1
%%第五步：更新信息素
Delta_Tau=zeros(n,n);
for i=1:m
for j=1:(n-1)
Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);
end
Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);
end
Tau=(1-Rho).*Tau+Delta_Tau;
%%第六步：禁忌表清零
Tabu=zeros(m,n);
end
%%第七步：输出结果
Pos=find(L_best==min(L_best));
Shortest_Route=R_best(Pos(1),:)
Shortest_Length=L_best(Pos(1))
subplot(1,2,1)
DrawRoute(C,Shortest_Route)
subplot(1,2,2)
plot(L_best)
hold on
plot(L_ave)
function DrawRoute(C,R)
%%=========================================================================
%% DrawRoute.m
%% 画路线图的子函数
%%-------------------------------------------------------------------------
%% C Coordinate 节点坐标，由一个N×2的矩阵存储
%% R Route 路线
%%=========================================================================
N=length(R);
scatter(C(:,1),C(:,2));
hold on
plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])
hold on
for ii=2:N
plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)])
hold on
end
设置初始参数如下：
m=31;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100;
31城市坐标为：
1304 2312
3639 1315
4177 2244
3712 1399
3488 1535
3326 1556
3238 1229
4196 1004
4312 790
4386 570
3007 1970
2562 1756
2788 1491
2381 1676
1332 695
3715 1678
3918 2179
4061 2370
3780 2212
3676 2578
4029 2838
4263 2931
3429 1908
3507 2367
3394 2643
3439 3201
2935 3240
3140 3550
2545 2357
2778 2826
2370 2975[/code]
运行后得到15602的巡游路径，路线图和收敛曲线如下： 评论
遗传算法求解旅行商(TSP)问题?十万火急
早熟现象这叫，可能和你的变异概率、交叉概率设置，选择机制都有关 评论
旅行商问题 分支限界
编辑词条 分支限界算法
分支定界 (branch and bound) s搜索法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。 利用分支定界算法对问题的解空间树进行搜索，它的搜索策略是： 1 ．产生当前扩展结点的所有孩子结点； 2 ．在产生的孩子结点中，抛弃那些不可能产生可行解（或最优解）的结点； 3 ．将其余的孩子结点加入活结点表； 4 ．从活结点表中选择下一个活结点作为新的扩展结点。 如此循环，直到找到问题的可行解（最优解）或活结点表为空。 从活结点表中选择下一个活结点作为新的扩展结点，根据选择方式的不同，分支定界算法通常可以分为两种形式： 1 ． FIFO(First In First Out) 分支定界算法：按照先进先出原则选择下一个活结点作为扩展结点，即从活结点表中取出结点的顺序与加入结点的顺序相同。 2 ．最小耗费或最大收益分支定界算法：在这种情况下，每个结点都有一个耗费或收益。如果要查找一个具有最小耗费的解，那么要选择的下一个扩展结点就是活结点表中具有最小耗费的活结点；如果要查找一个具有最大收益的解，那么要选择的下一个扩展结点就是活结点表中具有最大收益的活结点。 又称分支定界搜索法。过程系统综合的一类方法。该法是将原始问题分解，产生一组子问题。分支是将一组解分为几组子解，定界是建立这些子组解的目标函数的边界。如果某一子组的解在这些边界之外，就将这一子组舍弃（剪枝）。分支定界法原为运筹学中求解整数规划(或混合整数规划)问题的一种方法。用该法寻求整数最优解的效率很高。将该法原理用于过程系统综合可大大减少需要计算的方案数日。 分支定界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。 在竞赛中，我们有时会碰到一些题目，它们既不能通过建立数学模型解决，又没有现成算法可以套用，或者非遍历所有状况才可以得出正确结果。这时，我们就必须采用搜索算法来解决问题。 搜索算法按搜索的方式分有两类，一类是深度优先搜索，一类是广度优先搜索。我们知道，深度搜索编程简单，程序简洁易懂，空间需求也比较低，但是这种方法的时间复杂度往往是指数级的，倘若不加优化，其时间效率简直无法忍受；而广度优先搜索虽然时间复杂度比前者低一些，但其庞大的空间需求量又往往让人望而却步。 所以，对程序进行优化，就成为搜索算法编程中最关键的一环。 本文所要讨论的便是搜索算法中优化程序的一种基本方法枣“剪枝”。 什么是剪枝 相信刚开始接触搜索算法的人，都做过类似迷宫这样的题目吧。我们在“走迷宫”的时候，一般回溯法思路是这样的： 1、这个方向有路可走，我没走过 2、往这个方向前进 3、是死胡同，往回走，回到上一个路口 4、重复第一步，直到找着出口 这样的思路很好理解，编程起来也比较容易。但是当迷宫的规模很大时，回溯法的缺点便暴露无遗：搜索耗时极巨，无法忍受。 我们可不可以在向某个方向前进时，先一步判断出这样走会不会走到死胡同里呢？这样一来，搜索的时间不就可以减少了吗？ 答案是：可以的。 剪枝的概念，其实就跟走迷宫避开死胡同差不多。若我们把搜索的过程看成是对一棵树的遍历，那么剪枝顾名思义，就是将树中的一些“死胡同”，不能到达我们需要的解的枝条“剪”掉，以减少搜索的时间。 搜索算法，绝大部分需要用到剪枝。然而，不是所有的枝条都可以剪掉，这就需要通过设计出合理的判断方法，以决定某一分支的取舍。在设计判断方法的时候，需要遵循一定的原则。 剪枝的原则 1、正确性 正如上文所述，枝条不是爱剪就能剪的。如果随便剪枝，把带有最优解的那一分支也剪掉了的话，剪枝也就失去了意义。所以，剪枝的前提是一定要保证不丢失正确的结果。 2、准确性 在保证了正确性的基础上，我们应该根据具体问题具体分析，采用合适的判断手段，使不包含最优解的枝条尽可能多的被剪去，以达到程序“最优化”的目的。可以说，剪枝的准确性，是衡量一个优化算法好坏的标准。 3、高效性 设计优化程序的根本目的，是要减少搜索的次数，使程序运行的时间减少。但为了使搜索次数尽可能的减少，我们又必须花工夫设计出一个准确性较高的优化算法，而当算法的准确性升高，其判断的次数必定增多，从而又导致耗时的增多，这便引出了矛盾。 因此，如何在优化与效率之间寻找一个平衡点，使得程序的时间复杂度尽可能降低，同样是非常重要的。倘若一个剪枝的判断效果非常好，但是它却需要耗费大量的时间来判断、比较，结果整个程序运行起来也跟没有优化过的没什么区别，这样就太得不偿失了。 综上所述，我们可以把剪枝优化的主要原则归结为六个字：正确、准确、高效。 剪枝算法按照其判断思路可大致分成两类：可行性剪枝及最优性剪枝。 对于分支定界算法,上界是已求得的可行解的目标函数值中的最小者,分为初始上界和在探测过程中产生的动态上界.分支定界法在求最优解的迭代过程中, 若某结点估计的下界不小于已知的上界, 则不必从该节点往下继续搜索. 因此若能产生一个较好的上界, 可以消除许多不必要的列举计算. 分支定界算法的实现 在描述分支定界算法步骤之前, 先对算法涉及到的有关术语进行定义如下: p —— 分支层数; C*—— 当前最优目标函数值; P*—— 相应于C*的工件顺序; P1—— 当前节点(现在需要进行分支的节点)所对应的部分序列. 分支定界算法的实施步骤如下: 步骤1 初始化: 设置p = 0, P 1 = Á (空集) , C* = ∞.设当前节点总是与P 1 相对应. 此时, 当前节点即根节点. 步骤2 计算从当前节点分支得到的各个子节点的下界, 并按下界值由小到大对各子节点排序. 令p ←p + 1. 步骤3 如果当前节点被探测尽, 令p ←p - 1, 转步骤6. 否则, 设当前层(第p 层) 各活动子节点中具有最小下界值的节点为Q , 则在P 1末尾加入Q 对应第p 位置上的工件, 此时的当前节点转为Q , 转步骤4. 步骤4 因为当前节点是同层同父节点具有最小下界值的节点, 如果当前节点下界值大于或等于C* , 则不必再搜索当前节点及其同层同父的活动节点, 这样, 当前节点的上一层节点(父节点)被探测尽, p ←p - 1, 去掉P 1 中的最后一个工件,转步骤6. 否则, 转步骤5. 步骤5 如果p = n, 则得到一个较优顺序.令P* = P 1, C* 是当前节点的下界值, p ←p - 1,去掉P 1 中最后一个工件, 转步骤6; 否则转步骤2. 步骤6 若p ≠ 0, 去掉P 1 中最后一个工件,转步骤3; 否则, 算法停止. C* 是最优的目标函数值, P* 是最优顺序.
非完全图的旅行商问题
证明：我们知道AX=b有解的条件是
rank[A b]=rank(A)
必要性：
对于任意的b，AX=b都有解
现假设A的行列式等于零.也就是A不满秩
设rank(A)<n
假设A的列向量的最大线性无关组为a1...ak
将A化为最简形式
那么一定至少存在1个n维向量a(n+1)=(0 0 ... 1)T T表示转置
与a1...ak都线性无关
当b=a(n+1)时
很明显
rank(A b)≠rank(A)
这与对于任意的b，AX=b都有解矛盾
所以rank(A)>=n
又因为rank(A)<=n
所以rank(A)=n 也就是A的行列式不等于零
必要性得证.....(1)
充分性：
A的行列式不等于零=》rank(A)=n
对于任意b
显然rank(A b)>=rank(A)=n
而A是n阶矩阵 rank(A b)<=n
所以rank(A b)=n=rank(A)
所以对于任意的b，AX=b都有解
充分性得证.....(2)
由(1)(2)可知 对于任意的b，AX=b都有解的充分必要条件是A的行列式不等于零 评论
欢乐英雄