运筹学最短路径

前言：想要写出一篇令人眼前一亮的文章吗？我们特意为您整理了5篇运筹学最短路径范文，相信会为您的写作带来帮助，发现更多的写作思路和灵感。

运筹学最短路径范文第1篇

关键词:Floyd算法;VC++;应用

中图分类号:TP311文献标识码:A文章编号:1009-3044(2010)22-6227-02

Application of Floyd Algorithm in a Class of Practical Problems

WEI Lin-jing1,YUE Jian-bin2

(1.Information Science and Technology College, Gansu Agricultural University, Lanzhou 730070, China; 2.Lanzhou City College, Lanzhou 730070, China)

Abstract: Shortest path problem is the most attractive problem in the graph theory. It's not only of great priority, but also a difficult. This paper analyzes the basic idea of floyd algorithm,and discusses the realization in VC++ by a practical problem.

Key words: floyd algorithm; VC++; application

最短路作为图与网络技术研究中的一个经典问题一直在工程规划、地理信息系统、通信和军事运筹学等领域有着十分广泛的应用。顶点对之间的最短路径是指:对于给定的有向网G=(V,E),要对G中任意一对顶点有序对V、W(V≠W),找出V到W的最短距离和W到V的最短距离。

目前,关于最短路问题的研究已有较多结果,传统的最短路算法主要有 Floyd算法[1]和Dijkstra[2]算法等。其中,Dijkstra算法求解任意顶点对之间最短距离的方法是:轮流以每一个顶点为源点,重复执行算法n次,即可求得每一对顶点之间的最短路径,总的时间复杂度为O(n3)。

Floyd提出了另外一个求图中任意两顶点之间最短路径的算法,虽然其时间复杂度也是 O(n3),但其算法的形式更简单,易于理解和编程。

1弗洛伊德(Floyd)算法的基本思想

Floyd算法是通过权矩阵计算来实现的一种方法,其主要思想是从代表任意两个节点vi到vj距离的带权邻接矩阵 D(0)开始,首先计算D(1),即计算vi到vj经过一次经转的所有可能路径,经过比较后选出最短路,代替D(0)中对应的路径,迭代列出距离矩阵D(1),D(1)中各元素表示通过一次迭代后网络中任意两点间最短路,也即网络中任意两点之间直接到达或只经过一个中间点时的最短路。在此基础上依次计算D(2) ,D(3) ,…,D(k),D(k)中对应的元素表示任意两点间不经过中间点或最多允许经过2k-1个中间点时的最短路。当D(k+1) =D(k)时,表明得到的带权邻接矩阵D(k)就反映了所有顶点对之间的最短距离信息,,成为最短距离矩阵。其算法如下:

第一步,作初始距离矩阵D(0)=(dij(0)),其中:

,其中(i,j=1,2,…,n);

第二步,构造迭代矩阵D(k)=(dij(k)),其中:

;

第三步,若D(k+1)=D(k),迭代终止,否则,返回第二步。

2 问题的提出及求解

设计一个能够计算某城市任意两个院校间最短路距的查询器,院校间交通示意图见图1。要求系统应具备较好的容错与自动计算等功能。两个院校间最短路距是指从一个院校校门到另一个院校校门间的最短里程(单位:千米)。

在具体求解过程中,可以把一个学校所在位置作为一个始点,其他任何学校所处的位置都可能成为终点,即终点是任意的。由于Floyd算法是比较成熟的求非负权网络最短路问题的算法,且是一种多项式算法。在实现Floyd算法的过程中,核心步骤就是从未标记的点中选择一个权值最小的弧段,这是一个循环比较的过程。

利用VC++来求解本问题的过程如下。在VC++中运行程序, 为了避免∞在计算机中无法计算的问题,可以把∞改为100来计算(相对其他的数据来说,是比较大的),这样改动后,并不影响程序运行后所得到结果的正确性。

1) 初始化邻接矩阵和路径矩阵

#define N 20

#define INF 100

float cost[N][N];

int path[N][N];

float A[N][N];

int i,j,k;

