一种改进的蚁群算法求解TSP问题及实验结果分析

一种改进的蚁群算法求解TSP问题及实验结果分析（完整版）实用资料(可以直接使用，可编辑完整版实用资料，欢迎下载）

一种改进的蚁群算法求解TSP问题及实验结果分析一种改进的蚁群算法求解TSP问题及实验结果分析（完整版）实用资料(可以直接使用，可编辑完整版实用资料，欢迎下载）何开成（四川大学电子信息学院四川成都610064）摘要：首先对蚁群算法的基本模型进行介绍，其次针对算法容易陷入局部最优解，在算法中加入扰动量，扩大搜索范围，从而有效控制算法陷入局部最优解。针对蚁群算法收敛速度慢，利用蚁群在最差路径上的信息，对蚁群算法信息素更新规则上进行改进。实验结果表明，提出的改进蚁群算法有效的避免程序过早的陷入局部最优解，同时提高蚁群算法的速度。关键词：蚁群算法；扰动量；算法改进；局部最优解中图分类号：TP301文献标识码：A文章编号：1671－7597（2021）0820071－021蚁群算法基本模型许多种类的蚂蚁在食物搜索过程中都存在释放信息素和信息素引导的现象。Deneubourg利用一个简单的试验模型说明了这种以自组织为基础的路径选择方式。在此模型中，蚁穴和食物之间被一座有两个等长支路的桥所分离。开始时，由于两条支路上都没有信息素分布，蚂蚁们将按照相同的概率进行路径选择。引入随机波动后，将有一条路径上通过的蚂蚁会更多一些，这将增加该路径上的信息素浓度，于是就会引导更多的蚂蚁选择这条路径。在Deneubourg设计的试验中，遗留在路径上的信息素浓度与经过的蚂蚁数量成正比，而且不考虑信息素的挥发问题。在这种简化的模型中，蚂蚁选择路径的依据就是己经过该路径的蚂蚁总数。设减和尽双为第i个蚂蚁经过桥之后，分别选择了路径A和B的蚂蚁数。则第i+l只蚂蚁选择路径A和B是，由于构造型算法优化质量较差，迄今为止已开发了许多性能较好的改进型搜索算法，主要有：模拟退火算法，禁忌搜索算法，Hopfield神经网络优化算法，蚁群算法，遗传算法，混合优化策略。3蚁群算法求解旅行商问题模型以求解平面上n个城市的旅行商问题为例说明蚁群系统的基本模型。旅行商问题就是给定n个城市的位置和两两城市之间的距离，要求确定一条经过各城市当一次且只有一次的最短路线。其图论描述为：给定图（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）上释放一种物质，成为信息素轨迹；2）蚂蚁按概率选择下一个将要访问地城市，这个概率是城市间的距离和连接两城市的路径上存有的轨迹量的函数；3）为了满足问题的约束条件，在完成一次循环以前，不允许蚂蚁选择己经选择过的城市。=C（C为常数）。蚂蚁k（k=1，2，3，…，m）在运动过程中根据各条路径上的信息素量决定转移方向。蚁群系统使用随机比例转移规则进行状态的转移。转移规则给出了位于城市i的蚂蚁kk在城市i选择城市j的转移概率式中：allowed={0，1，k下一步允许选择的城市。经过n个时刻，当m只蚂蚁都经过一次搜索周期后，在路径上的信息素量的改变根据下面式子进行更新：上述公式对这种选择方式进行了量化。参数n决定了选择函数的非线性度，n较大时，只要一条路径上的信息素浓度稍高于另外一条路径，则下一只蚂蚁选择前一路径的概率就会更大。参数k反映了未标记路径的吸引力，k越大，则进行非随机化选择所需的信息素浓度要求越高。这种概率表达方式是实际的蚂蚁路径选择试验推导而来的。比较适合试验需要的参数设置是n=2和k=20。2旅行商问题旅行商问题（TravelingSalesmanProblem，简称TSP）即给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。其图论描述为：给定图G=（V，A），其中V为顶点集，A为各顶点相互连接组成的边集，设D=（dij）是由顶点i和顶点j之间的距离所组成的距离矩阵，要求确定一条长度最短的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完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、优化算法的间接比较标准。因此，快速、有效地解决旅行商问题有着重要的理论价值和极高的实际应用价值。基于旅行商的问题特性，构造型算法成为最先开发的求解算法，如最近邻点、最近合并、最近插入、最远插入、最近添加、贪婪插入等。但蚁群算法最主要的缺点是求解速度慢。很多学者对此进行了研究，提出了多种改进方法，但不论采用那种具体方法，都可归结为通过提高蚂蚁每次周游的质量来提高蚁群算法的求解速度。之所以都采用这种方法，就是由于基本蚁群算法求解速度慢的一个重要原因是蚂蚁每次周游得到的信息没有被充分地利用起来。这主要体现在各条路径上的信息量更新规则上。由上面对蚁群算法的介绍可知，蚂蚁在周游过程中，会使它经过的路径上的信息量减少，同时，增强蚂蚁周游的信息没有充分地利用起来。实际上，每只蚂蚁周游的信息也是很有用的。蚁群算法求解速度慢的另一个重要原因是蚂蚁获取的信息与实际情况会有一些差异，这会对蚂蚁产生误导，而蚁群算法排除误导的速度较慢。蚁群算法求解过程是一个正反馈过程。蚂蚁的第一次周游时，由于各路径上的信息量相同，蚂蚁选择城市是随机的。这一次选择会使一些不是最优的路径上的信息量偏大。以后的蚂蚁就会根据这个不正确的信息选择以后的路径，这些不是最优的路径被蚂蚁选择的可能性将很大，这会导致这些较差的路径上的信息量不断增大。经过这样一个正反馈过程，路径上的信息量就具有了很大的误差而导致算法难以找到较优解。蚁群算法在一定程度上可通过信息量的挥发过程以及蚂蚁周游的下一个城市的随机选择过程来排除具有较大误差的信息。但是，信息量挥发过程是缓慢的。而且在挥发过程中，很可能会有许多蚂蚁再次经过这条路径，并有可能使这条路径上的信息量增大。一次通过选择城市随机性来削减误差仅在算法刚运行不久，各条路径上的信息量相差不是很大的情况下才可能起到一定作用。由于这两种排除误差的方法均不能较快地排除误差，也导致了蚁群算法求解速度慢，并且增加了算法陷入局部最优的可能性。5蚁群算法的改进1）加入扰动的改进针对蚁群算法容易陷入局部最优解，这里引入参数q0，蚂蚁k从i城市选择下一个城市j时，首先产生一个[0，l]均匀分布的随机数q，当q小于常数q0时，蚂蚁根据先验知识即：能见度选择下一个城市。公式（1）改进为：③依状态转移规则选择下一结点；④重复步骤③，直至每只蚂蚁均形成一条完整路径，即遍历所有结点；⑤更新最优解；⑥进行信息素更新；⑦判断是否满足算法终止条件：若满足，则算法终止；否则，转步骤②。6实验结果及分析本文利用MATLAB仿真平台对典型的旅行商问题OdysseyofUlysses进行进行了仿真实验，已知OdysseyofUlysses问题的最优解是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）信息素更新规则的改进蚁群算法最主要的缺点是求解速度慢。由于基本蚁群算法求解速度慢的一个重要原因是蚂蚁每次周游得到的信息没有被充分地利用起来。这主要体现在各条路径上的信息量更新规则上。由上面对蚁群算法的介绍可知，蚂蚁在周游过程中，会使它经过的路径上的信息量减少，同时，增强蚂蚁在最短路径上的信息。这一过程利用了蚂蚁周游最短路径的信息。但其它蚂蚁周游的信息没有充分地利用起来。实际上，每只蚂蚁周游的信息也是很有用的。本文充分利用蚂蚁在最差路径上的信息对蚁群算法的信息素更新规则做了改进，在规则中引入了最差路径信息量减少参数w，改进后公式（2）调整为：从实验结果对比来看，改进后的蚁群算法在100次周游下已经找到问题的最优解，而原始的蚁群算法虽然在加大周游次数可以逐步接近最优解，但是他的收敛性不好，容易陷入局部最优解，所以，加大周游次数对求解旅行商最优解的意义不大。而改进的蚁群算法正是对原始蚁群算法的收敛速度慢，容易陷入最优解这两个方面进行了改进，改进后的蚁群算法能够扩大最优解的搜索范围，有效地避免算法过早陷入局部最优的情况的出现。实验结果证明：改进后的蚁群算法无论是最优解的方面还是在收敛速度方面都比原始蚁群算法要好。7结论蚁群算法最大的缺点就是收敛速度慢，容易陷入最优解，这也是限制它应用的最大瓶颈。本文针对蚁群算法收敛速度慢、容易过早陷入局部最优的缺点提出了一种新的改进算法。实验证明了这种改进的有效性和正确性。表示挥发系数，Q为信息量增加常数，w为信息量减少常数。3）算法实现MATLAB是一个可视化的计算程序，被广泛地使用于从个人计算机到超级计算机范围内的各种计算机上。它包括命令控制、可编程，有上百个预先定义好的命令和函数。这些函数能通过用户自定义函数进一步扩展。MATLAB有许多强有力的命令。正因为MATLAB具有这么多的优点，特别是在数值计算方面的独到性，本文利用MATLAB平台进行仿真实验。其程序步骤如下：①初始化信息素分布；②将每只蚂蚁随机置于任一个结点上；参考文献：[1]吴斌、傅伟鹏、郑毅、刘少辉，史忠植一种基于群体智能的Web文档聚类算法计算，机研究与发展，2021，39（11）：1429～1435.[2]吴启迪、汪镭，智能蚁群算法及应用[M].上海：上海科技教育出版社，2021.4.[3]黎锁平、张秀媛、杨海波，人工蚁群算法理论及其在经典TSP问题中的实现[J].交通运输系统工程与信息，2007，2（2）：73～76.一种基于新的相模变换矩阵的输电线路故障测距改进算法郭亮1,吕飞鹏1,罗长亮1,蒋科1,李鹏飞2(1.四川大学电气信息学院,四川成都610065;2.山东电力工程咨询院,山东济南250013摘要:针对已有电力系统行波故障测距算法中采用的相模变换、小波变换存在的不足,提出了一种结合新的相模变换矩阵和提升小波的行波故障测距改进算法,实现了单一模量反映所有故障类型,简化了高频小波系数的计算,提高了计算速度。通过Matlab仿真实验,验证了与普通小波测距相比,算法具有较高的测距精度。关键词:相模变换;提升小波;故障测距;输电线路;暂态行波Abstract:Consideringthedeficienciesoftheusedphase-modetransformationandwavelettransformintheavailabletransmis2sionlinefaultlocationalgorithms,animprovedalgorithmforthefaultlocationbasedonanewphase-modetransformationma2trixandliftingwaveletisproposed.Alltypesoffaultcanbereflectedbyasinglemodulus,thecalculationforthewaveletcoef2ficientswithhighfrequencyissimplified,andthecalculationspeedisenhanced.Matlabsimulationshowsthatthealgorithmhasahigheraccuracycomparedwiththetraditionalwaveletlocationmethods.Keywords:phase-modetransformation;liftingwavelet;faultlocation;transmissionline;transienttravelingwave中图分类号:TM755文献标志码:A文章编号:1003-6954(202106-0038-040引言故障测距是电力系统查找输电线路故障点的重要依据。在输电线路故障后及时、准确地找到故障点,对修复线路,保证可靠供电以及电力系统的安全稳定、经济运行具有非常重要的作用。行波故障测距法因其原理简单,近年来受到了国内外学者的关注,得到了广泛的研究[1~11]。现有的行波故障测距法多采用相模变换与小波变换相结合对暂态行波信号进行分析。目前常用的Clark、Karrenbauer、Wedpohl等变换矩阵在分析时域问题时应用最多,但其在继电保护应用中的最大缺陷是单模量不能适用于所有类型故障。若要使模量能反映所有类型故障,必须使用双模量或选相配合,从而使计算量大大增加[12]。传统的基于卷积的离散小波变换计算量大,计算复杂度高,对存储空间的要求高,不利于硬件实现[14]。针对已有行波故障测距算法存在的不足,提出了一种结合新的相模变换矩阵和提升小波的行波故障测距法。该算法通过对电流行波进行相模变换,再利用提升小波分析线路两端电流行波线模量来实现高精度故障测距。与已有的行波测距法相比,该方法不仅解决了单一模量不能反映所有故障类型的问题,还具备运算所需储存空间小,计算量小和计算效率高等优点。最后将其仿真结果与普通小波测距结果进行了对比。1新的相模变换矩阵的分析相模变换的数学本质就是将参数矩阵化为对角阵。对于三相均匀换位线路,根据其相模变换矩阵的构造原则,即第一列各元素相等,第二、三列元素之和均为零,文献[13]构造出一种新的相模变换矩阵,其原始阵为S=1155555-1-45-4-1(1S-1=11112-31-32(2对故障暂态相电流进行相模变换,可以提取线模分量,即1模量和2模量。表1给出了各种类型故障下使用该相模变换矩阵所得到的1模量和2模量的值。通过表1可知,运用该相模变换矩阵得到的模量・83・表1各种故障类型下的电流量模值故障类型边界条件1模量2模量BGib=ic=0iaiaBGia=ic=02ib-3ibCGia=ib=0-3ic2icABic=0,ia=-ibib-4ibBCia=0,ib=-ic5ib-5ibCAib=0,ia=-ic4ia-iaABGic=0ia+2ibia-3ibBCGia=02ib-3ic2ic-3ibCAGib=0ia-3icia+2IcABCia+ib+ic=0ia+2ib-3icia-3ib+2ic值在所有类型故障下均为非零值,即1模量和2模量均能单独反映所有类型故障[13],因此可以任意选取其中之一作为仿真分析对象。2提升小波变换提升小波于1996年由Sweldens提出,其算法的基本思想是,将现有的小波滤波器分解成基本的构造模块,分步骤完成小波变换[14]。传统的小波都可以找到等效的提升方案。如图1,由提升算法构成的小波变换过程可以分为以下3个阶段。图1提升算法的分解和重构(1分解。将输入信号Si分为两个子集Si-1和di-1,最简单的方法是按奇偶性分,分解过程F(Si=(Si-1,di-1;(2预测。在基于原始数据相关性的基础上,用偶数序列Si-1的预测值去预测奇数序列di-1,即将滤波器P对偶数信号作用后作为奇数信号的预测值,奇数信号的实际值与预测值相减得到残差信号,重复分解和预测过程,经n步后原信号集可用{Sn,dn,…,S1,d1}来表示;(3更新。更新的基本思想是找出一个更好的子数据集Si-1,使之保持原始数据集的一些特性。构造一个更新算子U,Si-1=Si-1+U(di-1。综上所述,提升算法可以实现原位运算,在每个点都可以用新的数据流替换旧的数据流。当重复使用原位提升滤波器组时,即可得交织的小波变换系数。电力暂态信号分析处理中的小波基的选择目前主要倾向于经验性选择。因为对故障暂态信号进行研究需要提取的是非平稳信号的瞬时、突变成分,即提取有限频带上的信息,所以在小波基的选取上,需要考虑其在时、频两域的紧支撑性和带通滤波性能,又为了能准确检测出信号中的奇异点,该小波函数必须具有正则性[7、15]。综合考虑,这里选择db4小波作为提升小波的小波基。图2仿真模型3算例仿真为了验证所提出的算法,用Matlab/Simulink建立一个500kV双电源系统模型,如图2。设定仿真时间为0.05s,采样频率为1MHz,分布参数线路PM、MN、NQ的长度皆为300km,故障起始时间为0.025s,接地电阻为10Ω,线路参数为R1=0.01273Ω/kmR0=0.3864Ω/kmL1=0.9337×10-3H/kmL0=4.1264×10-3H/kmC1=12.74×10-3μH/kmC0=7.751×10-3μH/km以线路MN为研究对象,其区内故障点为f。先以A相单相接地故障为例,设定故障点f距母线M端45km,运行仿真可得M端和N端的1模量暂态电流波形及其高频小波系数如图3所示。再以CA两相相间短路为例,设定故障点f距母线M端135km,运行仿真可得M端和N端的1模量暂态电流波形及其高频小波系数如图4所示。测距算法采用不受波速影响的双端行波测距[5]。故障距离采用以下公式进行计算。X=(t2-t1×l2(t3-2t1+t2(3其中l为线路全长,t1为故障初始行波从故障点・93・到达测量端母线的时刻,t2为故障点反射波到达测量端母线的时刻,t3为故障初始行波从故障点到达对端母线的时刻。分别对M、N两端的提升小波系数进行测量得到3个波头的时间,再代入式(3计算可得测距结果。以上两个例子的仿真结果如表2所示,可见该算法能够比较准确地确定故障地点。为了进一步验证该算法,表3给出了各种类型故障下分别采用提升小波和普通小波所得的部分测距结果。通过比较可以看出,采用提升算法后大多数故障测距结果精度比普通小波测距高,能够满足精确故障定位的要求。表2算例的仿真结果故障t1/mst2/mst3/msX/kmε/kmAG45km25.15725.46725.88344.8840.116CA135km25.46926.39925.571135.1740.174注:ε为绝对误差,其他符号意义同式(3。图31模量波形及其提升小波变换(45km,A相图41模量波形及其提升小波变换(135km,CA相间表3各种故障类型下的仿真故障类型故障仿真距离/km提升小波测距/km绝对误差/m普通小波测距/km绝对误差/m单相接地短路4040.0686839.99919090.0585890.231231180180.0000179.97129220220.0000219.93268280280.271271280.271271两相相间短路4040.0686839.99919090.0585890.231231180180.0000179.97129220220.0000219.93268280280.271271280.271271两相接地短路4040.0686839.99919090.0585890.231231180180.0000179.97129220220.0000219.93268280280.271271280.271271三相接地短路40280.271271280.271271・04・4结论针对传统相模变换矩阵的不足,提出了一种采用新的相模变换矩阵,并结合提升小波的故障测距改进算法。通过分析与仿真得出以下结论:所提出的算法,不仅能反映所有类型的故障,减小计算的工作量,而且相较于普通小波测距,多数情况下测距结果精度较高。参考文献[1]陈平,葛耀中,索南加乐,等.基于故障开断暂态行波信息的输电线路故障测距研究[J].中国电机工程学报,2000,20(8:56-59,64.[2]覃剑,陈祥训,郑健超,等.利用小波变换的双端行波测距新方法[J].中国电机工程学报,2000,20(8:6-10.[3]李友军,王俊生,郑玉平,等.几种行波测距算法的比较[J].电力系统自动化,2001,(14:36-39.[4]蒋涛,陆于平.不受波速影响的输电线路单端行波故障测距研究[J].电力系统自动化,2004,24(12:29-32.[5]李泽文,曾翔君,徐小箐,等.输电线路双端行波故障定位新算法[J].电力系统自动化,2006,30(15:40-43.[6]董杏丽,葛耀中,董新洲,等.基于小波变换的行波测距式距离保护原理的研究[J].电网技术,2001,25(7:9-13.[7]熊小伏,林金洪.基于小波重构的电力电缆故障测距方法[J].电网技术,2003,27(6:36-38.[8]范春菊,张兆宁,郁惟镛.小波方法在超高压输电线路故障测距中的应用[J].电网技术,2003,27(8:50-53.[9]黄雄,王志华,尹项根等.高压输电线路行波测距的行波波速确定方法[J].电网技术,2004,28(19:34-37.[10]覃剑,葛维春,邱金辉,等.影响输电线路行波故障测距精度的主要因素分析[J].电网技术,2007,31(2:28-35.[11]徐丙垠.利用暂态行波的输电线路故障测距技术[D].西安:西安交通大学,1991.[12]王安定,葛耀中.模量变换技术在反应故障分量的微机保护中的应用研究[J].电力系统自动化,1988,12(3:17-27.[13]宋国兵,李森,康小宁,等.一种新相模变换矩阵[J].电力系统自动化,2007,31(14:57-60.[14]葛哲学,沙威.小波分析理论与MATLAB7实现[M].北京:电子工业出版社,2005.3.[15]MognagoFH,AburA.Faultlocationusingwavelets[J].IEEETrans.OnPWRD,1998,13(4:1475-1480.作者简介:郭亮(1982-,男,硕士研究生,从事电力系统继电保护研究。吕飞鹏(1968-,男,博士,教授,从事电力系统继电保护和故障信息处理智能系统研究。罗长亮(1983-,男,硕士研究生,从事电力系统继电保护研究。蒋科(1983-,男,硕士研究生,从事电力系统继电保护研究。李鹏飞(1981-,男,硕士,从事电力系统继电保护研究。(收稿日期:2021-09-01(上接第25页一级母线接地判断方式为:二级支路均无不平衡电流但一级母线传感器有不平衡电流;由于母线和负荷支路同时接地的情况非常少,所以可以只定义为上述方式,并且多个继电器室发生多负荷支路接地时,绝缘监测装置仍可上传信号。4结束语通过对变电站直流系统接地告警方式的设计,可以使运行人员直观地监视到直流系统故障状况,锁定故障点,及时排除故障,当然由于直流馈线并未最终的负荷端,运行人员可以绘制更为详细的二级接线图,以方便下级支路的查找。参考文献[1]贾秀芳.直流系统绝缘监测综合判据[J].电力系统自动化,1999,23(16:47-49.作者简介:李俊儒(1982-,女,助理工程师,德阳电业局。刘玲(1982-,女,助理工程师,德阳电业局。赖民昊(1981-,男,助理工程师,成都电业局。(收稿日期:2021-07-08・14・第36卷第9期2006年9月数学的实践与认识Vol.36No.9Sep.,2006用矩阵和积求最短路的一种新算法詹棠森,张三强,唐敏(景德镇陶瓷学院信息工程学院,江西景德333001)摘要:先定义了矩阵和积的概念和运算,在求最短路中,这种方法和线性代数中的矩阵运算相似,通过这种方法,把求最短路转化为矩阵的运算,计算简便,有效.关键词:最短路;矩阵和积;多阶段决策;不完全关联;距离阵1引言求最短路的方法很多,有动态规划的多阶段决策方法[1],在动态规划算法中,利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解,而Disjkstra算法是解单源最短路径问题的贪心算法,其基本思想是设置顶点集合S并不断地做贪心选择来扩充这个集合[2,3].等.2定义矩阵和积及运算1)符号意义表示和运算⊕表示或运算[4,5]2⊕3表示2和32)运算形式和运算律交换律ab=ba分配律a(b⊕c=)(ab)⊕(ac)例23=32=5,2(3⊕4)=(23)⊕(24)=5⊕6.记∞(a⊕b⊕…⊕c=(∞).3)两矩阵和积的算法设矩阵Am×s=(aij)m×s,Bs×n=(bij)s×nAm×sBs×n=Cm×n=(cij)m×n其中cij=s∑k=1⊕aikbkj=ai1b1j⊕…⊕aisbsj.3构造多阶段决策最短路算法1.完全关联的多阶段问题及距离阵多阶段的决策问题的特点是先将一个复杂问题分解成相互联系的若干阶段,每一个阶段的点(事件点)与后一阶段的点完全相互联系,这种问题称为完全关联的多阶段问题.[6]9期詹棠森,等:用矩阵和积求最短路的一种新算法171如右图1B1C2=7,B1C3=4B2C1=3,B2C3=2B3C1=5,B3C2=1对于四个阶段的决策问题,若第一阶段只有一个点,第二,三,四阶段分别有n,m,1个点.构造矩阵,矩阵的元素由这些距离组成第1,2,3阶段的矩阵为k=A2以kk为列向量构成权矩阵(2)(2)(2)W(2)=(k1,k2,…,kn)(1)(1)1,k1,…k1)=(k(1)(2)(n)T(2)(2)(2)(2)Tkk=(kk1,kk2,…,kkm),k=1,2,…n[7].图1W(1)W(s-1)W(s-2)W(2)k.(3)=(k1,k2,…,km)(3)(3)(3)(3)(1)(s-1)最后得A到T的距离行阵(或称为权阵)k=W(3)W(2)k更一般S阶段的距离为k=2.求A到T的最短路按上图1,利用上面计算权重的方法,可得6k=(6,3,2)7(3)32=(12⊕10⊕6,9⊕5⊕4,11⊕4⊕6)42=14⊕12⊕8⊕12⊕8⊕7⊕15⊕8⊕10从这些数字中,我们很快找到A到T最短路是7,并按逆推过程可得取得最短路径是A→B2→C3→T,从中可看出距离为8的有3条,距离为10,14,15的各一条,距离为12的有二条.A到T最长距离为15,且路径是A→B