算法分析讲课大纲动态规划之求矩阵连乘积问题(完整版)实用资料.doc

《算法分析讲课大纲动态规划之求矩阵连乘积问题(完整版)实用资料.doc》由会员分享，可在线阅读，更多相关《算法分析讲课大纲动态规划之求矩阵连乘积问题(完整版)实用资料.doc（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法分析讲课大纲动态规划之求矩阵连乘积问题（完整版）实用资料(可以直接使用，可编辑 完整版实用资料，欢迎下载） 第一小节 动态规划问题最短路径问题 一 在正式提出动态规划法前我们先看一个数学例子： 例1：在 x+x2+x3+xn =a是约束条件下，求的极大值.令 ( 0 ) 令 且可得a-x=x, 所以 x=a/2故 同理 令 所以 a-x=2x , x=a/3所以 f3(a)=用数学归纳法可以证明：fn(a) = , x1=x2=x3=xn=证明：1：n=1 2：设fn(a) = , x1=x2=x3=xn= 成立，则fn+1(a)=max(+fn(a-x)=max( )令 y= y=所以

2、nx=a-x ,(n+1)x=a x= fn+1(a)=+n=我们刚才的解题策略是：“摸着石头过河”，f2 利用f1的结果，f3又利用f2的结果。类似于游戏中的一个勇士打败了一些敌人后得到一件武器，然后去打败另一个强大一些的对手，得到一件更好的武器，接着打败更强大的敌人。最后取得胜利。 在实际生活中，有这么一类问题，它们的活动过程可分为若干个阶段，而且在任一阶段 后的行为仅依赖于第I阶段的过程状态，而与I阶段之前的过程如何达到这种过程如何达到这种状态的方式无关，这样的过程就构成了一个多阶段决策过程。在50年代，贝尔曼（Richard Bellman）等人根据这类问题的多阶段决策的特性，提出了解

3、决问题的“最优性原理”从而创建了最优化问题的一种最新的算法设计方法动态规划。分治法和动态规划法的比较动态规划算法与分治法类似，其根本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的.以从16个数据中找出最大者为例，说明 分治法的“静”和动态规划法的“动”的区别。下面我们以具体的例子来说明如何运用动态规划算法来求解问题，并分析可用动态规划算法解的问题的所应具备的一般特征。对教材68页上的里子给予简要说明（因为书上的文字叙述有些含混晦涩，对符号的说明不清晰） y1OAF 2

4、 K 3 P 1 S 2 U 下面精讲一个例子 2 1 2 2 3C 2 G 3 L 4 Q 5 T 3 4 1 2 3 D H M R 2 2 1 3 4 3 2 31. 介绍这个图的特点.从而说明从O到A的最短路径必由7段而不是更多或更少段组成。其行进路线必然是x和y单调递增的（非严格单调）。从O(0,0)到U（4，3）点的每一条路径对应于由4个x上的和3个y上的字符构成的字符串，这种字符串的数目为C=35.如果采用穷举法进行搜索，需要进行35*6=210次加法，34次比较。2. 下面我们采用动态规划法来解决这一问题。令O为起点到U的最短距离为Do，以A为起点到U的最短距离为DA - -

5、- ,用dij表示（i , j）边的长度。 显然Ds=dsu=2,Dt=dTU=3,DQ=min2+2,5+3=4DP=1+Ds=1+2=3DR=3+DT=3+3=6DL=minDlq+DQ,dLP+DP=min4+DQ,2+Dp=min4+4,2+3=5Dk=3+Dp=3+3=6DM= min2+DQ,4+DR=min2+4,4+6=6DN=4+DR=4+6=10DF=2+DK=2+6=8DG=min1+DK,3+DL=min1+6,3+5=7DH=min1+5,1+6=6DJ=min3+DM,3+DN=min3+6,3+10=9DC=min2+DF,2+DG=min2+8,2+7=9DD=

6、min4+DG,2+DH=min4+7,2+6=8DE=min1+DH,2+DJ=min1+6,2+9=7DA=min3+DC, 2+DD=min3+9,2+8=10DB=min2+DD,3+DE=min2+8,3+7=10Do=min1+DB,2+DA=min1+10,2+10=11共进行了29次加法，12次比较。由Do=1+DB=11回溯，可得到最短路径为OB-D-HLP-S-UO-B-E-H-L-P-S-U推广到x轴m段y轴n段的情形：用动态规划法需要做2mn+（m+n-2）次加法，mm次比较；而如果用穷举法，需要次加法， 次比较。若m=n, 动态规划法要做2n2 +2n-2次加法，n2

7、 次比较，因此复杂度为O(n2) ;而穷举法需要次加法， 次比较 ，O(n2n+1)。第二小节 动态规划问题货郎担问题 1. 动态规划方法的思想- 动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。2. 货郎担问题：- 某售货员要到若干个村庄售货，各村庄之间的路程是已知的，为了提高效率，售货员决定从所在商店出发，到每个村庄售一次货然后返回商店，问他应选择一条什么路线才能使所走的总路程最短？实质 - 从某点出发,遍历其余点,再回到原点,求总路径消耗最少的路线.例设共有4个要经过的点- -1，2，3，4-各个点之间的花费如下：

8、1-2 : 10; 1-3 : 15; 1-4 : 20; 2-1 : 5; 2- 3 : 9; 2- 4 : 10; 3-1 : 6; 3- 2 : 13; 3- 4 : 12; 4-1 : 8; 4- 2 : 8; 4- 3 : 9; （最短路径 ：1- 2-4-3-1） 1 2 3 42456758587853.问题的解决1.) 问题的描述:l T(V1; V) - 表示从V1出发,经过顶点集合V中的点各一次,再回到点 V1的最短路径. 2.) 动态规划函数: T(vi; V) = mindij + T(vj ; V-vj) (vj 属于 V)l T(vi; V):就是 从V中任何一点v