for(i=0;i

for(j=0;j

{if(i==j)

cost[i][j]=0;

else

cost[i][j]=INF;

}

cost[0][1]=0.5; cost[1][0]=0.5;cost[1][10]=0.3;cost[2][12]=1.5;cost[2][10]=2.2;

cost[3][18]=1.1; cost[3][16]=0.1;cost[4][16]=0.3;cost[4][15]=0.1;cost[5][15]=0.6;

cost[6][15]=0.3; cost[6][7]=1.3;cost[7][6]=1.3;cost[7][8]=1.0;cost[8][7]=1.0;

cost[8][14]=0.2; cost[9][15]=0.3;cost[9][14]=0.1;cost[10][18]=2.6;cost[10][1]=0.3;

cost[10][11]=1.7 ; cost[10][2]=2.2;cost[11][10]=1.7;cost[11][19]=0.7;cost[11][12]=0.5;

cost[12][13]=0.8 ; cost[12][2]=1.5;cost[13][12]=0.8;cost[13][14]=1.1;cost[13][17]=0.5;

cost[14][13]=1.1; cost[14][8]=0.2;cost[14][17]=0.4;cost[14][9]=0.1;cost[15][5]=0.6;

cost[15][6]=0.3; cost[15][4]=0.1;cost[15][9]=0.3;cost[16][3]=0.1;cost[16][4]=0.3;

cost[16][17]=0.4; cost[17][16]=0.4;cost[17][14]=0.4;cost[17][19]=1.2;cost[17][13]=0.5;

cost[18][3]=1.1; cost[18][10]=2.6;cost[18][19]=0.4;cost[19][18]=0.4;cost[19][11]=0.7;

cost[19][17]=1.2;

for(i=0;i

for(j=0;j

A[i][j]=cost[i][j];

if(cost[i][j]

path[i][j]=i;//初始化路径矩阵,原来有路

else

path[i][j]=-1;//原来没有路

}

2) Floyd算法核心代码

for(k=0;k

for(i=0;i

for(j=0;j

if(A[i][j]>(A[i][k]+A[k][j])){

A[i][j]=A[i][k]+A[k][j];

path[i][j]=k;//表示从i到j,要经过k节点

}

3) 系统运行界面

如图2所示。

3 结论

在实际中最短路径的选取需要考虑多种因素,而这些因素往往又是模糊的。如何综合利用这些因素是交通线路选取所面临的一个关键性问题。本文所提出的方法的优点有:1) 它考虑了影响最短路径选择的多种模糊因素,使得最短路径的选取更加客观;2) 它可以动态的计算最短路径,而且计算速度比较快。实践表明,该方法可以有效的、快速的计算出任意两个学校间的最短路径,具有一定的理论价值和很好的应用价值。

参考文献:

[1] 程理民,吴江,张玉林.运筹学模型与方法教程[M].北京:清华大学出版社,2000.

运筹学最短路径范文第2篇

关键词:“120”系统;智能指挥调度;指挥调度算法;最短路径算法

中图分类号:TP311.1文献标识码:A文章编号:1009-3044(2009)36-10316-02

Design and Practice of Intelligent "120" Command and Dispatch

YU Yong

(He'nan Economic and Trade Vocational College, Zhengzhou 450053, China)

Abstract: Through the study of the "120" Command and Dispatch Process and Features,made a algorithm that could be realized by intelligent command dispatching,the algorithm can be find a Optimal Dispatching scheme which Integrated such asAlarm one's position、Road length、Traffic Condition、Hospital Location、Emergency vehicle's locationand so on.

Key words: "120" system; intelligent command and dispatch; command and dispatch Algorithm; shortest-path algorithm

1 背景

随着电子信息技术的发展,以及社会对公共卫生事件的处置响应速度要求的提高,进一步提高“120”指挥调度系统的信息化水平和智能化水平在当前显得非常迫切,各个城市都在寻求合适的系统进行应用推广。通过参与某市“120”指挥调度系统的建设,深刻体会到急救工作是否及时、妥善,直接关系到伤病员的生命安危和愈后状况,急救工作的状况往往标志着一个国家、一个地区的医疗预防水平的高低,它不仅是医学问题,也是社会和谐的重要体现。但,当前我们国家的“120”指挥调度系统的总体信息化水平还不高,指挥调度还停留在人工阶段,对“120”指挥调度系统进行进一步研究有着现实意义。

通过对“120”指挥调度的流程进行研究,可使用智能化指挥调度代替当前的人工指挥调度,以提高指挥调度的效率和准确性。而要实现智能指挥调度则必须要智能生成指挥调度方案,该调度方案需要根据报警位置、道路长短、交通状况、医疗站点位置、急救车辆位置等多种情况,找到报警位置到最佳的医院或急救车辆的路径,各单位、各部门人员密切配合和协作,通过该调度方案完成一次急救工作,因此,智能指挥调度的关键点在于需要一个算法综合各种情况计算出最优或较优指挥调度方案。

要解决智能生成指挥调度方案的问题,我们可以结合地理信息技术(GIS)将道路网拓扑结构进行提取、构建和存储,将道路网转化为可以使用图论的理论和方法进行分析的道路网拓扑结构图,从而将智能生成指挥调度方案的问题就转化为求解图的最短路径问题。本文通过对常用的最短路径算法进行研究,并结合“120”指挥调度的流程和特点,并提出了一个合理的、适合得出最优或较优指挥调度方案的算法,以支持构建“120”智能指挥调度系统的需要。

2 常用最短路径算法

最短路径问题由来已久,且在现实生活中也经常遇到,当前,它是运筹学、交通工程学、地理信息学等学科的研究热点,国内外很多专家学者对此问题进行了大量的研究,因此,新的最短路径算法不断涌现,它们在空间复杂度、时间复杂度、易实现性及应用范围等方面各具特色,一些算法在一些特定领域得到了广泛的应用,取得了较好的效果。目前,常用的最短路径算法有Dijkstra算法及其改进算法、启发式搜索算法、遗传算法等几类,下面对这几类最短路径算法做一简单介绍。

1) Dijkstra算法及其改进算法

Dijkstra算法是荷兰数学家E.W.Dijkstra于1959年提出的一个适用于非负值网络的最短路径算法,其思路清晰,搜索准确,但是耗时长,占用空间大,鉴于以上缺点,人们对算法进行了做了很多改进。改进主要是集中在Dijkstra算法的数据结构和搜索策略上。在数据结构方面将结点组织成用二进制堆(binary heap)表示的优先队列,或采用Fibonacci堆表示的优先队列,或者使用一个新的数据结构-基数堆(radix heap),这些对数据结构的改进,大大提高了Dijkstra算法的执行效率。

在搜索策略上,主要有限制搜索区域Dijkstra算法,大大缩小了算法的搜索区域,提高了算法的搜索效率;并提出了双向Dijkstra算法,采用起点和终点双向同时搜索的方法,将算法的搜索空间在理论上减少了百分之五十。

2) 启发式搜索算法

启发式搜索算法是基于知识的搜索策略,即通过选定一种估价函数,在搜索过程中都寻找估价函数数值最高的节点作为下一个搜索节点,从而快速的向目标靠近,达到提高算法搜索效率的目的。基于启发式搜索的算法主要有Costed 算法、分支界定法、限制搜索区域法、A*算法等。目前,A*算法在路径规划领域应用的非常广泛,它对实现道路网络的最佳优先搜索很有效。对A*算法的进一步改进算法有:双向启发式搜索、动态管理优化A*算法等。

3) 遗传算法

遗传算法是20世纪60年代,由美国Michigan大学的J.H.Holland 教授首先提出来的。遗传算法是一种优化选择算法,在某种意义上,它是“仿生学”在数学领域的直接应用,该算法的有效性虽尚未有严格的数学论证,然而该算法却在实践上已经有成功的实例,因此,得到了广泛的关注。

4) 其它的一些最短路径算法

