一种基于动态多维矩阵编码的组卷遗传算法(完整版)实用资料.doc

《一种基于动态多维矩阵编码的组卷遗传算法(完整版)实用资料.doc》由会员分享，可在线阅读，更多相关《一种基于动态多维矩阵编码的组卷遗传算法(完整版)实用资料.doc（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一种基于动态多维矩阵编码的组卷遗传算法（完整版）实用资料(可以直接使用，可编辑 完整版实用资料，欢迎下载） 一种基于动态多维矩阵编码的组卷遗传算法王力1 陈郁明2(1.贵州大学 电子科学与信息技术学院,贵州 贵阳550003(2.贵州大学 计算机科学与技术学院,贵州 贵阳 550003摘要:提出动态多维矩阵表示解(染体色的遗传算法,并针对这种染色体在交叉、变异和选择等遗传算子的实现进行了研究。运行结果表明,算法运行效率较好,有很好的实用价值。 关键词:多维矩阵染色体;遗传算法;自动组卷中图法分类号:TP399 文献标识码: BA Genetic Algorithm based-on dynam

2、ic multiple dimension matrix codingWang Li 1, CHEN Yuming 2(1.School of Electronic Science and Information Technology Guizhou University Guiyang 5500032. School of Computer Science and Technology, Guizhou, Guiyang 550003Abstract : The genetic algorithm was proposed by using multiple dynamic dimensio

3、n matrixes to represent solution (chromosome. And realization of genetic operators such as crossover 、mutation and selection, and so on was explored. The operation result reveals that the algorithm has a better efficiency and therefore it is of better practical value.Keywords : dynamic multiple dime

4、nsion chromosome; genetic algorithm; automatic generating test paper1引言遗传算法(Genetic Algorithm,简称GA 是一种演化算法,从提出至今不过50年时间。与爬山算法、模拟退火算法和禁忌算法等一样都属启发式搜索算法1。目前遗传算法在函数优化、组合优化、生产调度、机器人学、图像处理45和自动编程等诸多领域已经得到成功应用。在教育领域中,有大量的研究者把遗传算法用于自动排课、自动组卷23、学生成绩数据挖掘分析等,并且取得成功。很多自动组卷遗传算法都基于线性二进制串2或整数编码3实现染色体,本文先介绍了三维矩阵试卷模

5、型,然后提出了一种新的编码方式动态多维矩阵表示GA 的解(染色体,以及交叉算子、变异算子和选择算子的实现。2 试卷模型构成试卷是长度为n 的一维向量(123,.,n t t t t ,其中t i 是试卷的第i 道题在试题库中的编号,并且每道题目具有题型、知识点、分数、难度系数等多个属性。向量中,按题型可把题目分为m 类,按照知识点也可把题目分成k 类。因此,可以把试卷看成一个三维向量A mnk ,m 表示题型数量,n 表示知识点数量,k 为某题型中每个知识点试题数,题库中不同的题型和知识点k 值不同。矩阵中的元素a ijr 表示题型i 及知识点j 的第r 道题的题目编号。设Q1.n,1.m,1

6、.k中元素q ijr 保存题目a ijr 的分数,设x1.n,1.m,1.k为一标志数组,试卷满足如下公式:=未被选中题目被选中,题目ijr ijr a ,0a 1,r j i X =m i n j kr r j i Q r j i x Z 111,n 为题型数,m 为知识点数,k 为某题型和知识点对应的题目数。3组卷遗传算法3.1动态多维矩阵染色体数据结构编码是运用GA 时要解决的首要问题,也是设计GA 的一个关键步骤。针对具体应用问题,如何设计一种完美的编码方案一直是遗传算法的应用难点之一,也是遗传算法的一个重要研究方向。考虑使用三维矩阵(设为C mnk 作为染色体。其中,题型数为m ,知

7、识点数为,某题型和知识点题目数为k 。设预组试卷只有选择题、填空题和解答题3类题型,涉及4个知识点,图2.1为该染色体对应的“动态三维矩阵”。00 第二面:填空题00001001101 第三面:解答题 010* 图3.1 染色体构成示例以第一面选择题为例,第一行表示题库中知“识点1”满足条件的题目只有2道,并且没有一道被选中,第二行表示“知识点2”满足条件的题目数有4道,但只有第1道被选到试卷中。由于每道题型、每个知识点的题目数不一样多,有时可能没有题目,因此在设计时用动态三维数组实现染色体。Chro: Array of Array of Array of byte;本文所提的“动态三维矩阵”

8、并不是传统意义的三维矩阵,实际上是类似于三维矩阵的特殊的数据结构。3.2 染色体适应度函数适应度用于表示解的质量,GA 通过计算种群的每个个体适应度,然后根据适应度值的大小确定个体与解的逼近程度。为了得到个体适应度,必须构造相应适应度函数,但是适应度函数并不是显而易见的或由问题自动给出的,而是与问题的目标相关的,一个解如果完全满足目标,它就应该有最好的适应值。自动组卷的目标就是要使总分、题目数、难度系数等每项组卷指标的误差i 最小,可以对每项指标设定一个权值W i ,表示对试卷的影响程度的估计。个体i 适应度函数可表示为:=n i ii W i f 1*( ,n 为组卷指标数f(i的值越小表明

9、个体i 适应环境越强。因此,自动组卷问题变成了对函数f(i求极小值的问题。为了方便,把求极小值问题变成求极大值问题,函数变为:=ni i i W C i f 1*(,C 为一常数,保证f(i为大于零的正数3.3 选择算子设计采用轮盘赌选择算法,即某个染色是否被选中根据指针在轮盘上拔动位置来选择。设每个个体的适应度值对应轮盘的每一格,可以知道轮盘上格子距离最大的一格,即表示适应度值大的个体,其被选中的概率也大。个体在轮盘中格子大小(概率按下式计算:=N j i j f i f P 1(, N 为种群大小,且 11=N i iPP i 表示个体i 被选中概率,被选中的概率越大,则在轮盘赌中,赌赢的

10、概率越大。为了模拟轮盘,还要计算每个个体的累积概率,公式如下: =i i ip i FF 1由计算机产生一个0,1之间的随机数r ,该数对应轮盘指针停放的位置,如果(1r FF k k N =时,表示选中个体k 进入下一代。为了确保最优个体能进入下一代,在进化过程中,始终保存最优个体,如果最优个体的适应度值小于本代最优个体,则把最优个体代替本代最差个体,否则把本代最优个体当作最优个体进入下一代。3.4交叉算子设计对于N 个体的种群,以概率P c (0.95随机地选择两个个体进行交叉,方法是对三维“矩阵”的面(题型维或面中的行(知识点维进行整体交叉,随机生成两个随机数(,1,1u v u m v

11、 n =,分别表示对两个个体的第u 面到最后一面进行交叉,根据需要,也可根据指定的条件再对该面的第v 行进行交叉。交叉结果保证了每种题型的题目数不发生变化,知识点的题目数也不发生变化。3.5变异算子设计变异算子可以增加种群的多样性,对于防止种群的早熟有着极其重要的作用。在变异概率P m (=0.2作用下,利用随机函数产生三个整数(,1,1u v u m v n =和(1w w k =,表示在第u 面第v 位实施变异操作,即把0变1或把1变成0,由于操作将导致题目数增1或少1的情况发生,同时把第u 面第w 位取反,要注意的是第v ,第w 位异或结果必须为1。当以满足分数优先为前提进行自动组卷操作

12、时,只需要简单地把变异位取反即可。3.6停机条件停机条件是种群循环迭代最后结束的条件,在自动组卷过程中,当最优个体的适应度值与本代种群的平均适应度值之差的绝对值趋近于某个任给的大于0的常数时,或者当达到指定的迭代的次数时,强制让程序结束。4算法实现先从试题库取出满足条件(指定题型、指定知识点的题目编号,并放在一个动态三维数组ST 中。然后根据预先设定的试卷分数或题目数随机地生成N 个个体的种群P(0代。当未达到停机条件时,通过迭代对种群进行演化,最多进行T 次迭代后算法结束。算法结束后,取最优的染色体,并在动态三维数组中映射出试卷的题号,形成试卷向量(123,.,n t t t t 。具体算法

13、伪代码如算法4.1 :算法4.1:初始化P(0;t:=0;while(t=Tdobegin计算P(t的适应度;选择得到新的种群P(t+1;交叉、变异操作;处理最优个体;inc(t;end;对最优个体进行解码;本算法的一个难点是对初始化种群中的个体,不能采用随意产生初始个体,原因是这样产生的个体与待组试卷差异过大,算法的收敛速度变慢。为此,在初始化个体时,使之基本满足预先设定的题目数、分数及各题型、各知识点的总分数,使种群的每个个体在进化之前就已基本满足预先指定的条件,加速了算法收敛速度。5实验结果分析及结论利用本算法在具有不同题型和知识点对应的题目数的800道试题的“数据结构”的试题库系统中进

14、行组卷。变异概率P m=0.02,交叉概率P c=0.8,各项影响指标的权值向量为W=(0.2,0.1,0.1,0.2,0.1,0.1,0.1,0.1T,组卷参数由教师给定,以满足分数优先为条件的一份试卷在不同的种群下进行了试验,得到表4.1行结果:表5.1不同种群下算法的执行情况比较种群规模迭代次数变异次数交叉次数最好个体适应度值平均适应度运行时间(秒10 4373 850 17124 0.33632524 0.33632524 6.13920 328 979 19721 0.33884413 0.33884413 1.17130 139 1081 21372 0.33429157 0.33

15、429157 0.81240 2748 2776 54835 0.33490189 0.33490189 17.13550 5487 14539 290024 0.34412119 0.34412119 37.334从表4.1可以看出,在种群为30的情况下,执行速度较快,只需要迭代139次,耗时0.812秒就完成了自动组卷工作。而在种群数为10和50实验结果,迭代次数超过4000次,耗时最多为37.334,整体效率不如种群为30时好。实验表明,变异概率P m在0.02左右,交叉概率P c在0.65至0.85范围内,种群规模在20-40时,算法具有良好的运行效果。本文作者创新点:提出了“动态多维

16、矩阵”染色体编码方法,并在此基础上实现了交叉、变异和选择等相关遗传算子,染色体中某种题型、某个知识点的题目数在每次运行是动态产生的,与普通矩阵编码相比节约了内存空间。与传统的线性二进制串、整数等编码相比,该编码方法更加直观,交叉算法更加简单,运行时间大大减少,算法具有更高的效率。参考文献:1 美Zbigniew Michalewicz David B.Fogel著.如何求解问题-现代启发式方法M, 曹宏庆,李艳等译.北京:中国水利水电出版社,2003,2.2 董敏,霍剑青,王晓蒲. 基于自适应遗传算法的智能组卷研究J.小型微型计算机系统.2004, 25(1:82-85.3 陆亿红,柳红.基于

17、整数编码与自适应遗传算法的自动组卷J.计算机工程.2005, (12:232-233.4 马剑英,张晓娜. 基于免疫遗传算法的图像多阈值分割J.微计算机信息.2007, 1-3:309-3115 甘勇,马芳,熊坤,吉星.基于遗传算法和梯度算子的图像边缘检测J.微计算机信息.2007, 2-3:306-308作者简介:王力(1971-,男(苗族, 贵州安顺人, 贵州大学电子科学与信息技术学院副教授,主要从事信息管理与信息系统、智能计算、模式识别研究Biography: Wang Li(1971-,male(Miao,GuiZhou, School of Electronic Science an

18、d Information Technology, Guizhou University, Associate Professor, Information management and information system, Intelligent computation and pattern recognition通信地址:贵州大学蔡家关校区电信学院(550003邮箱:houyL72sina ;wangL_tom 注:本文受贵州大学数据结构重点课程建设基金支持一种基于Markov矩阵的分形建模方法基金项目：福建省教育厅A类科技项目（JA07196）作者简介： 章立亮，副教授，主研领域:分

19、形与计算机图形图像章立亮（宁德师范学院 数学研究所 福建 宁德 352100 ）摘 要 提出一种基于转移概率矩阵的Markov迭代函数系统分形吸引子的建模方法。将MIFS的仿射变换实施多级化的分解，利用转移概率矩阵对吸引子的局部子图像做Markov变形处理，基于计算机数学实验给出了雪花分形和树木分形的应用实例，表明该方法能够有效地控制分形吸引子的局部变形。关键词 迭代函数系统 Markov 变形 分形 A METHOD OF FRACTAL MODELING BASED ON MARKOV MATRIXZHANG Li-liang(Institute of Mathematics,Ningde

20、 Teachers College,Ningde Fujian 352100)Abstract Proposed based on the Markov transition probability matrix iterated function system fractal attractor modeling. Affine transformation will MIFS implementation of the multi-level of decomposition, use of transition probability matrix of the attractor fo

21、r the local sub-image Zuo Markov deformation processing, computer-based mathematics test given snowflake fractal and fractal trees, an application example, show that the method can effectively Fractal Attractor control of the local deformation.Keywords Iterated function systems Markov Decomposition

22、Fractal1 引 言迭代函数系统IFS(Iterated function systems)是分形理论研究的一个重要领域，其理论和方法在分形的计算机构造方面应用广泛。Barnsely M F、Elton J H、Hart J C等人把Markov理论应用于IFS之中，得到更具普遍意义的广义迭代函数系统，开展了许多具体的应用研究1，2，3。国内一些学者也积极从事这方面的研究，讨论有限Markov转移概率矩阵对吸引子的各种作用，分析MIFS吸引子的结构特征4，5，6。由于MIFS系统在函数的选择上加入了可控制的参数，加强了对图形的人为控制，因此，很大程度上丰富了IFS可以表现的分形范围。但这一

23、方法是将Markov矩阵“均匀”地作用于图像的各个局部，引起图像整体结构的演变，在进行分形建模时，它缺乏局部独立表示能力。本文提出一种对分形图像中各局部子图像进行独立处理的方法，利用不同类型的Markov转移概率矩阵，将MIFS分形吸引子图像的各个局部子图像分别实以形状变形，给出了算法的实际应用实例，结果表明该方法具有更好的灵活性和适用性。2 MIFS系统的基本理论 完备度量空间以及个压缩映射组成的映射族 称为迭代函数系统，记作IFS，对于每一个映射伴随一个概率，取依递归方式独立地取。选取充分大的整数，则序列收敛于IFS的吸引子。压缩映射常取如下形式的仿射变换：若将上述构造IFS吸引子的方法进

24、行推广，考虑应用Markov链控制映射的选取，构成Markov迭代函数系统，在迭代计算过程中下一次被选择的映射的概率与前一次被选择的映射密切相关。若记条件概率，则矩阵 称为Markov转移概率矩阵，其中 。表示上次选择的映射为时，这次选择映射的概率。定义 给定完备空间的压缩映射，令是Markov转移概率矩阵，满足：，则称是一个Markov迭代函数系统，记为MIFS 。定理 设为完备度量空间，是相应的由的非空紧集组成的空间，是上压缩比为的MIFS，其中，变换定义如下：，则是上压缩比为的压缩映射，即，且存在唯一的不动点 ,满足,同时,对任意成立。定理中的不动点A称为这个MIFS的吸引子(吸引子通常

25、为分形)，利用Markov转移概率矩阵可以很大地扩展IFS可以表现的分形的范围，这种由转移概率控制的图像生成方法，只要使用的转移概率矩阵不同，则所得到的MIFS吸引子也各不相同。3 分形图像的局部变形算法3.1 算法思想利用Markov迭代函数系统构造IFS分形吸引子，是通过引入Markov转移概率矩阵人为地控制迭代映射的转移，在迭代过程中图像各局部之间迭代计算的转移方式是依概率相关联的 7，这是一种“整体性”的行为，图像中某一局部分形特性的变化必然会影响到其它局部，因此，图像的分形结构常呈现为局部与整体间或局部与局部间存在某种程度上的自相似性。为了克服这种分形结构的自相似性限制，以便能够构造

26、形状特征更加富有变化的分形图像，本文考虑将图像的不同局部分别进行独立构造，并将图像的各局部子图像依次输出，拼贴形成整幅图像，可以只对某一局部子图像实施变形处理，而不会影响到图像的其它局部子图像，如果对不同的局部子图像选取各异的Markov矩阵，则可能产生包含多种不同形状结构的不具自相似特征的分形图像。应用该方法构造分形图像，首先需要得到图像的各局部子图像的分形迭代码，这可以利用迭代函数系统的仿射变换分解定理来实现。3.2 算法描述仿射变换的分解定理8 如果是分形图像的IFS码，是的逆，定义算子为，则是子图像的IFS码。子图像变换矩阵的转换公式为：应用仿射变换的分解定理对MIFS局部子图像的IF

27、S码进行逐级分解，对仿射变换的最终一级分解码，利用Markov转移概率矩阵实行迭代计算生成对应的局部变形图像。如给定仿射变换，的1级分解码设为，对得到的1级分解变换，还可以继续做下一级的分解，其2级分解码设为，依此逐级分解至设定的级数停止。具体算法如下：（1）从仿射变换族中选择某些仿射变换（如），按照转换公式（*）逐级分解至设定的级数（设为n），得到分解码。（2）对分解得到的前n-1级仿射变换序列：规定只参与迭代但不画点。（3）逐个输出经Markov变形处理后的MIFS：局部子图像。（4）逐个输出未曾进行Markov变形处理的其它各级局部子图像。4 应用实例利用以上算法，分别对雪花分形图像和树

28、木分形图像进行局部变形控制，生成形状结构变化多端的分形图像。实例1（雪花分形）设 其中，(a)原吸引子图像 (b)整体变形 (c)1级分解变形 (d)2级分解变形图1雪花分形图像 图1（a）为未做Markov变形处理前的吸引子图像。利用概率矩阵对雪花分形图像做Markov变形得到如图1（b）所示图像，这是一种整体结构的变形，图像的形状结构表现较为“单一”。将分别对应原吸引子图像底部两个子图像的仿射变换进行1级分解，并利用矩阵和分别对这两个子图像做变形，结果如图1（c）所示，由图可见图像包含有3种不同的形状结构。图1（d）是将对应原吸引子图像顶部子图像的仿射变换进行2级分解后，再对此子图像上部的

29、3个2级子图像做Markov变形的结果。实例2（树木分形）设，图2（a）为未做Markov变形处理前的吸引子图像。先将对应树木上枝子图像的仿射变换进行1级分解，再将分别对应树木的左、右侧枝的两个仿射变换进行2级分解，然后利用矩阵对仿射变换的1级分解子图像和仿射变换的2级分解子图像进行Markov变形，再利用矩阵对仿射变换的2级分解子图像进行Markov变形，得到图2（b）的图像，比较图2（a）与图2（b）可以发现，经多级分解变形处理之后的树木其细节变化多端形态更加逼真、自然。 (a)原吸引子图像 (b)1级和2级分解变形图2树木分形图像5 结 论 以上利用IFS仿射变换的多级化分解方法，可以有

30、效地控制MIFS吸引子图像的局部演变，图像的演变范围能够被任意地限制于指定的局部之中，使得不同局部的分形结构有所差异，可以得到形状富有变化的分形图像，特别是在一类自然景物的分形建模方面，计算机图形实验结果已表明能够取得较好的应用效果，该方法的应用进一步拓宽了MIFS吸引子分形图像的表现范畴。参 考 文 献1 Barnsely M F, Elton J H and Hard D P. Recurrent iterated function systems. Constructive Approximation,1989,5:3312 Hart J C. Fractal image compres

31、sion and recurrentiterated function systems. IEEE Computer Graphics and Application,1996,7:25333 Sherman P, Hart J C. Direct manipulation of recurrent models. Computers&Graphics,2003,27:1431514 刘向东,朱伟勇,赵雅明. Markov双曲迭代函数系统参数与吸引子关系的研究.计算机科学,2000,27(5):68715 李红达,叶正麟,彭国华. 向量递归迭代函数系统及其不变测度.系统科学与数学,2003,2

32、3(2):279 2886 王兴元,刘波. 一类NMIFS吸引子的递归计算构造及特性分析.自然科学进展,2004,14(9):103910467 章立亮. Markov迭代函数系统分形的动力学特性分析.工程图学学报,2021, 30(6):1321368 曹汉强,朱光喜,朱耀庭等. 基于迭代函数系统的数字全息图像生成方法.激光杂志,2000, 21(2):3233作者简介： 章立亮，副教授，主研领域:分形与计算机图形图像作者单位: 宁德师范学院数学研究所通信地址：福建省宁德市蕉城南路98-1号 宁德师范学院数学研究所 E-mail: 139 基金项目：福建省教育厅A类科技项目（JA07196）

33、第36卷第9期2006年9月数学的实践与认识Vol.36No.9Sep.,2006用矩阵和积求最短路的一种新算法詹棠森,张三强,唐敏(景德镇陶瓷学院信息工程学院,江西景德333001)摘要:先定义了矩阵和积的概念和运算,在求最短路中,这种方法和线性代数中的矩阵运算相似,通过这种方法,把求最短路转化为矩阵的运算,计算简便,有效.关键词:最短路;矩阵和积;多阶段决策;不完全关联;距离阵1引言求最短路的方法很多,有动态规划的多阶段决策方法1,在动态规划算法中,利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解,而Disjkstra算法是解单源最短路径问题的贪心

34、算法,其基本思想是设置顶点集合S并不断地做贪心选择来扩充这个集合2,3.等.2定义矩阵和积及运算1)符号意义表示和运算表示或运算4,523表示2和32)运算形式和运算律交换律a b=b a分配律a (bc=)(a b)(a c)例2 3=3 2=5,2 (34)=(2 3)(2 4)=56.记 (abc=().3)两矩阵和积的算法设矩阵Ams=(aij)ms,Bsn=(bij)snAmsBsn=Cmn=(cij)mn其中cij=sk=1aik bkj=ai1 b1jais bsj.3构造多阶段决策最短路算法1.完全关联的多阶段问题及距离阵多阶段的决策问题的特点是先将一个复杂问题分解成相互联系的

35、若干阶段,每一个阶段的点(事件点)与后一阶段的点完全相互联系,这种问题称为完全关联的多阶段问题.69期詹棠森,等:用矩阵和积求最短路的一种新算法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,n7.图1W(1

36、)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=(12106,954,1146)42=14128128715810从这些数字中,我们很快找到A到T最短路是7,并按逆推过程可得取得最短路径是AB2C3T,从中可看出距离为8的有3条,距离为10,14,15的各一条,距离为12的有二条.A到T最长距离为15,且路径是AB3C1T.3.其它问题对不完全关联,我们可化不完全关

37、联为完全关联,不是阶段决策问题可化为阶段决策问题.这些问题的转化参考16.在求最小距离时,添加的权记为,在求最大问题时,添加的权记为0.如右图2,实线是已连通,虚线是添加的,且B1C2=4,B2C1=3,B2C3=1,B3C2=8,C1E2=2,C2E3=7,C3E2=10.求A到F的最短路距离.S=(7,8,6)4257963481图2172数学的实践与认识36卷6=(1110,1313,1815)43184=(17161717),1413()1916,()21212219)=(21202121()1918()2421()24242522从上可得最短路是18,其路径是AB2C1E2F.最长路

38、是25,其路径是AB3C3E2F.同理,对多发点和多收点(即第一阶段和最后阶段有多个点)的情况下,这种算法仍然适用,并且也很简便.在此就不再叙述.参考文献:1运筹学教材编写组编.运筹学M.北京:清华大学出版社,1990.2王晓东编.算法设计与分析M.北京:清华大学出版社,2003.3SaraBaase,AllenVanGelder.ComputerAlgorithmsIntroductiontoDesignandAnalysisM.ThirdEdition,HigherEducationPress,2002.4贺仲雄编.模糊数学及其应用M.天津:天津科学技术出版社,1983.5左孝凌等编.离散

39、数学M.上海:上海科学技术文献出版社,1999.6林同曾主编.运筹学M.机械工业出版社,1989.7姜启源等编.数学模型M.高等教育出版社(第三版),2003.OnaNewAglorithmsofTheShortestPathByMatrix-SumProductZHANTang-sen,ZHANGSan-qiang,TANGMin(SchoolofInformationEngineering,JingdezhenCeramicInstitute,JingdezhenJiangxi333001,China)Abstract:Amatrix-sumproductanditscalculationaredefined,themethodissimilaetocal-culationofmatrixinlinearalgebratosolvetheshortestpath,bythisway,theprocessissimpleandeffective.Keywords:shortestpath;matrix-sumproduct;multi-phasedecision-making;incompletecon-nectiondistancematrix