9、i出发, 经过V中的点各一次,再回到 点 vi的最短路径.l Dij:表示从点vi出发,到某点vj的耗费(有方向性).l 注:这是一个递归定义的函数,关键是每次的函数T(vi; V)它所处理的点 集逐渐减少.3.)实例:(如上图)求从v1出发的货郎担问题. 解: T(v1; V)= T(v1; v1, v2, v3, v4)= min d12 + T(v2; v3, v4),d13 + T(v3; v2, v4), d14 + T(v4; v2, v3) /实例意义:初始的货郎担问题是从点v1出发,涉及其余3点v2,v3,v4;那按照动态规划“分而治之”的思想(这里就是把问题规模缩小,而问题的

10、数量可多一些),我们可先计算分别从v2, v3, v4出发,涉及(v2, v3, v4)三点的三条货郎担路线的路耗,再各自加上相应的dij,这样,最后就得到3个总路耗,再做一个min运算,就可求出初始问题的解.T(v2; v3, v4)= min d23 + T(v3; v4), d24 + T(v4;v3)T(v3; v4)= d34 + T(v4, )T(v4; v3)= d43 + T(v3, )T(v4, )= d41T(v3, )= d31T(v3; v4)= d34+ d41=6+9=15T(v4; v3)= d43+ d31=8+8=16T(v2; v3, v4)= min d2

11、3 + d34+ d41, d24 + d43+ d31= min 7+6+9, 6+8+8=22同理:T(v3; v2, v4)= min d32 + d24+ d41, d34 + d42+ d21= min 5+6+9, 6+5+4=15T(v4; v2, v3)= min d42 + d23+ d31, d43 + d32+ d21= min 5+7+8, 8+5+4=17则最后: T(v1; v1, v2, v3, v4)= min d12 + T(v2; v3, v4),d13 + T(v3; v2, v4), d14 + T(v4; v2, v3) = min 2+22,5+15

12、,8+17 =20所选的路线是:1-3-4-2-1第三小节 动态规划问题投资问题一 问题描述：投资问题就是考虑如何把有限资源分配给若干个工程的问题。二 给定条件：1.资源总数（设为a） 2.工程个数（设为n） 3.每项工程投资的利润（不同数目的投资所获得的利润不同），用向量Gi (1in)表示。 n三 问题求解：求出一个a的分划x1, x2,., xn,0xia, 且 xi a,使得以下式表示的利润为最大： i=1 n G(a)= Gi (xj) 0xja i=1 其中Gi (xj)是把资源xj分配给第I项工程能获得的最大利润。四 问题分析： i）若Gi 是x的线性函数，则为线性规划问题。ii