除了以上介绍的几类最短路径算法外,还有基于神经网络的最短路径算法、多条最短路径算法、基于GIS空间查询语言的最短路径算法等,它们都在一些特定领域,或在解决一些实际问题上取得了成功的应用。

3 智能指挥调度算法设计

通过对各类最短路径算法进行对比分析,并结合生成指挥调度方案对算法的要求,我们可以在传统的Dijkstra算法的基础上对其进行改进,使之可以满足进行智能指挥调度的需要,改进的Dijkstra算法基本思想是:

将网络节点分成5部分:源节点、未标记节点、临时标记节点、永久标记节点、目标节点(多个)。网络中所有节点首先初始化为未标记节点,接着将与源节点相连通的节点标识为第一批临时标记节点,并选择其中与源节点路径长度最短的节点标识为永久标记节点,从而形成一个从源节点出发的最短路径,接着继续搜索,在搜索过程中,与最短路径中的节点相连通的节点,且该节点在指定的搜索范围之内,则该节点被标识为临时标记节点,每次循环都是从临时标记节点中搜索距源点路径长度最短的节点作为永久标记节点,每次循环,如果找到目标节点中的一个,则得到一个最短路径,并将最短路径计数器加1,直至最短路径计数器达到一定值来结束算法,如果指定范围内的所有节点都成为永久标记结点,且最短路径计数器未达到指定值,则增大搜索范围,继续搜索,直至到达搜索范围的上限或搜索出所有需要的最短路径来结束算法。

