基于Floyd算法建模的研究应用（科技创新资料）.docVIP

基于Floyd算法建模的研究应用（科技创新资料） 文档信息 ： 文档作为关于“文学、艺术、军事或历史”中“声乐器乐”的参考范文，为解决如何写好实用应用文、正确编写文案格式、内容素材摘取等相关工作提供支持。正文4459字，doc格式，可编辑。质优实惠，欢迎下载！ 目录 TOC \o 1-9 \h \z \u 目录 1 正文 1 文1：基于Floyd算法建模的研究应用 1 文2：基于Kmeans算法车牌分割的应用 6 0　引言 6 1　算法描述 7 （4）图像的输出 8 2　仿真实验 8 3　总结 9 参考文摘引言： 9 原创性声明（模板） 10 文章致谢（模板） 10 正文 基于Floyd算法建模的研究应用（科技创新资料） 文1：基于Floyd算法建模的研究应用 ０引言 Ｆｌｏｙｄ算法是求解带权图中所有顶点对之间最短路问题的最有效的算法之一，这一算法在实际生产生活中经常遇到，因此，许多文献都对此算法作了介绍。通常的最短路径算法，都是建立在抽象的数学模型之上，即网络模型。本文将从图论中的带权图，用数学建模的方法来探讨Ｆｌｏｙｄ算法的原理、路径标记方法、及其应用。 １Ｆｌｏｙｄ算法描述 １．１基本思想 Ｆｌｏｙｄ算法是由弗洛伊德（Ｆｌｏｙｄ）提出的，又称为插点法，其基本思想是： 第一，设邻接矩阵W，其元素W［i］［j］为权值，若权值为∞，表示两点之间不存在直接连通弧。 例如在一个带权图中，设结点数为n(v1，v2，…，vn)，求从结点vi到vj的最短路径。若从到有连通弧，则存在一条路径，长度记为W［i］［j］的，但是不一定为最短路径，所以多数需要做n次试探。 第二，验证路径(vi ， v1 ， vj)的存在性（即弧(vi ， v1)和v1 ， vj的存在性）．若存在，则比较(vi ， vj)和(vi ， v1 ， vj)的路径长度，其最短路径取法是序号不大于１，从vi到vj长度较短者的中间顶点；若再增加点v2，最短路径的选法将它和前面不大于１的最短路径相比较之后，从中选出中间顶点的序号不大于２的最短路径，继续增加一点v3，进行试探，依次做下去。 在通常情况下，若（ｖｉ，…，ｖｋ）和 （ｖｋ，…，ｖｊ）分别表示的是从ｖｉ到ｖｋ与从ｖｋ到ｖｊ的中间顶点序号不大于ｋ－１的最短路径，把已经得到的从ｖｉ到ｖｊ中间顶点序号不大于ｋ－１的最短路径和（ｖｉ，…，ｖｋ，…，ｖｊ）相比较，较短者就是从ｖｉ到ｖｊ的中间顶点的序号不大于ｋ的最短路径；类推下去，经历ｎ次比较后，最后可得从ｖｉ到ｖｊ的最短路径。按此方法，就可求得各对顶点间的最短路径；同时，在比较过程中利用一个动态数组ｐａｔｈ记载每次进行路径试探过程中获得最短路径的结点编号。 １．２基本步骤 有ｎ个顶点的一个带权图Ｇ， 从１到ｎ进行编号．设距离矩阵的初值为带权邻接矩阵Ｗ，即 Ｄ（０）＝（ｄｉｊ（０））ｎ×ｎ＝Ｗ 其中：ｄｉｉ＝０，ｉ＝１，２，…，ｎ；ｄｉｊ＝∞，当ｉ，ｊ之间没有边时． 对于无向图，Ｄ（０）是对称矩阵， ｄｉｊ＝ｄｊｉ． Ｆｌｏｙｄ算法就是递推产生一个矩阵序列Ｄ（０），Ｄ（１），…，Ｄ（ｎ）。其中ｄｉｊ（ｋ）表示从顶点ｖｉ到顶点ｖｊ的路径上所经过的顶点序号不大于ｋ的最短路径长度． 第１步构造Ｄ（1）＝（ｄｉｊ（1））ｎ×ｎ，其中ｄｉｊ（１）＝ｍｉｎ｛ｄ（０）ｉｊ，ｄｉ１（０）＋ｄ１ｊ（０）｝是从ｖｉ到ｖｊ的只允许以ｖ１作为中间顶点的路径中最短路长度． 第２步构造Ｄ（2）＝（ｄｉｊ（2））ｎ×ｎ，其中ｄｉｊ（2）＝ｍｉｎ｛ｄ（1）ｉｊ，ｄｉ2（1）＋ｄ2ｊ（1）｝是从ｖｉ到ｖｊ的只允许以ｖ１，ｖ２作为中间顶点的路径中最短路长度． 第ｎ步构造Ｄ（ｎ）＝（ｄｉｊ（ｎ））ｎ×ｎ，其中ｄｉｊ（n）＝ｍｉｎ｛ｄ（n-1）ｉｊ，ｄｉn（n-1）＋ｄnｊ（n-1）｝是从ｖｉ到ｖｊ的只允许以ｖ１，ｖ２，…，ｖｎ作为中间点的所有路径中最短路的长度． 故Ｄ（ｎ）是距离矩阵，反映了所有顶点对之间的最短距离信息． ２Ｆｌｏｙｄ算法应用 ２．１选址问题 当知晓了一些现有设施的地址，如果要进而在确定一些新设施的地址，这是选址问题的意思。但是大部分选址问题，依据现实情况，有时候只有少数个地址能选择，所以通常采用离散型法来进一步解决。而求对应网络中全部点对间的最短路便是解决离散型选址问题的关键。 例１配送中心是物流网路中举足轻重的结点，它不仅承载着多种物流功能，还越来越多地进行指挥调度、信息处理等重要的职能，是全部物流网络的关键所在．今考虑在某个城市建立一个物流配送网络．如果各需求点之间物流费用见图１，试择最佳配送中心。 解：首先，运用Ｆｌｏｙｄ算法构造距离矩阵． 由图１写出其初始带权邻接矩阵Ｄ（０） 依次插入中间点，得距离矩阵： 其次，计算各顶