13、）若Gi 不是线性函数，则要用动态规划求最佳分配。用总量为a的资金在n个项目上进行投资以取得最大的利润，可以转化为下述的问题：将总量资金a分为两部分z(0za)及a-z，分别用在第n个项目及剩下的n-1个项目上进行投资，获得的最大利润G(a)=max(第n个项目上资金量为z的利润与用a-z的资金在n-1个项目上投资的最大利润之和)。这样问题就转化为”求用a-z的资金在n-1个项目上投资的最大利润”，与我们的原问题” 求总量为a的资金在n个项目上进行投资以取得最大的利润”性质完全一致，仅仅是问题的规模比原问题少了一个项目，如此将问题的规模细化下去，一直到项目数为1为止，则问题迎刃而解。我们在对原

14、问题进行”分而治之”的过程当中，最终实现了最优化的求解。五 问题解决方案：设fi(x)：前i个项目共投资资金x所产生的最大利润；di(x)：产生fi(x)在项目i上的资金数。由上分析可给出投资问题的动态规划函数方程：f1(x)= G1(x);d1(x)=x x=0,1afi(x)=maxGi(z)+ fi-1(x-z) z=0,1x; x=0,1adi(x)=产生fi(x)的z值 i=2,3.n;六 问题举例：设有8（万元）的投资可分给3个项目，每个项目的利润函数如下表（一）所示： 表（一）利润函数表x0 1 2 3 4 5 6 7 8 G1(x)G2(x)G3(x)0 5 15 40 80

15、90 95 98 1000 5 15 40 60 70 73 74 750 4 26 40 45 50 51 52 53解题步骤：第1步：设项目1是可用于投资的唯一项目，把x万元投资到项目1，利润为 f1(x)= G1(x) 这就得到表（二）的最后一行的值，投资到项目1的最优数量为 d1(x)=x x=0,18；第二步：设资金8万元可投资到项目1和项目2。由第1步已知任意数量的资源投资到项目1所产生的最优，所以下到各种和式中的最大值就是目前情况下的最大利润： G2(0)+ f1(8)=0+100=100 G2(1)+ f1(7)=5+98=103 G2(2)+ f1(6)=15+95=110G

16、2(3)+ f1(5)=40+90=130 G2(4)+ f1(4)=80+60=140G2(5)+ f1(3)=70+40=110 G2(6)+ f1(2)=73+15=88G2(7)+ f1(1)=74+5=79 G2(8)+ f1(0)=75+0=75 可见将8万元投资于项目1和2 ，所能获得的最大利润f2(8)及投资到项目2的最优数量分别为：f2(8)=maxG2(z)+ f1(8-z)=140 z=0,18d2(8)=4；第三步：假设以任意x(8)万元投资到项目1和2，对每个x值，计算从项目1和2所产生的最优利润，即：f2(x)=maxG2(z)+ f1(x-z) z=0,1x;投资

17、到项目2的数量为d2(x)=产生f2(x)的z值。得到所表（二）的结果。第四步：将8万元投资于3个项目，这就是原问题。则f3(8)应取下述各量的最大值： G3(0)+ f2(8)=0+140=140 G3(1)+ f2(7)=4+120=124 G3(2)+ f2(6)=26+96=126G3(3)+ f2(5)=40+90=130 G3(4)+ f2(4)=45+80=125G3(5)+ f2(3)=50+40=90 G3(6)+ f2(2)=51+15=66G3(7)+ f2(1)=52+5=57 G3(8)+ f2(0)=53+0=53 因此将8万元以最优方式投资到3个项目时所获得的最大

18、利润及投资到项目3的分别为： f3(8) =G3(0)+ f2(8)=140 d3(8)=0； 表（二）向项目1，2投资所到的利润表x0 1 2 3 4 5 6 7 8 f1(x)d1(x)f2(x)d2(x)0 5 15 40 80 90 95 98 1000 1 2 3 4 5 6 7 8 0 5 15 40 80 90 95 120 1400 1 2 3 0 0 0 3 4 因为d3(8)=0；故剩下8万元要最优的投资到项目1和2中。由表（二）易知，当项目1和2 可用时，d2(8)=4表示 投资到项目2的最优数量，因此项目1应投资剩下的4万元。第四小节 动态规划问题矩阵连乘积问题一、求矩