改进的Dijkstra算法的求解描述如下:

给定带权有向图G=(V,E)、源点S0、圆形限制搜索区域半径R、圆形限制搜索区域半径增长步长R’、目标节点的集合D、要搜索的最短路径数量Cnt,其中V是包含n个节点的节点集,E是包含m条边的边集,设S为已求得的最短路径的终点的集合,i为已搜索到的最短路径的数量,求S0到目标节点集合D中前Cnt个节点的最短路径生成算法如下:

第一步:利用十字链表CLink来表示带权有向图G,Lij表示弧上的长度,Wij表示弧上的权值,若弧不存在,则将Lij设为∞,Wij设为1。令S为已找到从S0出发的最短路径的终点的集合,将其初始化为空集,令i为已搜索到的最短路径的数量,将其初值设为0。用di表示从S0出发到终点vi的可能到达的最短距离,取其初始化值为:

di=L(s0,vi)*W(s0,vi)vi∈V (1)

第二步:选择vj,使得

dj=min{di│νi∈V-S}(2)

且满足

Dis(S0 , Vj)

其中Dis(i,j)为距离计算函数,表示结点i到结点j的直线距离,

则νj就是当前从S0出发的最短路径的终点,

若

vj∈D(4)

则令

i=i+1(5)

令

S= S∪{vj} (6)

V=V-{vj}(7)

第三步:修改从S0出发到集合V-S中任一顶点νk的可达最短路径长度,如果

dj+ L(j,k)*W(j,k)< dk(8)

则修改dk为

dk= dj+ L(j,k)*W(j,k)(9)

重复操作第二步、第三步,直到i=Cnt,由此可求得按路径长度递增次序排列的从S0出发至目标节点集合D中前Cnt个节点的最短路径序列。

4 智能指挥调度算法实现

上面讨论了改进Dijkstra算法进行“120”指挥调度方案求解的过程,下面将具体给出使用改进Dijkstra算法智能生成“120”指挥调度方案的程序流程图,如图1所示。

在本流程图中,首先需要进行一些参数的定义和初始化工作,其中包括:定义十字链表Clink来表示带权有向图G,其中G就是表示道路网拓扑结构的有向图,其定义为G=(V,E),其中V是G中所有节点的节点集,假设有n个节点,E是G中所有弧的集合,假设有m条弧;十字链表Clink、节点个数n、弧的个数m在加载道路网拓扑结构图时初始化;定义D为目标节点的集合,也就是所有医院节点组成的集合,在加载道路网拓扑结构图时初始化;定义S0表示源点,也是患者的位置所在,S0在调用该算法时初始化;定义R为圆形限制搜索区域半径;定义R’为圆形限制搜索区域半径增长步长;定义Cnt为要搜索的最短路径数量;变量R、R’、Cnt由系统配置参数进行初始化;定义集合变量S为已求得的最短路径的终点的集合,并初始化为空集;定义变量i为已搜索到的最短路径的数量,并初始化为0;设Lij表示弧上的长度,Wij表示弧上的权值,若弧不存在,则将Lij设为∞,Wij设为1。用di表示从S0出发到终点vi的可能到达的最短距离,取其初始化值为L(s0,vi)*W(s0,vi)。使用改进Dijkstra算法进行“120”指挥调度方案求解的过程如图1。

5 结束语

通过对“120”指挥调度流程和方法进行研究,并结合地理信息技术及各类最短路径算法,提出了一种合理的、适合智能生成指挥调度方案的“120”智能指挥调度算法,该算法可大幅提高“120”系统的信息化水平和智能化程度,提高“120”指挥调度的准确性和效率,对当前“120”系统建设具有借鉴意义。

参考文献:

[1] 陆锋,卢东梅,崔伟宏.交通网络限制搜索区域时间最短路径算法[J].中国图像图形学报,1999,4(10).

[2] 付梦印,李杰,邓志红.限制搜索区域的距离最短路径规划算法[J].北京理工大学学报,2004,24(10).

[3] 芟强.双向Dijkstra算法及中间链表加速方法[J].计算机仿真,2004,21(9):79-80.

[4] 孟庆浩,张明路,刘大维,彭商贤.基于双向A*算法的自主车全局路径规划[J].天津大学学报,1998(31):24-29.

运筹学最短路径范文第3篇

[关键词] 优化 反射原理 最短路径

1.引言

某油田计划在铁路线一侧建造两家炼油厂，同时在铁路线上增建一个车站，用来运送成品油。如下图：

由于这种模式具有一定的普遍性，油田设计院希望建立管线建设费用最省的一般数学模型与方法。针对两炼油厂到铁路线距离和两炼油厂间距离的各种不同情形，提出你的设计方案。

2.问题的分析

针对两炼油厂到铁路线距离和两炼油厂间距离的各种不同情形，利用光的反射原理，建立了相应的数学模型，给出了最优设计方案。在方案设计时，若有共用管线，考虑了共用管线费用与非共用管线费用相同或不同的情形。

3.模型的建立与求解

针对两炼油厂到铁路线距离和两炼油厂间距离的各种不同情形，以及是否有共用管线、共用管线费用是否相同。我们以费用最小为目标，建立管线建设费用最省的一般数学模型与方法。

首先我们根据，，三者的关系来判断是否采取共用管线的情形。此时我们假定输油管道费用全部相同，只从路线最长短来考虑，

如图1所示，我们只考虑的情形，（的情形类似考虑）依据光的反射原理我们可以看出，若无共用管线时，最短路径为：

若有共管线，此时我们可得到最短路径为：

比较两种情况的大小：

得到

因此，

当，，满足时，即时，我们选取无共用管线策略，输油的最短路线如图2

此时运油车站设在位置处，且。

当，，满足时，即时，我们选取共用管线策略。

针对共用管线的情形，当共用管线费用相同时，此时我们得到

当共用管线费用不同时，一般情况下，都是大于 ，；因此我们需要考虑他们之间的关系，这里面包括两种情形：共用和共用的情形：

共用时，此时B炼油厂的有先输向炼油厂A，总费用为

共用时，此时A炼油厂的有先输向炼油厂B，总费用为

因此，针对共用管线的情形，我们可得到如下设计方案：

当时，此时共用管线为时，此时A炼油厂的油先输向炼油厂B，输油路线如图3所示：

图3

此时运油车站设在位置D处。

当时，此时共用管线为时，此时B炼油厂的有先输向炼油厂A，输油路线如图4所示：

图4

此时运油车站设在位置C处。

4.模型的改进与推广

输油管线的布置问题，在现实生活中是一个很常见的问题，管线的布置既要考虑路线的长短，又要管线拆迁和工程补偿等附加费以及是否共用管线等问题，优化的布置能节省大量经费，为经济的发展有不可估量的作用。同样地对于铁路线的铺设可做类似的处理。

参考文献：

[1]姜启源等，数学模型，第三版[M].北京：高等教育出版社，2003.

[2]边馥萍等.数学模型方法与算法[M].北京：高等教育出版社，2005.

[3]钱颂迪等．运筹学[M]．北京：清华大学出版社，1997.

[6]周义仓，赫孝良．数学建模实验[M].西安：西安交通大学出版社 1999.

运筹学最短路径范文第4篇

关键字：管网流量分配 分配方法

中图分类号： B026 文献标识码： A

1管网流量分配原因

无论在水利工程中的饮水，还是到城市乡镇的供水系统，我们都要应供水、输水的的要求选择合适的管路半径。现在我们很少就用一根管路来进行水量的输送，已经将管路形成一种复杂的网络行，如环形、循环行管路。我们对管网流量分配的目的, 最初步确定各管段中的流量, 据以选出管径, 在管网设计和计算中, 它是一个重要环节。流量分配的合理与否, 直接影响各管段管径的设计值,进而影响到管网造价和供水能耗。

2管网流量分配方法

流量分配的方法比较多，常用的节点累计法、应用最小平方和的流量分配法、均分法和界面法。一些方法已经不能再满足流量分配的要求。随着管网越来越复杂且一些方法存在的弊端限制了管网发展，出现了很多的改进的流量分配方法以及利用一些边缘学科的技术运用到管网流量的分配上，这些方法获得了优异的成绩，更好的分配了管网流量。下面就几种管网的分配方法做简单的介绍。

2.1节点累计法

节点累计法最初是用于初始分配管段真实流量的一种方法, 必须在各管段流向已定的前提下进行。然后, 从管网配水源节点到终端节点赋以各管段分配流量比例, 即与配水源节点相连结的节点,