19、阵的连乘积1、一个实际的例子（体现了乘积顺序对矩阵连乘的重要性）a) 例子 在讲这个问题之前先举个例子MA *B *C ，其中A=( aij)10*100 B=( bij)100*5 C=( cij)5*50根据矩阵乘法的结合律，则有M（A *B ）*C和MA *（B*C）两个方案但是可以发现他们所做的乘法的次数是不相同的以M（A *B ）*C为例令AB=M=(mij)10*5，因此mij（其中,I=1,210；j1，25）故计算AB共进行了10*5*100=5000次乘法M= MC（其中,I=1,210；j1，250）故计算MC共进行了10*5*50=2500次乘法总共需要 50002500

20、7500次乘法同理，MA *（B*C）方案需要 100*5*50+10*100*50=25000+50000=75000次乘法，两者相差近十倍！B）结论不难得出，矩阵相乘的结合方式对计算结果所需要的乘法操作总数有很大的影响。但是M相乘的个数增多至n个，求出所有的可能结合方式的乘法操作次数，再从中找出操作次数最小的结合方式，其工作量是惊人的! 对于n个矩阵的连乘积，设有P（n）个不同的计算次序。由于我们可以先在第k和k1个矩阵之间将原矩阵序列分为两个矩阵子序列，k1，2，n1。然后分别对这两个矩阵子序列完全加括号。最后对所得结果加括号，得到原矩阵序列得一种完全加括号方式。由此，可以得到关于P（n

21、）得递归式如下：P（n）=1 , n=1时P（n） ，n1时解此递归方程可得，P（n）C（n1）其中，C（n）P（n）=P(1)P(n-1)+P(2)P(n-2)+P（n1）P（1）P（2）1P（n）这样的话这种枚举的方法实际上是不可能的。这里用动态规划的方法可以提供一种O（n3）的算法。如果可以找出乘法次数最少的的结合方式来计算的话，那么就减少了不少工作量。2、动态规划法求解的方案（还是以一个实际的例子来讲动态规划法的算法）a） 算法分析举例最佳的乘积方案是（A1A2Ai）（AI1AI2An ）则A1A2Ai和AI1AI2An必须达到最佳。令mij为计算乘积AIAI1Aj的最少乘法数，显然有

22、mij mii0， I，j1，2n其中mik是求AIAI1Ak乘积时最佳方案的乘积数目，m会1；j是求Ak1Ak2Aj乘积时的最佳方案的乘积数，AIAI1Ak是ri*rk+1阶矩阵，Ak1Ak2Aj是rk+1*rj+1矩阵，rirk+1 rj+1是求（AIAI1Ak）（Ak1Ak2Aj）所需的乘数法利用上式将之变为多段判决即可以计算以下4个矩阵为例A130*35，A235*15，A315*5，A45*10 n4为例m1230*35*15=1575030*35*15=15750m2335*15*5=2625m3415*5*10=750m13min m12+30*15*5, m23+30*35*5

23、= min 15750+2250, 2625+5250=7875m24min m23+30*5*10, m34+35*15*10= min 2625+1750, 750+5250=4375m14min m12+ m34+30*15*10, m24+30*35*10, m13+30*5*10= min 15750+4500,4375+10500, 7875+30*5*10=9375故最佳方案为：（A1（A2 A3）A4）J=1 2 3 4I=1 2 34 0m12m13m140m23m240m340B） 算法时间空间复杂性分析计算顺序是沿着对角线进行的。如果编程的话，程序如下（！c程序只供参考，