其他节点

其中, 为管段 的管段流量参数; K I 为节点i的上游联接管段集合。然后按此比例从管网终端节点到配水源节点分配与各节点连结的上游管段的流量, 即

其中,D I 为节点i 下游管段的集合; K I 为节点i上游管段的集合;为节点i 的节点流量; 为节点i 下游管段的流量。

节点法的流量分配相对比较均匀，难以确定管网主干管线和主干管之间的连接管，同时在分配流量时未考虑管段长度的影响，对管网的经济性和可靠性不利。

2.2最小平方和法

建立流量分配的数学模型,目标函数是管网各管段的摩阻损失总和最小,约束条件是管网在各节点上保持节点流量平衡。因为该数学模型的目标函数是各管段流量平方和的函数,所以此方法称为最小平方和法。初始分配数学模型为:

Min

s.t.

式中f ―――目标函数;

―――以i 为发送节点, j 为接受节点的管段管道常数;

m ―――管网的管段编号;

―――以i 为发送节点, j 为接受节点的管段初始流量,m3/ h ;

A ―――管网的管段2节点关联矩阵;

q ―――管网的管段初始流量向量;

M ―――管网的管段数;

Q ―――管网的节点载荷向量;

N ―――管网的节点数。

缺点：用最小平方和法来分配管段的流量, 有时会出现某些管段流量与同一管段初始真实流

量方向不一致的现象, 该方法对管网布置不是均匀情况, 且各区域用水负荷有明显差异时, 流量分配往往出现较大偏差。

2.3运筹学方法

随着运筹学在各个学科中的应用，它不再仅限于对经济学是的运用，越来越多的应用到了实际工程中。对于都是求解最优解，我们把运筹学中决策树和遗传算法中的部分内容应用到了给水分配上。

2.3.1“最短树”

一个管网图,如果它的每个相异节点之间总存在自一个节点到另一个节点的一条路,则这个图是连通的。从一个管网图中去掉若干条管段所得的一个子图,如果满足(1)是连通的、(2) 没有回路、(3) 包含原管网的所有节点这三个条件,就称为是原管网的一个“树”。

对于管网的一个树,凡是属于该树的管段,称为“树支管段”;凡是属于原管网而不属于该树的管段,称为“连支管段”。

对一个含有环(回路) 的管网,其树的取法有许多种,取法不同,其树支管段的总长度一般不相同,其中至少有一个树的树支管段的总长度最短。树支管段总长度最短的树称为管网的最短树。如果把最短树的树支管段作为给水干管,那么给水干管总长度最短,有利于节省投资并减少运行费用。

现将最短树的算法算法思想介绍如下。

设G(n ,m) 是含n 个节点和m 条边(管段) 的网络,节点编号为整数1 ,2 …,n。在这个网络中取一个节点s 为源点。对G( n ,m)的每个节点赋以数组[D(i ,1) ,D(i ,2) ] ,并设边的长度为L (i ,j) ,i 、j 分别对应该边的两端节点号。算法过程如下。

第一步,对源点s ,令:D ( s ,1) = s ,D ( s ,2) = 0 。并对其余节点令:D(i ,1) = 1 ,D(i ,2)= ∞(一个充分大的数。)

第二步,依次对每条边计算,如果L (i ,j)+ D(i ,2) < D(j ,2) ,则令:D(j ,1) = i ,D(j ,2)=L (i ,j) + D (i ,2) 。重复这一步,直到没有这样的边。

第三步,对各节点至源点的距离D ( i ,2) ,按从小至大进行排序,并将其对应的节点号保存在数组MV(i) 中。

采用该算法编程,程序的输出包括D(i , 1) ,D(i ,2) 和MV(i) 三组数。其中,D(i ,1) 为第i 节点在最短树中连接的上一节点的节点号,D(i ,2) 为第i 节点在最短树中距源点的距离,MV(i) 为距离源点由近至远的节点序列。

“最短树”的方法有利于节省投资并减少运行费用。

2.3.2最小生成树

最小生成树丛法,将环状管网转变成枝状管网。对枝状管网分配初始流量和初始压力降,从而初选管径。

对单流量来源的管网,可确定一棵以供水点为根的最小生成树,任一节点都位于某一树枝上,水流沿着树枝供应到节点,此路径为最短路径。最短路径的确定过程如下。

对全部节点设置标志A 和标志B ,并将全部节点的标志A 和标志B 均设置为0。供水点到某个节点x 的最短路要经过中间节点,由最短路的性质,供水点到这些节点的最短路是供水点到节点x 的最短路的一部分,因此不必求供水点到中间节点的最短路。为了识别这些节点,置其标志A 为1。对已求出供水点到该点最短路的节点,置其标志B 为1。标志A 为0 而标志B 为1 的节点,是最小生成树的树梢,供水点到树梢的最短路,为树枝。

对多个流量来源的管网,可确定最小生成树丛。对于某1 个供水点,其他供水点看成一般节点,确定以该供水点为根的最小生成树。具体应用可查看姜东琪 ,段常贵的最小生成树丛法分配管网初始流量的管径初选[5]。虽然他是针对的是燃气管道的流量，只要在个别参数上加以修改，即可用于输水管道的流量计算上。

应用最小生成树丛法,可将环状管网转变成枝状管网，简化管网。对枝状管网分配初始流量和初始压力降,从而初选管径,为管网水力计算和优化设计计算奠定了基础。

2.3.3遗传算法

遗传算法运算流程图

其中，终止条件一般规定为：计算代数t大于最大运算代数T时，运算终止，否则继续计算。

遗传算法与传统的优化算法不同，大多数古典的优化算法是基于一个单一的度量函数(评估函数)的梯度或较高次统计，以产生一个确定性的试验序列；遗传算法不依赖于梯度信息，是借鉴了生物界的自然选择(Natural Selection)和自然遗传机制的随机搜索(Random Searching Algorithms)，通过模拟自然进化过程来搜索最优解(Optimal Solution)，它采用某种编码技术，作用于称为染色体的数字串，并通过有组织的、随机的信息交换来重新组合那些适应性好的串，生成新的串的群体，并逐步使种群进化到包含近似最优解的状态]。

运用遗传算法有一下几点好处：

1.遗传算法在搜索过程中不易陷入局部最优。

2.遗传算法采用自然进化机制来表现复杂的现象，能快速可靠地求解非常困难的问题。

3.遗传算法具有固有的并行性和并行计算能力。

4.遗传算法具有可扩展性，易于同其它技术混合使用

2.4其他

管网的流量分配的还有很多其他的方法，比如最短路线法，它是确定环状的主要干管供水路线以及主干管之间的连接管，从而，进行初始流量分配的方法。根据初始分配的流量选定经济管径，进行平差计算，最后求出管网造价和年折算费用。当截面法分配流量时，由于未考虑节点流量平衡条件，会出现流量多余或不足的管段。股很少采用。如果对流量进行优化分配，则因目前尚缺理想的解法，且计算较繁，在应用上受到限制。

现在管网为环状的比较的多，故当给水管网为环状网时, 初始流量分配方案不同将导致不同的优化结果。环状管网可有无数多的流量分配方案, 比较复杂, 研究表明环状网只有相对经济的流量分配。一般是由水原点进水节点和控制点,按最短供水路线确定几条平行的主干管线, 并分配大致相近的流量, 主干管之间用连接管相接, 以满足可靠性要求。

管网有限元算法,尽管通用性较强, 但设计人员和初学者须系统掌握有限元的原理等基础知识, 因此就有人模拟电路系统用等效电路的模型及算法来计算管网流量的分配, 它既具有通用性, 并易于设计人员掌握。当然我们在设计管网时还有很多其他的方法来按实际工程要求合理分配流量。

3结论

流量的分配方法会越来越精妙，现在虽还没有很好的方法将流量的分配做到天衣无缝，但已经基本上能够复合我们的工程设计要求。随着计算机技术的发展以及科技的进步，同时很多边缘学科的兴起，我们根据这些计算与理论在不就的将来会有更精妙的方法来分配管道流量，使我们更好的节省管道工程的材料和降低工程的造价。

参考文献

[1]徐得潜.给水配水系统的最优化设计[J]. 中国给水排水，1993,9(5):29-31

[2] 顾丽华,王国明,项建平. 采用节点累计法分配管段虚流量的方法[J]. 合肥工业大学学报( 自然科学版)，2005.28（4）：421-424

[3] 沈致和. “最短树”的多水源给水管网流量分配[J].化工给排水设计，1996，第4期：1-4

[4] 王诗鹏,张国忠. 管网最小平方和法初始流量分配[J]. 油气储运,2004,23（11）：20-22