24、不作为讲课内容）void MatrixChain (int p, int n, int n*m, int *s) for (int r=2; r=n; r+) for (int i=1; i=n-r+1; i=i+) int j=I+r-1; mij=mi+1j+Pi-1*pi*pj; sij=I; for (int k=i+1; kj; K+) int t=mik+mk+1j+pI-1*pk*pj; if (tmij mij=t; sIj=k; 计算量主要取决于程序中对r，I，k的三重循环。循环体内的计算量为O（1），而三重循环的总次数为O(n3),由此该算法的计算时间上界为O(n3)，算法

25、所占用的空间显然为 O(n2)，显然比穷举搜索法有效的多。二、动态规划的基本要素（综合讲过的几个例子,总结算法的基本要素）从以上的最优计算次序的动态规划算法可以看出，这些算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。从一般意义上讲，问题所具有的这两个重要的性质是该问题可用动态算法求解的基本要素。1最优子结构设计动态规划算法的第一步通常是要刻画最优解的结构。当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。问题的最优解子结构性质提供了该问题可用动态规划求解的重要线索。比如，在矩阵连乘积最优解计算次序问题中，我们注意到，若A1、A2An的最优完全

26、加括号方式在Ak和AK1之间将矩阵链断开，则由此确定的子链A1、A2Ak和AK1、AK2An得完全加括号方式也最优。即该问题具有最优解子结构性质。在分析该问题得最优解导出得其子问题得解不是最优的，然后再设法说明在这个假设下可构造出一个比原问题最优解更好的解，从而导致矛盾。在动态规划算法中，问题的最优子结构性质使我们能够自底向上的方法递归的从子问题地最优解逐步构造出整个问题地最优解。同时，它也使我们能在相对小的子问题空间中考虑问题。例如，在矩阵连乘积最优解次序问题中，子问题空间是输入地矩阵链的所有不同子链组成的。所有不同子链的个数为O（n2），因而子空间规模为O（n2）2重叠子问题可用动态规划算

27、法求解问题应具备地另一基本要素是子问题地重叠性质。在用递归算法自顶向下解此问题时。每次产生地子问题并不总是新问题，有些子问题被反复计算多次。多态规划算法正式利用了这种子问题地重叠性质，对每个问题只解一次，尔后将其解保存在一个表格中，当再次需解此问题时，只是简单地用常数时间查看一下结果。通常，不同地子问题个数随输入问题地大小呈多项式增长。因此，用动态规划算法通常只需多项式时间，从而得较高得解题效率。例如，搜索法和动态规划求解矩阵连乘法（这里略去具体）由此可以看出，在解某个问题得直接递归算法所产生得递归数中，相同的子问题反复出现，并且不同子问题的个数又相对减少时，用动态规划算法是有效的三、分治法和

28、动态规划法的比较动态规划算法与分治法类似，其根本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。(! 这里严求真已经提过了)若用分治法来求解这类问题，则分解得到的子问题数目太多，以至于最后解原问题需耗费指数时间。然而，不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重计算了很多次。如果我们保存已解决子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。为了达到这个目的，我们可以用一个表来记录所有已解决的子

29、问题的答案。不管该子问题以后是否被用到，只要被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但他们具有相同的填表格式。 !！另外提一下（因为第五周的课上，石浩讲分治法求矩阵乘积时说无法看出分治法体现在哪里,后来在一本书上看到如下的解释）分治法中的矩阵乘法即Strassen矩阵乘法中。其分之思想是，将幂为2的矩阵A，B，C中每一个矩阵都分成4个大小相等的子矩阵，每个矩阵都是(n/2)*(n/2)的方阵，由此可将方程CAB重写为分治法的基本思想是将一个矩阵为n的问题分解为k个规模较小的子问题，这些子问题的解合并得到原问题的解。参考资料：算法分析与设计 周培德

30、机械工业出版社 （教材）计算机算法设计与分析王晓东 电子工业出版社算法与复杂性 卢开澄 高等教育出版社计算机算法导引设计与分析 卢开澄 清华大学出版社计算机算法基础 余祥宣 崔国华 邹海明 华中科技大学出版社一种改进的蚁群算法求解TSP问题及实验结果分析何开成（四川大学 电子信息学院 四川 成都 610064）摘 要： 首先对蚁群算法的基本模型进行介绍，其次针对算法容易陷入局部最优解，在算法中加入扰动量，扩大搜索范围，从而有效控制算法陷入局部最优解。针对蚁群算法收敛速度慢，利用蚁群在最差路径上的信息，对蚁群算法信息素更新规则上进行改进。实验结果表明，提出的改进蚁群算法有效的避免程序过早的陷入局

31、部最优解，同时提高蚁群算法的速度。关键词： 蚁群算法；扰动量；算法改进；局部最优解中图分类号：TP301 文献标识码：A 文章编号：16717597（2021）0820071021 蚁群算法基本模型许多种类的蚂蚁在食物搜索过程中都存在释放信息素和信息素引导的现象。Deneubourg利用一个简单的试验模型说明了这种以自组织为基础的路径选择方式。在此模型中，蚁穴和食物之间被一座有两个等长支路的桥所分离。开始时，由于两条支路上都没有信息素分布，蚂蚁们将按照相同的概率进行路径选择。引入随机波动后，将有一条路径上通过的蚂蚁会更多一些，这将增加该路径上的信息素浓度，于是就会引导更多的蚂蚁选择这条路径。在

32、Deneubourg设计的试验中，遗留在路径上的信息素浓度与经过的蚂蚁数量成正比，而且不考虑信息素的挥发问题。在这种简化的模型中，蚂蚁选择路径的依据就是己经过该路径的蚂蚁总数。设减和尽双为第i个蚂蚁经过桥之后，分别选择了路径A和B的蚂蚁数。则第i+l只蚂蚁选择路径A和B是，由于构造型算法优化质量较差，迄今为止已开发了许多性能较好的改进型搜索算法，主要有：模拟退火算法，禁忌搜索算法，Hopfield神经网络优化算法，蚁群算法，遗传算法，混合优化策略。3 蚁群算法求解旅行商问题模型以求解平面上n个城市的旅行商问题为例说明蚁群系统的基本模型。旅行商问题就是给定n个城市的位置和两两城市之间的距离，要求

33、确定一条经过各城市当一次且只有一次的最短路线。其图论描述为：给定图（V，A），其中v为顶点集，A为各顶点相互连接组成的边集，已知各顶点间的连接距离，要求确定一条长度最短的回路，即遍历所有顶点一次且只有一次的最短回路。为了更好地说明问题，首先引入如下记号M：蚁群中蚂蚁数量；bi（t）：t时刻位于城市i的蚂蚁的个数，i和j之间的距离；nij：边（i，j）的能见度，城市i和j之1/ diji，j）上的信息素轨迹强度；k在边（i，jk的转移概率，j是尚未访问的城市。每只蚂蚁都是具有如下特征的简单实体；1）在从城市派到城市j的运动过程中或是在完成一次循环后，蚂蚁在边（i，j）上释放一种物质，成为信息素轨

34、迹；2）蚂蚁按概率选择下一个将要访问地城市，这个概率是城市间的距离和连接两城市的路径上存有的轨迹量的函数；3）为了满足问题的约束条件，在完成一次循环以前，不允许蚂蚁选择己经选择过的城市。=C（C为常数）。蚂蚁k（k=1，2，3，m）在运动过程中根据各条路径上的信息素量决定转移方向。蚁群系统使用随机比例转移规则进行状态的转移。转移规则给出了位于城市i的蚂蚁kk在城市i选择城市j的转移概率式中：allowed=0，1，k下一步允许选择的城市。经过n个时刻，当m只蚂蚁都经过一次搜索周期后，在路径上的信息素量的改变根据下面式子进行更新：上述公式对这种选择方式进行了量化。参数n决定了选择函数的非线性度，

35、n较大时，只要一条路径上的信息素浓度稍高于另外一条路径，则下一只蚂蚁选择前一路径的概率就会更大。参数k反映了未标记路径的吸引力，k越大，则进行非随机化选择所需的信息素浓度要求越高。这种概率表达方式是实际的蚂蚁路径选择试验推导而来的。比较适合试验需要的参数设置是n=2和k=20。2 旅行商问题旅行商问题（Traveling Salesman Problem，简称TSP）即给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。其图论描述为：给定图G=（V，A），其中V为顶点集，A为各顶点相互连接组成的边集，设D=（dij）是由顶点i和顶点j之间的距离所组成的距离矩阵，要求

36、确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短距离。旅行商问题可分为如下两类：1）对称旅行商问题（dij=diji，j=1，2，3，n）；2）非对称旅行商问题（dijdiji，j=1，2，3，n）。非对称旅行商问题较难求解，我们一般是探讨对称旅行商问题的求解。若对于城市V=v1，v2，v3，vn的一个访问顺序为T=t1，t2，t3，ti，tn，其中tiV（i=1，2，3，n），且记tn+1=t1，则旅行商问题的数学模型为：4 蚁群算法的缺点旅行商问题是一个典型的组合优化问题，并且是一个NP完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发

37、式的搜索、优化算法的间接比较标准。因此，快速、有效地解决旅行商问题有着重要的理论价值和极高的实际应用价值。基于旅行商的问题特性，构造型算法成为最先开发的求解算法，如最近邻点、最近合并、最近插入、最远插入、最近添加、贪婪插入等。但蚁群算法最主要的缺点是求解速度慢。很多学者对此进行了研究，提出了多种改进方法，但不论采用那种具体方法，都可归结为通过提高蚂蚁每次周游的质量来提高蚁群算法的求解速度。之所以都采用这种方法，就是由于基本蚁群算法求解速度慢的一个重要原因是蚂蚁每次周游得到的信息没有被充分地利用起来。这主要体现在各条路径上的信息量更新规则上。由上面对蚁群算法的介绍可知，蚂蚁在周游过程中，会使它经

38、过的路径上的信息量减少，同时，增强蚂蚁周游的信息没有充分地利用起来。实际上，每只蚂蚁周游的信息也是很有用的。蚁群算法求解速度慢的另一个重要原因是蚂蚁获取的信息与实际情况会有一些差异，这会对蚂蚁产生误导，而蚁群算法排除误导的速度较慢。蚁群算法求解过程是一个正反馈过程。蚂蚁的第一次周游时，由于各路径上的信息量相同，蚂蚁选择城市是随机的。这一次选择会使一些不是最优的路径上的信息量偏大。以后的蚂蚁就会根据这个不正确的信息选择以后的路径，这些不是最优的路径被蚂蚁选择的可能性将很大，这会导致这些较差的路径上的信息量不断增大。经过这样一个正反馈过程，路径上的信息量就具有了很大的误差而导致算法难以找到较优解。

39、蚁群算法在一定程度上可通过信息量的挥发过程以及蚂蚁周游的下一个城市的随机选择过程来排除具有较大误差的信息。但是，信息量挥发过程是缓慢的。而且在挥发过程中，很可能会有许多蚂蚁再次经过这条路径，并有可能使这条路径上的信息量增大。一次通过选择城市随机性来削减误差仅在算法刚运行不久，各条路径上的信息量相差不是很大的情况下才可能起到一定作用。由于这两种排除误差的方法均不能较快地排除误差，也导致了蚁群算法求解速度慢，并且增加了算法陷入局部最优的可能性。5 蚁群算法的改进1）加入扰动的改进针对蚁群算法容易陷入局部最优解，这里引入参数q0，蚂蚁k从i城市选择下一个城市j时，首先产生一个0，l均匀分布的随机数q

40、，当q小于常数q0时，蚂蚁根据先验知识即：能见度选择下一个城市。公式（1）改进为： 依状态转移规则选择下一结点； 重复步骤，直至每只蚂蚁均形成一条完整路径，即遍历所有结点； 更新最优解； 进行信息素更新； 判断是否满足算法终止条件：若满足，则算法终止；否则，转步骤。6 实验结果及分析本文利用MATLAB仿真平台对典型的旅行商问题Odyssey of Ulysses进行进行了仿真实验，已知Odyssey of Ulysses问题的最优解是75.6651。我们分别取NC=10，m=50，a=l=2，p=0.3，Q=1，W=4，q0=0.1。a=l；NC=50，m=50，a=l=2，p=0.3，Q=1，W=4，q0=0.1，。a=l；NC=100，m=50，a=l，p=0.3，Q=1，W=4，q0=0.1a=l，原始蚁群算法与改进蚁群算法分别周游10次，50次，100次所得到的最优解对比如下表：加入扰动参数q，每隔一定时间，蚂蚁在选择下一个城市时，只根据能见度选择，这样可以排除因为蚁群算法正反馈导致的较大误差解，扩大了解的搜索范围，有效避免了蚁群算法过早陷入局部最优解。2）信息素更新规则的改进蚁群算法最主要的缺点是求解速度慢。由于基本蚁群算法求解速度慢的一个重要原因是蚂蚁每次周游得到的信息没有被充分地利用起来。这主要体现在各条路径上的信息量更新规则上。由上面对蚁群算法的介绍可知，蚂