[5] 姜东琪 ,段常贵. 最小生成树丛法分配管网初始流量的管径初选[J]. 煤气与热力，2003，23（12）：711-714

[6]衡洪飞.基于退火遗传算法的城市给水管网的优化研究[D].2006年4月

[7] 宋建军, 杨广军, 田稚球等. 给水管网设计计算模型及方法的研究[J]. 河北建筑科技学院学报，1998，15（4）：11-15

[8] 肖益民,付祥钊. 环状供热管网水力计算方法探讨[J]. 重庆大学学报(自然科学版) ，2005，28（11）：122-124转150

运筹学最短路径范文第5篇

关键词：图论；灰度；蚁群算法；

中图分类号：TP391.41 文献标识码：A 文章编号：1007—9599 （2012） 14—0000—02

一、引言

图论是离散数学的一个分支，以图为研究对象，研究顶点和边组成图形的数学问题。基于图论的图像分割是将图像分割转化为最优化图的划分问题，相比于传统的分割方法有着独特的优势。

蚁群算法是由意大利学者于上世纪90年代提出来的，是分析蚂蚁群体行为的基础上提出来的一种新的仿生类进化算法。蚁群算法在组合优化问题求解方面获得了成功的应用，引发了学者们广泛的关注。

蚁群算法逐次迭代正反馈的搜索目标，将蚁群算法引入图论中可降低算法复杂度，加快分割过程；同时蚁群算法具有较强的鲁棒性，则将蚁群算法引入图论中搜索过程中不需要进行人工的调整，同时分割效果更加准确。

二、图论和蚁群算法的基本介绍

（一）图论的基本介绍

基于图论的图像分割是将图像映射为一幅无向权图G=（V，E，W），其中V={v1，v2，…，vn}称为顶点集，V中的元素vi称为顶点，vi对应于图像中的像每个素点；E={eij}称为边集，E中的元素eij称为边，eij表示V中任意两顶点之间的连线；W={wij}称为权集，W中的元素wij称为边eij的权，wij表示顶点vi，vj之间的相似程度。

（二）蚁群算法的基本思路与步骤

蚁群算法是在分析蚂蚁群体行为的基础上提出来的。昆虫学家观察和研究发现，蚂蚁具有在没有任何提示的情况下，能够找出从其窝巢到食物源的最短路径，并且能够随着环境的变化而改变，适应性搜索新的路径，产生新的选择。这是由于：在蚂蚁搜索食物源时，能够在爬过的路径上释放信息素，使得一定范围内的其它蚂蚁能够获取信息素并影响这些蚂蚁的行为。某条路径上，信息素越多，蚂蚁选择该路径的概率越大，从而又增加了道路上的信息素浓度。

表示蚂蚁x从图像的i行j列转移到k行l列的转移概率，其中pq表示蚂蚁x能够允许转移的城市，τijkl（t）表示路径（ij，kl）上的信息素浓度，ηijkl表示路径（ij，kl）的能见度，并有 ；

调整信息素浓度的公式为：

根据上面对图论和蚁群算法的基本介绍，我们可以将蚁群算法引入图论分割方法中，得出基于图论使用蚁群算法分割图像。

具体实施步骤为：

四、基于图论的蚁群算法的改进

对于图论中，蚁群算法可以经过一系列的改进，从而使图的分割更加清晰，更好分离出目标和背景的同时计算量减小。

当图片像素点较多时，上述3基于图论的蚁群算法计算量较大，假设一幅图像有N个像素点，一群蚂蚁中有n只蚂蚁，则我们必须要重复n次步骤a到e，才能完成图像的分割。因此，可以通过降低图像的分辨率，使得图中顶点的相似取值减少来减少计算量，也适当的粗化原始图片以减少步骤a到e中的运算次数，可以大大的减少计算量。在3中仅仅考虑了图的灰度属性，可以同时考虑图的亮度，纹理等属性来改进的蚁群算法，分析图片，使得图中两顶点间相似度值更加准确。

五、结论

利用蚁群算法进行图像分割较为精确，但是本算法耗时较长，通过改进，可降低运算量同时不影响图像分割的精确度。

参考文献：

[1]贺国光.ITS系统工程导论[M].中国铁道出版社：181—184

[2]运筹学.《运筹学》教材编写组[M].清华大学出版社：251—253

[3]章毓晋.图像处理和分析[M].清华大学出版社：179—215