模糊最短路

模糊最短路（精选十篇）

模糊最短路 篇1

对于近年来国内外重大故障的分析表明,因线路故障或过载而切除之后所产生的连锁线路切除是造成电网事故扩大甚至系统崩溃的重 要原因[1,2,3]。其之所以发生是由于故障或过载支路切除之后导致与该支路传输功率同向的线路传输功率过载而被相继切除,使得事故扩大。若能事前探测到因事故或过载支路切除而会产生传输功率重大改变的线路及断面,并对可能出现过载的支路采取重调甚至切负荷等措施,则可避免线路连锁跳闸切除的发生。因此,如何快速地辨识及搜索出因故障或过载支路跳闸切除而导致传输功率明显变化的其他线路及输电断面(以下简称关键输电断面),就成为备受关注亟待解决的问题之一。

近年来,已有不少文献提出了相关关键输电断面的快速搜索及辨识方法。文献[4]基于区间并行输电断面及电气距离,先简化网络并进行分区,然后通过可达矩阵进行逻辑运算判断关键输电断面。文献[5]基于潮流追踪技术[6,7,8]来辨识关键输电断面,该方法首先采用潮流追踪技术获得所有线路的功率构成,然后采用差离平方和对线路进行聚类,得到线路的并行输电断面。该方法具有比较高的辨识率,但是聚类时由于需要人工选择阈值确定样本分类数,不可避免地存在线路漏选或多选问题[9]。当前,很有代表性的一类方法是基于最短路径法确定相关输电断面。所谓最短路径是指从故障或过载支路的一个端点到达另一端点电气距离最小的连续支路组。文献[10]认为当故障支路或过载支路跳闸之后,最短路径上的所有支路相对于其他支路具有更大的跳闸可能性,故认为最短路径上的支路组即为关键输电断面。由于最短路径上的支路组的总电气距离最小,其上与故障或过载支路功率方向同向的支路确实是关键输电断面中的支路,但功率方向相反的支路却不是关键输电断面中的支路;另外,若只关注最短路径上的支路,很可能造成很多支路的漏选[11,12,13,14]。文献[15-17]提出了基于前k次最短路径的关键输电断面辨识方法,以克服只在最短路径上寻找输电断面所产生的支路漏选问题;如何合理地确定k值是该类方法的关键,当前基本上是凭经验公式确定,若选择不恰当,则可能多选或漏选支路。

基于如上综述,本文提出了基于功率构成模糊聚类和最短路径的潮流转移关键输电断面快速搜索新方法。该方法既避免了文献[8]人为给定聚类数目以及可能的漏选及多选线路的缺点,又克服了最短路径类方法中k值按经验选定的缺点,实现了基于潮流追踪关键输电断面选择方法和最短路径选择关键输电断面方法的有机融合和优势互补,进一步提高了辨识精度。

1关键输电断面定义及初始输电断面确定

1.1关键输电断面的相关定义

输电断面:有功潮流方向相同且电气距离相近的一组输电线路的集合称为输电断面。

并行输电断面:与故障或过载支路有相同电源区或负荷区的输电断面称为该支路的并行输电断面。

关键输电断面:故障或过载支路开断之后有功潮流增幅较大的输电回路所组成的输电断面称为该故障或过载支路的关键输电断面,即故障或过载支路开断之后关键输电断面中的支路具有较大的功率分布因子(通常大于某一门槛值)。

停电事故表明线路故障或切断过载支路后,潮流往往较多地涌向与其具有相同电源区或负荷区的输电断面,即并行输电断面,使得并行输电断面中的部分或全部线路出现过载而跳闸。而出现过载的并行输电断面中的支路即构成了相应故障或过载支路的关键输电断面[7]。

1.2基于潮流跟踪的线路功率构成计算

基于潮流跟踪方法计算线路功率构成的步骤如下[6,7,8]。

步骤1:对于发电机数为NG、负荷数为NL、支路数为NB的电网系统,基于系统潮流计算形成有向图,得到节点—支路关联矩阵;建立发电机对线路潮流贡献因子矩阵KlG和负荷对线路潮流汲取因子矩阵KlL。

步骤2:计算线路j(j=1,2,…,NB)传输功率中发电机i(i=1,2,…,NG)的贡献功率Pi-j和负荷m(m=1,2,…,NL)的汲取功率Pj-m,即

式中:Pi为发电机i的功率;Pm为负荷m的功率。

步骤3:计算发电机i经线路j向负荷m输送的功率Pi-j-m,即

式中:Pj为线路j上传输的功率。

对于NG台发电机及NL个负荷,所有发电机经线路j向所有负荷输送的功率即组成了NGNL维的向量PjΣ= [P1-j-1P1-j-2…PNG-j-NL]T。向量PjΣ各元素的 代数和sj等于Pj,因此,向量PjΣ表示线路j的功率构成。对于电网中的NB条支路,每一支路均有一个相应 的功率构成,由这些NB个支路功率构成向量组成了矩阵P:

1.3基于模糊聚类的初始关键输电断面确定

故障或过载支路切除之后,潮流往往较多地涌向与被切支路有相同电源区或负荷区的输电断面,导致其中部分支路过载而出现连锁切除,因此,文献[8]采用聚类方法寻找与故障或过载支路相似的功率构成支路,构成故障或过载支路的并行输电断面。但由于所使用的聚类方法需要人为给定聚类数,而该聚类数只能凭经验或反复试验来选择最佳值,故不可避免地存在漏选及多选问题。

为了回避人为给定聚类个数所产生的误差,本文采用基于划分熵指数为准则函数的模糊聚类方法来确定故障或过载支路的并行输电断面。先求出每个备选聚类中心数T所对应的聚类结果,然后依据熵指数准则函数计算每个聚类结果所对应的准则函数值。根据准则函数值确定最优聚类中心数以及相应的聚类结果,从而实现无需事先给定聚类中心数即可聚类的随机模糊聚类算法。

划分熵指数公式为[9]:

式中:EP的取值范围为[0,lnT];T为当前分类数,其取值范围为[2,Tmax],其中Tmax为最大分类数,通常为表示上取整运算;ujt为线路j隶属于第t个聚类中心的隶属度。

当分类数T固定时,若线路关于某类的隶属度越大,而关于其他类的隶属度越小,EP越接近于0,则聚类越硬;当线路隶属于每个聚类中心的隶属度均相同时,EP值为lnT,聚类最模糊,无法判断线路隶属于哪个中心。

EP 与分类数T的关系曲线如图1所示,即EP随着T的增大而增大。T值越小,EP值越小,代表聚类越明确,相应聚类也越硬。一个最佳的聚类数需综合计及聚类清晰度及聚类硬度,一般选择T与EP 的关系曲线中的递增曲率显著变化点所对应的T为最佳聚类结果Tbest[9],此时EP值为EP(Tbest)。

对于由1.2节所得到的所有线路的功率构成向量,对其进行基于划分熵指数为准则函数的模糊聚类而获得初始输电断面,具体步骤如下。

步骤1:初始分类数T=2;给定Tmax,通常取小于

步骤2:计算线路 功率构成 向量PjΣ(j =1,2,…,NB)元素代数和序列sj(j=1,2,…,NB),其中最大值记为smax,最小值为smin。

步骤3:计算当前初始聚类中心,k=0;计算线路j归一化模值αj(T),即

式中:1≤αj(T)≤T。

步骤4:计算当前线路功率构成向量PjΣ隶属于第t个聚类中心ct(k)的隶属度uj(tk),即

式中:m∈(1,∞)是一个加权指数。

相应地进一步得到隶属度矩阵U(k):

步骤5:令k=k+1,更新聚类中心,即

步骤6:若t∈ {1,2,…,T },均有|c(k+1)t-ct(k)|<ε,则得到了对应于分类数为T时的聚类结果,即每个样本对所有聚类中心的隶属度,以及相应的聚类中心,转步骤7;否则转步骤4。

步骤7:计算划分 熵指数EP(T),则有

步骤8:T=T+1,若T<Tmax,转步骤3;否则,得到T与EP(T)的关系曲线,转步骤9。

步骤9:计算T不同取值时的曲率K(T),计算公式为K(T)=|y″|/(1+y′2)3/2,其中y为曲线T-EP(T)的关系表达式EP(T)=y(T)。当K(T)最大时,对应的点为(Tbest,EP(Tbest)),即为曲线递增曲率显著变化点,此处T值即为最佳分类数Tbest。得到聚类最佳分类结果,聚类过程结束。

经过随机模糊聚类后,与故障或过载支路同属一类的支路组成了初始输电断面。不难看出,该聚类方法无需事先给定聚类数,整个聚类过程针对线路功率构成向量依据数据驱动进行分类,避免了主观给定分类数所产生的影响。

2基于最短路径的关键输电断面确定

虽然第1节的模糊聚类方法可以提高故障或过载支路的并行支路的辨识率,但仍需事先给定最大分类数Tmax、加权指数等主观参数,以及计算误差等原因,线路漏选问题仍可能存在,上述方法所确定的输电断面还只能是初始输电断面。为了避免漏选,本文进一步搜索同时包含初始输电断面中的支路和故障或过载支路的最短回路,选定故障或过载支路的潮流方向为回路潮流方向,并逐一考察最短回路中的全部支路。若其潮流方向与故障或过载支路方向相反,则为候选关键输电断面中的支路,从而实现对初始输电断面中的支路进行筛选,以及补充在初始断面确定时所漏选的支路。

基于Dijkstra算法[18]的包含两条支路的最短回路搜索过程如下:以支路电抗作为边的权值,路径长度即为路径内全部支路的电抗总和,阻抗值最小的路径即为最短路径;假定故障或过载支路a-b的潮流方向为a→b,初始输电断面中第i条支路的端点为ui和vi,功率方向为ui→vi。采用Dijkstra算法搜索a到ui的最短路径li,长度记为d1;b到vi的最短路径l2,长度记为d2;搜索a到vi的最短路径l3,长度记为d3;b到ui的最短路径l4,长度记为d4。如果(d1+d2)<(d3+d4),说明l1,l2与a-b,ui-vi 构成最短回路,如图2(a)所示。如果 (d1+d2)>(d3+d4),说明l3,l4与a-b,ui-vi 构成最短回路,如图2(b)所示。

确定了最短回路之后,以故障或过载支路的潮流方向为回路方向,若最短回路中支路的潮流方向与回路方向相反,则其为候选关键输电断面中的支路,否则该支路不是候选关键输电断面中的支路。与图2类似,若支路a-b为故障或 过载支路,支路ui-vi 为初始关键输电断面中的支路,其最短回路及支路潮流方向如图3所示。

图3中,a-b为过载支路,ui-vi 为并行支路 ,l1,l2,l3为最短路径中的支路,且未出现在初始输电断面集合中。根据回路潮流方向判定,l2潮流方向与回路潮流方向相反,为漏选支路,保留为候选关键输电断面中的支路;l1和l3潮流方向与回路方向相同,不是候选关键输电断面中的支路;初始输电断面中的支路ui-vi 潮流方向与回路潮流方向相反 ,也保留为候选关键输电断面中的支路。

因此,对于支路数为Nc的初始关键输电断面,基于最短路径的候选关键输电断面确定方法的具体步骤如下。

步骤1:j=1。

步骤2:确定同时包含初始输电断面中支路j与故障或过载支路的最短回路。

步骤3:以故障或过载支路潮流方向为回路方向,依回路方向遍历当前最短回路中的全部支路,与回路方向相反的支路,选入候选关键输电断面。

步骤4:j=j+1;若j>Nc,程序结束,否则转步骤1。

通过上述步骤,既确定了初始输电断面中的支路是否为候选关键输电断面中的支路,同时也补充了不在初始输电断面中的部分支路,相应实现了初始输电断面确定时漏选支路的补充。

对于实际系统而言,根据1.1节的定义,关键输电断面中的支路因故障或过载支路切除之后的传输功率变化率要相对大,即要大于某一设定值λ0(本文取0.2)。因此,需进一步对于候选关键输电断面的每一支路,校核其故障或过载支路切除之后相应的功率分布因子是否大于λ0:若是,则该支路为关键输电断面中的支路;否则,从关键输电断面中删除该支路。因此,按式(10)计算候选关键输电断面中的每一支路lj在故障或过载支路li开断后的功率分布因子λj为:

式中:Pj(0)和Pj(1)分别为支 路li开断前后 线路lj的有功功率。

若λj≥λ0,线路lj为最后的关键输电断面中的支路;否则,线路lj不为最后的关键输电断面中的支路,并删除。这样,就得到了最后的故障或过载支路的关键输电断面中的所有支路。因此,本文所提出的搜索关键输电断面算法的总体过程如下。

步骤1:基于系统有功潮流形成有向图,确定顺流、逆流节点顺序,计算发电机对线路的贡献功率和负荷对线路的汲取功率,得到所有线路的功率构成向量。

步骤2:基于所有线路的功率构成向量,采用划分熵指数为准则函数的模糊聚类方法来确定故障或过载支路的并行输电断面,与过载支路同属一类的支路组成过载支路的初始输电断面。

步骤3:基于最短路径对初始输电断面的每条线路进行判别,找到同时包含待定支路和过载支路的最短路径,并确定最短回路中的候选关键支路。

步骤4:基于分布因子,进一步确定候选关键输电断面中的支路为最后的关键输电断面中支路。计算故障或过载支路切除之后候选关键输电断面中的每一支路的功率分布因子,若大于设定值,则保留该线路为关键输电断面支路;否则,删除该线路。最终的线路集合即构成关键输电断面。

3算例及仿真分析

为验证算法的可行性和有效性,以IEEE14节点系统、IEEE118节点系统及安徽电网作为算例,对本文方法、文献[8]方法(使用差离平方和法聚类基于功率构成搜索关键输电断面)、基于前k最短路径方法搜索关键输电断面[11]及完全潮流计算选出的相应关键输电断面集(为正确断面)进行对比分析。使用前k最短路径方法搜索关键输电断面时,k值的选择至关重要,k值选择的经验公式为:

式中:Pi-len为两点间第i条最短路径的长度;M为路径长度之比的阈值,取整数3,同时为了防止时间过长,限制k最大取4。

3.1IEEE14节点系统

附录A图A1为IEEE14节点系统,计算结果如表1所示,表中λ为对应支路的潮流分布因子。

从表1不难得到如下情况。

1)文献[8]方法所得到的关键输电断面,当过载支路为2-4时,选择在6次聚类内与过载支路合并的支路作 为并行输 电断面的 候选支路,得到支路2-4的输电断面为支路5-4,2-5,1-5,漏选支路23;过载支路为5-4时,选择在7次聚类内与过载支路合并的支路作为并行输电断面的候选支路,得到支路5-4的输电断面为支路2-4,1-2,2-3,没有漏选支路;过载支路为4-7时,选择在5次聚类内与过载支路合并的支路作为并行输电断面的候选支路,得到支路2-4的输电断面为支路4-9,漏选支路5-6,11-10,6-11。

2)当过载支路为2-4时,由k值选取的经验公式计算可得k=3(两点之间 一共有3条路径,且P1-len/P1-len=1<3,P2-len/P1-len=1.50<3,P3-len/P1-len=1.70<3)。选定k=3,会漏选支 路2-3(λ2-3=0.27);过载支路为5-4时,由k值选取的经验公式计算 可得k=2(P1-len/P1-len=1<3,P2-len/P1-len =1.30<3,P3-len/P1-len=3.67>3)。选定k=2,会漏选支路2-3(λ2-3=0.23);过载支路为4-7时,由k值选取的 经验公式 计算可得k=4(P1-len/P1-len=1<3,P2-len/P1-len=1.32<3,P3-len/P1-len=1.78<3,P4-len/P1-len=2.07<3)。选定k=4时,不会出现支路漏选情况,但会出现多选少量无关支路的情况,多选了支路2-5,4-3(完全潮流计算λ2-5=0.03,λ4-3=0.02)。

3)本文方法可以找到关键输电断面中的所有支路。在模糊聚类形成并行输电断面之后,若存在支路漏选问题,通过Dijkstra最短路径搜索可以补充漏选支路。当过载支路为2-4时,根据线路功率构成相似程度进行聚类,最佳聚类数为3,过载支路的初始输电断面为1-2,2-3,1-5,2-5,4-3,5-4。这些支路构成过载支路的初始输电断面。之后基于最短路径对支路进行搜索,同时对最短路径中的支路按支路潮流方向进行判断,得到候选关键输电断面中的全部支路,最后计算潮流分布因子,得到过载支路2-4的关键输电断面为支路2-3,1-5,2-5,5-4,本文搜索结果与完全潮流计算结果完全一致。

当过载支路为5-4时,根据线路功率构成相似程度形成聚类,得到最佳聚类数为3。与过载支路同属一类的支路为1-2,2-3,2-4,1-5,2-5,4-3,这些支路构成过载支路的初始输电断面。之后基于最短路径对支路进行搜索,同时对最短路径中的支路按支路潮流方向进行判断,得到候选关键输电断面中的全部支路。 最后计算 潮流分布 因子,得到支路5-4的关键输电断面为支路1-2,2-3,2-4,本文结果与完全潮流计算结果完全一致。

当过载支路为4-7时,根据线路功率构成相似程度形成聚类,得到最佳聚类数为3。与过载支路同属一类的支路为5-6,6-12,6-13,4-9,7-9,这些支路构成过载支路的初始输电断面。之后基于最短路径对支路进行搜索,同时对最短路径中的支路按支路潮流方向进行判断,得到候选关键输电断面中的全部支路:4-9,5-6,6-11,11-10,6-12,6-13,12-13,13-14。最后计算潮流分布因子,λ4-9=0.52>0.20,λ5-6=0.49>0.20,λ6-11=0.30>0.20,λ11-10=0.23>0.20,λ6-12=0.05<0.2,λ6-13=0.16<0.20,λ12-13=0.04<0.20,λ14-12=0.05<0.20,得到过载支路4-7的关键输 电断面为 支路4-9,5-6,6-11,11-10。本文结果与完全潮流计算结果完全一致。

3.2IEEE118节点系统

附录A图A2为IEEE118节点系统,该方法的计算过程及结果示于附录A表A1。可以看出,本文方法的辨识率为100%,而其他方法要么多选,要么漏选,进一步证明了本文方法的正确性。

3.3安徽电网

本文算法已用于安徽电网实际运行中,通过搜索过载支路关键输电断面而避免出现连锁过载事故。安徽电 网正常运 行时,共有1205个节点和1298条线路。计算结果示于表2。

1)文献[8]方法所得到的关键输电断面,当过载支路为洛众5301线时,选择在5次聚类内与过载支路合并的支路作为并行输电断面的候选支路,搜索出皋西5357线、洛庄5306线为输电断面,这些支路所在的最小回路与过载支路相反,且功率分布因子大于0.20(皋西5357线λ=0.34,洛庄5306线λ=0.80),对比完全潮流计算的结果,漏选支路兴肥5355线及汤皋5351线(汤皋5351线λ=0.38,兴肥5355线λ=1.00)。

2)前k最短路径方法所搜索得到的关键输电断面,k值的选择至关重要。由k值选取的经验公式计算k=1(P2-len/P1-len=4.6>3),选定k=1时,当过载支路为洛众5301时,对比完全潮流计算的结果,漏选支路 兴肥5355线及汤皋5351线 (汤皋5351线λ=0.38,兴肥5355线λ=1.00)。

3)本文方法可以找到全部关键输电断面。过载支路为洛众5301线时,根据线路功率构成相似程度进行聚类,最佳聚类数为3,过载支路的初始输电断面为皋西5357线、洛庄5306线等216条支路。之后基于最短路径对支路进行搜索,同时对最短路径中的支路按支路潮流方向进行判断,得到候选关键输电断面中的全部支路(共101条)。最后通过计算候选关键输电断面的支路的功率分布因子对线路进行筛选,得到最后的关键输电断面。本文得到洛众5301线的关键输电断面为皋西5357线(λ=0.34>0.20),洛庄5306线(λ=0.80>0.20),兴肥5355线(λ=0.10>0.20),汤皋5351线(λ=0.38>0.20),其中兴肥5355线、汤皋5351线不属于初始输电断面,通过使用最短路径算法搜索包含洛庄5306线与过载支路的最短回路将其补充到候选关键输电断面中。本文搜索结果与完全潮流计算结果完全一致。

上述算例表明,本文方法所选择的关键输电断面均与潮流计算结果完全一致,比文献[8]方法及基于前k最短路径方法搜索关键输电断面的辨识率明显要高,而其他两种方法均存在漏选或多选问题。因此,证明了本文方法可以避免其他两种方法的漏选或多选问题,实现了两种方法的有机结合和优势互补。

为了验证本文所采用的划分熵指数模糊聚类方法相对于其他模糊聚类方法的有效性,将本文方法与其他模糊聚类方法对于同一算例进行了计算对比(仅模糊聚类方法采用不同的方法,其余部分均相同),其结果列于附录B中。从附录B的计算结果可以看出,本文所采用的模糊聚类方法相对于其他模糊聚类方法结果更优。

4结语

本文提出了基于功率构成模糊聚类和最短路径的电力系统关键输电断面快速搜索新方法。该方法首先采用基于准则函数的随机聚类方法对由潮流追踪所获得的所有线路功率构成进行分类,而获得故障或过载支路的并行支路集构成初始输电断面,以避免由于人为给定分类数的不恰当所产生的多选及漏选问题;然后对初始输电断面中的每一支路,依次从故障或过载支路的一端开始搜索包括相应支路的到故障或过载支路另一端的最短路径,在该路径上所有与故障或过载支路潮流方向相同的支路,均为关键输电断面中的候选支路;所有最短路径中与故障或过载支路潮流方向相同的所有支路即构成了关键输电断面中的所有候选支路,候选支路再经简单的分布因子校核计算即可确定为最后的关键输电断面支路。

该方法既避免了基于潮流追踪法确定关键输电断面的人为给定聚类数目以及可能的漏选及多选线路的缺点,又克服了最短路径类方法中k值按经验选定的缺点,实现了基于潮流追踪关键输电断面选择方法和最短路径选择关键输电断面方法的有机融合和优势互补,使得辨识精度得到了进一步的提高。因此,本文方法具有良好的实际工程应用前景。

附录见本 刊网络版 (http://www.aeps-info.com/aeps/ch/index.aspx)。

摘要：针对因支路故障或过载被切除之后的潮流转移关键输电断面如何正确快速确定问题,提出了基于模糊聚类和最短路径的潮流转移关键输电断面快速搜索新方法。该方法首先采用具有自适应选择最佳分类数的随机聚类方法,对所有线路功率构成进行分类,获得故障或过载支路的并行支路集构成初始输电断面,以避免由于人为给定分类数的不恰当所产生的多选及漏选问题;然后对初始输电断面中的每一支路,依次从故障或过载支路的一端开始搜索包括相应支路的到故障或过载支路另一端的最短路径,在该路径上所有与故障或过载支路潮流方向相同的支路,均为关键输电断面中的候选支路,以补充单纯由聚类方法确定的候选支路可能的漏选;候选支路再经简单的分布因子校核即可确定是否为关键输电断面中的支路。该方法实现了基于支路功率聚类关键输电断面选择方法和最短路径关键输电断面选择方法的有机融合和优势互补,提高了辨识精度。多个算例证实了文中方法的有效性。

最短路径教案 篇2

一、教学内容：本节课的主要内容是利用轴对称研究某些最短路径问题，最短路径问题在现实生活中经常遇到，初中阶段，主要以“两点之间，线段最短”“连接直线外一点与直线上各点的所有连线中，垂线段最短”为知识基础，有时还要借助轴对称、平移、旋转等变换进行研究。

本节课以数学史中的一个经典故事----“将军饮马问题”为载体开展对“最短路径问题”的课题研究，让学生经历将实际问题抽象为数学的线段和最小问题，再利用轴对称将线段和最小问题转化为“两点之间、线段最短”的问题。

二、教学目标

1、能利用轴对称解决简单的最短路径问题

2、再谈岁最短路径的过程中，体会“轴对称”的桥梁作用，感悟转化的数学思想。

三、教学重难点

重点：利用轴对称将最短路径问题转化为“两点之间、线段最短”问题。难点：如何利用轴对称将最短路径问题转化为线段和最小问题。

四、教学问题诊断

最短路径问题从本质上说是最值问题，作为初中学生，在此前很少涉及最值问题，解决这方面问题的数学经验尚显不足，特别是面对具有实际背景的最值问题，更会感到陌生，无从下手。

解答“当点AB在直线l的同侧时，如何在l上找到点C，使AC与BC的和最小”，需要将其转化为“直线l异侧的两点，与直线l上的点的线段的和最小”的问题，为什么需要这样转化，怎样通过轴对称实现转化，一些学生会存在理解上和操作上的困难。

在证明“最短”时，需要在直线上任取一点（与所求做的点不重合），证明所连线段和大于所求作的线段和，这种思路和方法，一些学生想不到。

教学时，教师可以让学生首先思考“直线l异侧的两点，与直线l上的点的和最小”为学生搭建“脚手架”，在证明最短时，教师要适时点拨学生，让学生体会任意的作用。

五、教学过程

教师引语：现实生活中经常会有这样的生活经历，比如学校虽然为我们铺设了一些石板甬路，方便同学们的行走，但是很多时候我们却并不在这些小路上行走，这样做的目的是什么呢？（学生一起回答）如果用数学知识来解释这种行为，那就是我们曾经学习的“两点之间、线段最短”或“垂线段最短”，我们称这样的问题为最短路径问题（板书课题）现实生活中经常涉及到最短路径问题，这节课我们学习的主要任务就是最短路径问题，并用所学知识探究数学史上著名的“将军饮马问题”。

1、情境引入

相传，古希腊亚历山大里亚城里有一位久负盛名的学者，名叫海伦，有一天，有一位将军专门拜访海伦，求教一个百思不得其解的问题：从图中的A地出发，到一条笔直的河边饮马，然后到B地，到河边什么地方饮马，可使他所走的路线全程最短？精通数学、物理学的海伦稍加思索，利用轴对称的知识回答了这个问题。这个问题后来被称为“将军饮马问题”。

2、探究解决问题的方法

问题一：这是一个实际问题，我们首先把它抽象为数学问题，请同学们用自己的语言说明这个问题的意思。

师生活动：学生独立思考后小组交换意见，然后尝试回答，相互补充，最后达成共识，教师根据学生的回答写出问题的板书：如图，已知点A和点B在直线L的同侧，在直线L上找一点C，使AC与BC的和最小。

设计意图：让学生将实际问题抽象为数学问题，即将最短路径问题抽象为“线段和最小问题”。

问题二：由上面的问题我们可以联想到下面的问题：A、B分别是直线L异侧的两点，如何在直线L上找到一点C，使AC与BC的和最小？

师生活动：学生独立思考，画图分析并尝试回答，教师补充。

问题三：对于第一个问题，如何将点B移到L的另一侧，B′处，满足直线L上的任一点C，都保持CB与CB′的长度相等？ 问题四：你能利用轴对称的知识找到符合条件的点B′吗？

师生活动：学生独立考，尝试画图，然后小组交流，学生代表汇报交流成果，师生共同补充：只要作出点B关于直线L的对称点B′，就可以满足CB=CB′,再利用问题二中的方法，连接AB′,则AB′与直线L的交点即为所求。

学生叙述，教师板书并画图，同时学生在练习本上画图。

设计意图：通过搭建台阶，为学生探究问题提供“脚手架”将同侧难以解决的问题提转化为异侧容易解决的问题，渗透转化思想。

3、推理证明“最短”

问题五：你能用所学的知识证明AC+BC最短吗？

师生活动：师生共同分析，然后学生说证明过程，教师板书。

证明：在直线L上任取一点C′（与点C不重合），连接AC′,BC′,B′C′.由轴对称的性质可知，BC=B′C,BC′=B′C′.∴AC+BC=AC+ B′C=AB′, AC′+ BC′= AC′+ B′C′

在△AB′C′中，AB′＜AC′+ B′C′

∴AC+BC＜ AC′+ BC′ 即AC+BC最短。

问题六：这里任取一点C′的作用是什么？

师生活动：学生相互交流，教师适时点拨，最后达成共识：若直线L上任取一点C′与A、B两点的距离之和都大于AC+BC，则说明AC+BC最短。

设计意图：让学生进一步体会做法的正确性，提高逻辑思维能力。

问题七：回顾前面的探究过程，我们是通过怎样的过程、借助什么解决问题的？

师生共同总结：首先作其中一点关于直线的对称点，然后连接另一点与对称点之间的线段，通过轴对称将两条线段和转化到同一条线段上去，这条线段与直线的交点即为所求，整个过程利用了“轴对称”和“两点之间、线段最短“的知识。

设计意图：让学生在反思的过程中，体会轴对称的“桥梁”作用，感悟转化思想，丰富数学活动经验。

4、巩固练习

（1）如图，一艘旅游船从大桥AB的P处前往山脚下的Q处接游客，然后将游客送往河岸BC上，再回到P处，请画出旅游船的最短路径。

师生活动：学生分析解题思路，并相互补充，然后独立完成画图，学生代表上台讲解。基本思路分析：此题中轮船的行走路线共有三段，其中PQ是必经路段，由“两点之间，线段最短”需首先连接PQ，再将河岸BC看成一条直线，这样问题就转化为“点P、Q在直线BC同侧，如何在BC上找一点R，使PR+QR最小”。

设计意图：让学生进一步巩固解决最短路径问题的基本策略和基本方法。

（2）如图，∠XOY内有一点P，在射线OX上找出一点M，在射线OY上找出一点N，使PM+MN+NP最短．

分析：此题的出题背景就是角。本题主要利用了两点之间线段最短的性质通过轴对称图形的性质确定三角形的另两点．

分别以直线OX、OY为对称轴，作点P的对应点P1与P2，连接P1P2交OX于M，交OY于N，则PM+MN+NP最短．

5、课堂小结：教师与学生一起回顾本节课所学主要内容，并请学生回答：（1）本节课研究问题的基本过程是什么？（2）轴对称在所研究的问题中起到什么作用？

浅谈“最短路线”问题 篇3

关键词:最短路线;展开图;总结

中图分类号:G633.6文献标识码:A文章编号:1006-8937(2009)18-0177-01

我们先看下面的问题。例1,问题一:已知圆柱的底面半径为4cm,高为6cm,当蚂蚁从A爬行到B点,蚂蚁爬行最短路线的长度为多少?小明方案:从A到C,再由C到B是最短的,即AC+CB。小亮方案:画出圆柱的侧面展开图,在Rt△ABC中,CB=4 cm,AC=6cm,AB是最短的。你认为谁有道理,请通过计算加以解释。问题二:探究当高度为4cm,其它条件不变时,情况又是怎样呢?这是一个有趣的数学问题。读完题目后,很多同学会有下面的想法:

①有的同学认为:根据“两点之间,线段最短”,连结AB,线段AB即为最短路线,如图1—1。这种想法是错误的。因为蚂蚁是在圆柱体的表面爬行,它不可能按线段AB这个路线爬行。

②有的同学认为:还有一种方案,从A到C,再走弧CB。这也是一条爬行的路线,但是CB=8cm,而弧CB=4 cm,即弧CB>线段CB。因此,这种方案与小明的方案相比,显然小明的方案更符合题意。

③有的同学认为:根据“三角形中任意两边之和大于第三边”,即AC+CB>AB,所以不需通过计算可知,小亮的方案有道理。这种想法也是错误的。因为CB为圆柱的底面直径,而CB为弧CB的长度,即圆柱底面圆周长的一半,因此无法直接比较AC+CB与AB的大小,还需根据已知条件,通过计算得出答案。

问题正确的解答过程如下:

解:(1)依题意可得:

小明所求长度为:AC+CB=6+4×2=6+8=14cm

在Rt△ABC中,根据勾股定理得

小亮所求长度为:AB= cm

∵193.75< =196 ∴AB

∴小亮所选择的路线最短,即蚂蚁爬行最短的路线长度为cm。

(2)依题意可得:AC+CB=4+4×2=12cmAB= cm

∵173.75> =144

∴AB>AC+CB

∴小明所选择的路线最短,即蚂蚁爬行最短的路线长度为12cm。

由问题的解答过程,我们发现:(1)中小亮所选择路线最短,而(2)中小明所选择路线最短。那有的同学会问:这两种路线的长度有可能相等吗?为解决这个问题,我们可以设圆柱的底面半径为r,高为h,当AC+CB=AB时,当 时,AC+CB=AB,即两种路线的长度相等,当 时, AC+CB>AB,即AB是最短的,按小亮所选的路线爬行,当 时, AC+CB

因此,蚂蚁有2条可行的路线,但按哪条路线爬行是最短的,还与题中h、r的取值有关。(注:在解题过程中, 取3.14,取近似值时保留到小数点后两位)

有兴趣的同学可以思考下面的这道题。

例2是一个长方体底座,AB=10m,BC=3m,BF=4m,求一只小甲虫从点A 出发爬到G最短的路径为多少?

分析:本题的关键是画出长方体的展开图,通过分类讨论再比较哪条路径最短。

你是这样想的吗?

解:分3种情况讨论:

(1)将前面与右面展开。

根据“两点之间,线段最短”,连结AG。

在Rt△ACG中,AC=AB+BC=10+ 3=13m,CG=4m,由勾股定理得路径AG= m

(2)将下面与右面展开,连结AG。

在Rt△AFG中,AF=AB+BF=10+ 4=14m,FG=3m,由勾股定理得路径AG= m

(3)将前面与上面展开,如图2—4,连结AG。

在Rt△ABG中,BG=BF+FG=4+ 3=7m,AB=10m,由勾股定理得路径AG= m

∴路径(3)方式爬行的路径最短,即最短的路径为 m。

综上所述,解决这类问题的基本思路为:找出符合题意的路线(可能有2种或2种以上),如果不能直接得出它们长度的大小关系,就通过计算比较,选择路线,得出答案。

参考文献:

[1] 伍鹏.在线课堂,八年级数学[M].上海:龙门书局出版社.

2008.

模糊最短路 篇4

一、利用反射变换

案例1 (1) 如图1, 点E和点D在直线a的两侧, 有一动点P在直线a上运动.问当点P运动到哪个位置时, DP+EP的值最小?在图中找出此时点P的位置.

(2) 如图2, 点E和点D在直线a的同侧, 有一动点P在直线a上运动.问当点P运动到哪个位置时, DP+EP的值最小?在图中找出此时点P的位置.

第 (1) 题只需画出线段DE, 由“两点之间线段最短”可知, 线段DE与直线a的交点, 就是所求动点P的位置.

第 (2) 题, 以直线a为对称轴, 作点D的对称点D', 即可转化为第 (1) 题.这类题目的解题思想, 是利用反射变换把其中的一条线段进行转移, 使之与另一条线段恰好组成一条线段, 然后用公理“两点之间线段最短”加以解决.反射变换的具体操作方法是:以动点所在直线为对称轴, 对其中一个已知点作反射变换.

变式1如图3, 在等边三角形ABC中, 点E是AB的中点, AD是BC边上的高, 点P是线段AD上的一个动点.问点P运动到哪个位置时, BP+EP的值最小?BP+EP的最小值是多少?

本题动点P所在的直线是AD.以直线AD为对称轴, 作出点B或点E的对称点.由于本题作点B的对称点更为简单, 因为点B的对称点就是点C.所以, 我们选点B, 然后连接CE.则CE与AD的交点就是所要找的点P位置.BP+EP的最小值等于线段CE的长.

变式2如图4, 已知⊙O的直径CD为4, 弧AD的度数为60°, 点B是弧AD的中点, 点P是直径CD上的一动点.问:当点P运动到哪个位置时, BP+AP的值最小?BP+AP的最小值是多少?

本题动点P所在的直线是CD.以直线CD为对称轴, 作出点B的对称点B' (也可以作点A的对称点) , 连接AB'.则线段AB'与直径CD的交点, 就是所求动点P的位置.所以BP+AP的最小值就是线段AB'的长.连接OB', 易得△OAB'是等腰直角三角形, 从而可得到线段AB'的长.

变式3如图5, 已知点C是∠AOB内部一点, 点D和点E分别是边OA、OB上的动点.问点D和点E在哪里才能使△CDE的周长最小?在图中, 找出此时点D和点E所在的位置.

本题动点D和动点E所在的直线分别是OA和OB, 故分别以直线OA和OB为对称轴作点C的对称点C''和C', 连接C'C'.那么, 线段C''C'与OA和OB的交点, 就是所要找的点D和点E所在的位置.

变式4如图6, 在平面直角坐标系中, 点A的坐标是 (4, 3) , 点B的坐标是 (4, 1) , 点M是y轴上的一个动点, 点N是x轴上的一个动点.当四边形AMNB的周长最小时, 求直线MN的解析式.

四边形AMNB的周长由AM、MN、NB、BA四条线段的长短来决定, 其中BA是固定不变的.四边形AMNB的周长最小, 则AM+MN+NB的值应为最小.由此, 本题可转化变式3题型, 变式3是变式4点A、B重合时的特殊情形.分别作点A关于y轴的对称点A', 作点B关于x轴的对称点B', 连接A'B'.那么, 线段A'B'与y轴和x轴的交点, 就是所动点M和动点N所在的位置.易知, 点A'的坐标是 (-4, 3) , 点B'的坐标是 (4, -1) .从而可求得直线MN的解析式是y=-0.5x+1.

二、利用平移变换

案例2如图7, 城市A和城市B坐落在河两岸.现在, 要在这条河上架一座桥 (桥通常与河岸垂直) , 开通城市A和城市B之间的城际公路.请设计一种方案, 使城市A和城市B之间公路路程最短.

因为本题中桥的长度是不变的, 所以要使城市A和城市B之间路程最短, 只要使岸上的公路路程最短即可.而岸上的公路路程与河的宽度无关.不妨假设河的宽度为零, 即把直线b和点B进行平移, 使直线b与直线a重合, 假设点B平移后为点B'.这样, 岸上公路的最短路程就等于点A和点B'之间的最短路程.

本题的方案设计如下:把点B沿与直线a垂直的方向 (往河岸方向) 平移到点B', 画线段AB', AB'交直线a于点M, 过点M作平行线间的垂线段MN.那么, 垂线段MN就是所要架桥的位置.

变式1如图8, 已知:点A的坐标是 (0, 2) , 点B的坐标是 (4, 5) , MN为x轴上的一条动线段, 且MN=2.当四边形AMNB的周长最小时, 求点M、N的坐标.

因为线段AB和MN的长度是不变的, 所以要使四边形AMNB的周长最小, 只要使AM+BN的值最小即可.这问题可通过平移点B或点A, 转化为案例1中的第 (2) 题的题型, 而加以解决.方法如下:把点B向左平移2个单位长度至B', 作出点A关于x轴的对称点A', 连接A'B', 则线段A'B'与x轴的交点就是点M.易得点A'的坐标是 (0, -2) , 点B'的坐标是 (2, 5) .可用待定系数法求得直线A'B'的解析式, 再求得点M、N的坐标.

三、利用表面展开

案例3如图9, 有一长方体的纸盒, 长、宽、高分别是5cm、4cm、3cm, 在纸盒的A处有一只蚂蚁, 在B处有一粒蜜糖.蚂蚁想吃到蜜糖, 所走的最短路程是多少cm?

本题只要将蚂蚁所经过的面展开, 根据两点之间线段最短, 可求得从A到B的最短路程.由题意可知, 本题有三种不同的行走路径:如图10,

变式1如图11, 圆锥的底面半径是1cm, 母线长是3cm, 在底面圆周A处有一只蚂蚁.这只蚂蚁从点A出发, 绕侧面爬行一圈回到点A, 所走的最短路程是多少cm?

沿着过点A的母线把圆锥侧面展开, 如图12, 蚂蚁所走的最短路径就是线段AA'.

∵圆锥的底面周长等于侧面展开图扇形的弧长

变式2如图13, 四边形ABCD是圆柱的轴截面图.圆柱的底面半径是1cm, 母线长是3cm.

(1) 蚂蚁从点A出发, 绕侧面爬行一圈到点D, 所走的最短路程是多少cm?

(2) 蚂蚁从点A出发, 绕侧面爬行二圈到点D, 所走的最短路程是多少cm?

(3) 蚂蚁从点A出发, 绕侧面至少爬行一圈到点C, 所走的最短路程是多少cm?

第 (1) 题, 沿着母线AD把圆柱侧面展开, 如图14, 线段AD'的长就是所走的最短路程.

第 (2) 题, 沿着母线AD把圆柱的侧面展开, 如图15, 取线段AD和A'D'的中点E、E', AE'+ED'的值就是所走的最短路程.因为, 把矩形DEE'D'沿着直线DD'平移, 使点D到D'处, 如图16, 只有E、E'为中点时, 线段AE'、ED'才能组成线段, 其他情况均为折线.

导航最短路径查询个人总结 篇5

2013110410 云丹久美

这次实践，我们小组通过一个具体的程序实践项目——导航最短路径查询，巩固了已经学习的数据结构知识。例如，对一维数组，二维数组，文件的读写，循环菜单等的巩固。让我对这个专业，这个学科也有些新的认识和更深一个层次的理解。与此同时，也让我以前不懂或是不牢固的知识在实践之中进一步的掌握了。比如我以前一直不懂动态数组的使用，这次通过这个项目的实践掌握了动态二维数组的知识。

除此之外，程序实践课程的学习也大大提高了我的应用能力，如问题分析能力，编码调试能力，团队合作能力等等。

以前刚开始学习数据结构的时候，真的不知道该怎么样才能学好它。也不知道它到底是干什么的。只是一味的认为上课跟着老师走就能把它学的很好。可是学到最后才发现其实学习编程并不是像学习理论知识那样靠死记硬背，它需要的是我们分析问题的能力和想出解决办法的思维。一些错误的思维方式可能会导致整个程序无法正确执行。在当我们被需要写一个程序时，要考虑到所有的可能性，最后从这些可能性里选择最好的解决方法。这样，数据结构提高了我们对待问题的正确思维能力。

老师为我们提供了独立思考的条件，也在上课期间为我们辛勤指导，让我们自己编代码，写程序并调试结果。通过这一过程，编码调试的能力有了些提高。来自软件公司专业的老师也让我们意识到遵守良好的编码格式，工整的编码结构很重要。

在一个小组中，每个人承担不同的功能模块。最后由小组长把这些子模快连接起来。在完成这个系统的过程中我们彼此讨论着要怎么样才能把这个功能模块做出来。团队可以让我们把彼此的想法汇总到一起，然后从每个人的理解角度来分析每个问题的错误原因。让我明白了在软件开发的过程中一个团队的重要性。当然，我也在此次的过程中认识到了自己的不足。在一开始分析数据的时候，看着这么多复杂的数据顿时觉得毫无头绪，代码调试中遇到错误时也是焦头烂额，还是会有畏难情绪的存在，需要今后大量的代码编写练习去克服。

通过这次为期7天的程序实践课程的学习，我收获了很多，也认识到了自身的不足。

两种最短路径算法的比较 篇6

最短路径是最优化重要问题之一,它不仅直接应用于解决生产实践中的许多问题,如管道的铺设、线路的安排、厂区的选址和布局、设备的更新等。而且也经常被作为一种基本工具,用于解决其他的最优化问题和预测、决策问题。[1]

所谓最短路径问题,就是给定一个赋权有向图。即给了一个有向图D=(V,E),对每一个弧a=(vi,vj),相应地有权重w(a)=wij。又给定D中的两个顶点vs,vt。设P是D中从vs到vt的一条路径,定义路径P的权是P中所有弧的权之和,记为w(P)。最短路径就是要在所有从vs到vt的路中,求一条权重最小的路径,即求一条从vs到vt的路径P0,使w(P0)=Min(w(P0))[2]。

应该注意的是:这里所说的最短路径问题是广义的最短路径。即图中边的权重不一定是仅指两点之间的距离。在经济活动中,它的含义很丰富,比如可表示收益、成本等。因此有向图中边的权重不一定都是大于或等于零,它也可能是小于零的数。关于最短路径算法的研究,目前已有很多的算法,但它们基本上都是以Dijkstra算法、Floyd算法这两种算法为基础。因此有必要对Dijkstra算法、Floyd算法作本质的研究。

2 基本思想的比较

(1)Dijkstra算法的基本思想是:以vs为起点,从图中找出与其距离最短的顶点。假设该点为vi,然后再以vi作为参照点,从余下的顶点中找出与其距离最短的顶点,依次类推。直到所有的顶点都对比完为止。至止,vs到各顶点的最短距离就已经求出来了。至于具体的最短路径,常用的方法是“反向追踪法”。即从终点出发,“顺藤摸瓜”找到最短距离上的各个点,按照有向图的方向,就可以得到最短路径。

(2)Floyd算法的基本思想是:从vs到vt的最短路径是以下各种可能路径中的长度最小的那条。[3,4]

若存在,则存在路径{vs,vt}。(路径中不含有其它顶点)

若,存在,则存在路径{vs,v1,vt}。(路径中所含顶点序号不大于1)

若,存在,则存在一条最短路径{vs,…v2…vj}。(路径中所含顶点序号不大于2)

依次类推,则vs到vt的最短路径应是上述这些路径中路径长度最小者。

两种算法的基本思想不同,导致了两种算法结果的不同。对于Dijkstra算法而言,其结果是可求出从某一个顶点到其余各顶点的最短路径。而Floyd算法的结果是可以得出图中任意两对顶点之间的最短路径。而且由于基本思想不同,它们的算法也大相径庭。下面给出它们算法的具体步骤:

3 算法步骤的比较

3.1 Dijkstra算法的步骤

从Dijkstra算法的基本思想可以得出其算法的步骤如下:

Step1:初始化:把图中的顶点集V分为两个集合V1和V2,且两个集合的交为空集。令V1={vs},P(vs)=0,其他顶点归属于v2,且T(vj)=+∞。

Step2:当V1≠V时,反复按如下进行:

(1)对vj∈V2,若T(vj)>P(vi)+wij,则T(vj)=P(vi)+wij,否则转向(2)。

(2)令T(vj0)=Min(T(vj1),T(vj2),…T(vj))。若这样的j0有两个以上,则可任选一个。

(3)令P(vj0)=T(vj0),将vj0的T标号变成P标号,并令i=i+1。

Step3:当V1=V时,整个计算过程终止。此时每个vj∈V1,dsj=P(vj),再用“反向追踪”方法求出具体的最短路径。

3.2 Floyd算法的步骤

从Floyd算法的基本思想可以得出其算法的步骤如下:

Step1:初始化距离矩阵D(0)=(dij(0))、序号矩阵S(0)=(sij(0))和执行次数变量k的值。其中距离矩阵D(0)和序号矩阵S(0)分别定义为:

若vi邻接到vj,则dij(0)=wij;否则dij(0)=∞。

sij(0)=j(i,j=1,2…n),即元素sij(0)的值等于它所在的列数。图中顶点的个数为n。

k=1

Step2:当k≤n时,D(k)中第k行与第k列元素保持与D(k-1)的相应元素相同。其他元素按下式进行计算:

dij(k)=Min(dij(k-1),dik(k-1)+dkj(k-1))

序号矩阵S(0)的元素取值规则为:

若dij(k)=dij(k-1),则sij(k)=sij(k-1);若dij(k)

经过计算,若dii(k)<0,则结束整个过程的计算。说明图中存在一条含有顶点vi的负回路,由序号矩阵中的sij(k)可以找出此回路,否则k=k+1,再执行Step2。

Step3:当k=n时,终止整个过程的计算。若dii(k)=+∞,则说明D中不存在从vs到vt的最短路径;否则dij(k)的值就是vi到vj的最短距离。其相应的路径可由序号矩阵中的sik(k)找出。(i,j=1,2…n)

从以上介绍的具体算法中可以看出:Floyd算法是从邻接矩阵出发,而且最短路径可以从序号矩阵中找出来。最短路径的权值从距离矩阵中得出。

3.3 相关程序

如果从算法的基本思想及具体的步骤来看,Dijktra算法比Floyd算法更通俗易懂些,也更易于掌握些。而Floyd算法则不具有这些优点,但Floyd算法也有它强劲的优势。即它除了能求出图中任意两对顶点的最短距离和最短路径外。对于用计算机来实现,它比Dijkstra算法更容易实现多。Floyd算法的编程,用任何一门语言均可实现,如用最基本VB、VF都能实现。而Dijkstra算法的编程,非VB、VF能解决,它需要用c++或者其他更高级的语言。这就要求使用者有相当高的编程能力。

下面给出用VB编写的floyd算法关键部分的程序[5]:

该算法的时间复杂性为O(n3+n2)。

因Dijkstra算法的程序用VB难以实现,故在此不能出。但从它的具体步骤可以看出它的时间复杂度为2n(n-1)。

尽管Floyd算法的时间复杂性与储蓄空间都比Dijkstra算法的大,但就今天的计算机性能而言,这已不值一提了。作为用户来说,在选择算法时,除了考虑所求问题的要求外,还要考虑自己的编程能力。

前面已提到最短路径问题是广义的最短路径,因此在许多情况下,图中的权重可能是负值。Dijkstra算法要求每一个权重必须大于或等于零,这是该算法的最大局限。为了弥补Dijkstra算法的不足,近年来,已出现Dijkstra算法的改进版。即在出现负值的权重时,用另外一种Dijkstra算法[1]。现介绍如下:

为方便起见,不妨设任两点vi、vj都有一条边。如果两个顶点之间没有边,则给它们添加一条边,并令wij=+∞。从vs到vj的最短路径总是从vs出发,沿着一条路到某个点vi,再沿(vi,vj)到vj,从vs到vj的这条路是从vs到vj的最短路径,因此d(vi,vj)必须满足如下方程:

d(vi,vj)=Min(d(vi,vj)+wij)i变化

为求解上面的方程,可用如下公式进行计算:

开始时,令d(1)(vs,vj)=wsj,当t=2,3…n时,d(t)(vi,vj)=Min(d(t-1)(vs,vi)+wij),j=1,2…n。

若进行到某一步,比如是第k步,对所有j=1,2…n,有d(k)(vs,vj)=d(k-1)(vs,vj),则{d(k)(vs,vj)},j=1,2…n,即为从vs到各点的最短距离。

4 结束语

在优化、预测与决策中,最短路径是常常遇到的。它也是这两个研究方向中的一个重要问题之一。有关它的求解方法,目前已有多种方法,但那些方法都是以D算法或F算法为基础,在此基础上进行一些改进。本质上不同的算法目前尚未出现。作这普通用户来说,因D算法和F算法各有千秋,在决定选择方法时,应注意它们的差异和要求。

参考文献

[1]《运筹学》教材编写组.运筹学[M].清华大学出版社,2006.7.

[2]程理民,吴江,张玉林.运筹学模型与方法教程[M].清华大学出版社,2005(9).

[3]李洪波,王茂波.Floyd最短路径算法的动态优化[M].计算机工程与应用,2006(34):61.

[4]王苏男.最短路径算法的比较[M].系统工程与电子技术,1994(5):43-49.

平面图形中的最短路径 篇7

解决这类题的基本方法是:先考察点或线段的特殊位置和极端位置, 从而确定最小值的具体数值, 再进行一般情形下的推理论证. 下面, 我们就以具体的例子来说明解决这类题的方法与规律.

例1在直角梯 形ABCD中, ∠ABC = 90°, AD∥BC, AD = 4, AB = 5, BC = 6, 点P是AB上一个动点. 当PC + PD的和最小时, PB的长为 ( ) .

A. 1B. 2C. 2.5D. 3

分析此题首先要确定P点的位置, 可以延长CB (或DA) 至一倍, 即CB = BM, 再连接MD交AB于P (大家可以思考一下P点的正确性与合理性———可运用两点之间, 线段最短这一性质) . 我们可以通过△MPB∽△DPA, 从而求出PB的长. 故选D.

总结已知两定点与一直线, 欲在直线上取一点, 使该点到两定点的距离和最小. 这题可分两类: 一类是当两点在该直线的两侧时, 可连接这两点, 则连线与该直线的交点, 即是所要求的点, 根据是两点之间, 线段最短. 当两点在该直线的同侧时, 可先找任一定点关于该直线的对称点, 再连接对称点与另一定点, 其连接线与该直线的交点就是要求的点. 同样, 我们也可以用上述依据加以说明.

例2如图2, △ABC中, AB = AC =13, BC = 10, AD是BC边上的中线, F为AD上的动点 , E为AC边上的动 点 , 则CF + EF的最小值为 _______.

分析显然, 这一题需要确定两个动点E和F, 那么, 怎样确定这两个点呢?我们可以过点B作BE⊥AC交AD于F, 从而确定了E和F点 (大家可以用从直线外一点与直线上所有点的连线中, 垂线段最短来加以说明) . 此时, CF + EF = BE, 用构造方程, 求出BE =120/ 13 , 即CF + EF的最小值为120 /13 .

总结本题可理解为特殊图形的最短距离问题, 看似两个动点难以把握, 但我们只要考虑其特殊的位置, 就不难想到这条特殊的线了. 此题中, 点C到AD上任意一点O的距离总是等于B点到点O的距离, 而O到AC的最短距离是点O到AC的垂线段的长度, 当这两线段成一条线段时, 便是最短的距离了, 从而得出BE就是最短的距离.

例3如图3, 已知平面直角坐标系中, A (2, -3) , B (4, -1) .

(1) 若C, D是x轴上的两 个动点 , 且D (a, 0) , CD = 3, 当四边形ABCD的周长最短时, 求a的值.

(2) 设M, N分别为x轴、y轴上的动 点 , 问 :是否存在 这样的点M (m, 0) 和N (0, n) , 使得四边形ABMN的周长最短? 若存在, 求出m, n的值;若不存在, 请说明理由.

分析 (1) 如图3, 过A点作x轴的平行线, 并截取AA1 = 3, 画A1 关于x轴的对称点A2 , 连接A2 B交x轴于点C, 再在x轴上截取CD = 3, 可得周长最短的四边形ABCD (大家也可以利用两点之间, 线段最短, 来证明最短周长的正确性) . 由题意可知, A2 (5, 3) , 设A2 B的直线解析式为y=k2 x + b2 , 将A2 (5, 3) , B (4, -1) 代入 , 得解之得即当 y = 0 时, x =17/ 4 , a =17/ 4 - 3 =5/ 4 .

(2) 如图4, 我们可以先 分别找出A, B关于y轴和x轴的对称点A1 和B1 , 再连接A1 B1 , 分别交x轴和y轴于M与N, 此时 , 四边形ABMN的周长是 最短的 (同样, 可以用两点之间, 线段最短来加以证明) . 设A1 B1的直线解析式为y = k3 x + b3 , 将A1 (-2, -3) , B1 (4, 1) 代入, 得解得即

当 x = 0 时, y = -5 /3 , 当 y = 0 时, x =5 /2 .

所以, m, n的值分别为5/ 2 , -5/ 3 .

总结此题的两个问题分别是两种最短距离的问题, 第一小题是在直线上取一条定线段使得两端点与直线同侧的两定点构成的四边形周长最短, 这类题可转化为求这个四边形的一组变化对边的和的最小值, 可通过平行四边形的对边相等进行线段的平移, 再利用对称性, 找出变化两边和的最小值, 从而得周长最小的四边形;第二小题是在角的两条边上各找一点, 使得其与该角内的两个定点所构成的四边形的周长最小. 此题的思路是如何使变化的三条边的和最小, 我们只需要将变化的三条边能组成一条线段, 便可利用“两点之间线段最短”得出结论.

总之, 在解题中充分利用图形的翻折变换、平移变换和旋转变换, 化曲为直, 使分散的条件加以集中, 为性质的运用创造条件, 从而达到解决问题的目的.

摘要：“两点之间, 线段最短”;“直线外一点与直线上所有点的连线中, 垂线段最短”.解题时可先考察点或线段的特殊位置和极端位置, 从而确定最小值的具体数值, 再进行一般情形下的推理论证.在解题中充分利用图形的翻折变换、平移变换和旋转变换, 化曲为直, 使分散的条件加以集中, 为性质的运用创造条件, 从而达到解决问题的目的.

浅谈蚂蚁爬行的最短路程 篇8

一、蚂蚁在“圆柱”上爬行

例1如图1所示, 有一个底面半径为2cm, 高为5cm的圆柱, 在圆柱下底面的A点有一只蚂蚁, 它想吃到上底面与A点相对的B点处的食物, 它需要爬行的最短路程是多少? (π取3)

分析:若在圆柱的侧面上爬行, 则毫无疑问是将其侧面展开, 得到如图2所示的矩形, 点B是矩形边的中点, 根据“两点之间, 线段最短”和勾股定理可得:

即蚂蚁爬行的最短路程约为71cm.

但是, 当蚂蚁是在此圆柱的表面上爬行时, 我们还要考虑, 在图1中, 蚂蚁从A爬到C, 再到B的这条路径, 蚂蚁若沿这条路径爬行时, 它爬行的路程为:5+4=9cm,

因为, 所以蚂蚁在圆柱表面上爬行的最短路程是

有同学可能会问, 没必要考虑图1中的这种路径, 一定是展开图 (图2) 中的这种路径最短。如果你有这种想法那就错了。不信, 我们现在将该圆柱的底面半径保持不变, 高变为2cm, 此时, 沿图1的路径走, 所走的路程为:2+4=6cm.

若沿图2所示展开图的路径走, 所走的路程为:

所以此时蚂蚁所走的最短路程是6cm.

其实, 细心的同学会注意到, 当圆柱的底面半径不变, 高由大变小时, 两种路径的差值在逐渐缩小。那么, 圆柱的底面半径和高有什么关系时, 两种路径一样?或者选择哪种路径走更短呢?我们不妨假设图1中圆柱底面半径为r, 高为h.

设AB=xcm, A—C—B路径的长为ycm,

(1) 当x=y时,

因为r>0, 所以 (π2-4) r=4h,

解得:h=4π2-4r;

(2) 当x>y时,

因为4r>0, 所以

(3) 当x

因为4r>0, 所以

由上可知, 当时沿AB和沿A—C—B爬行的路程一样;当时, 沿A—C—B爬行的路程最短;当时, 沿AB爬行的路程最短。

点评:探索“蚂蚁在圆柱上爬行”, 要考虑两种爬行, 进行比较才能得出结论, 通俗讲, “瘦高型”圆柱优先考虑展开图爬行, “矮胖型”圆柱优先考虑沿A—C—B爬行。

二、蚂蚁在“棱柱”上爬行

例如图所示有一个长方形的盒子它的长宽高分别为20cm、30cm、10cm, 在盒子的A处有一只蚂蚁, 它想吃到B处的食物, 那么它爬行的最短路程是多少?

分析:通过上面的例子不难想到, 要走的路程最短, 只需将此长方体展开成一个平面即可。但由于长方体的展开图有很多种, 到底要选择哪一种展开图计算才是最短的呢?下面我们一起探讨探讨。

由于点A是在此长方体的前、下、左三个面上。而点B在上、后、右三个面上, 因此, 只需将与A、B有关并且相连的两个面展开即可。列表如下:

从表格中可以看出有六种展开图, 但是细心的同学会发现, (前, 上) 与 (下, 后) , (前, 右) 与 (左, 后) , (下, 右) 与 (左, 上) 的展开图分别是一样的, 最后得到蚂蚁在此长方体上爬行时, 展开图应该只有三种。分别如下:

从而, 比较三种展开图得到蚂蚁爬行的最短路程:

点评:此类问题的基本思路是“化折为直”, 把空间问题转化为平面问题解决。通常情况下, 若一个长方体的长、宽、高分别为a、b、c (a>b>c>0) 时, 三种展开图中, 最短路程为.如本题中, 因为30>20>10, 所以蚂蚁所走的最短路程为同学们也可以去找一些例子进行验证。

运用“轴对称”解决最短路径问题 篇9

在苏科版八(上)“轴对称图形”一章的课后习题中就有这样一个问题:如图1,点A、B在直线l同侧,点B′是点B关于l的对称点,AB′交l于点P.(1)AB′与AP+PB相等吗?为什么?(2)在l上再取一点Q,并连接AQ和QB,比较AQ+QB与AP+PB的大小,并说明理由.

【解析】(1)由点B与点B′关于直线l成轴对称可知PB=PB′,则AB′=AP+PB′=AP+PB. (2)利用“三角形任意两边之和大于第三边”及(1)的结论可知,AQ+QB>AB′=AP+PB.

这个问题还可以进一步说明直线l上的点P能使得线段PA+PB的和最小.

下面再通过对几个最短路径问题的分析,帮助同学们熟悉并掌握这类问题的解题策略,真正能做到融会贯通,一通百通.

一、已知两点在一条直线的同一侧

例1 (将军饮马)古希腊一位将军要从A地出发到河边(如下图MN)去饮马,然后再回到驻地B. 问怎样选择饮马地点P,才能使路程最短?

【解析】先确定点A或点B中一个点关于直线MN的对称点,然后连接对称点和另一个点,与直线MN的交点P即为所求的点.

【变式训练】已知点P、Q是△ABC的边AB、AC上的点,你能在BC上确定一点R,使△PQR的周长最短吗?

【点拨】△PQR的周长等于PQ+PR+QR,因为PQ的长度不变,所以只要线段PR+QR的和最小,就能使△PQR的周长最短.

二、已知一点在两条相交直线的内部

例2如图5,OA、OB是两条相交的公路,点P是一个邮电所,现想在OA、OB上各设立一个投递点,要想使邮递员每次投递路程最近,问投递点应设在何处?

【解析】如图6,点P1、P2分别是点P关于直线OA、OB的对称点. 由轴对称的性质可知:PM=P1M,PN=P2N,因此邮递员每次投递的路程就等于P1M+MN+P2N=P1P2,所以当投递点分别设立在OA、OB上点M、N处时,邮递员每次投递路程最近.

【变式训练】如图7,已知∠AOB内有一点P,试分别在边OA和OB上各找一点E、F,使得△PEF的周长最小,不需说明理由.

【点拨】分别作点P关于OA、OB的对称点P1、P2,P1P2分别交OA、OB于点E、F,由轴对称的性质可知:PE=P1E,PF=P2F,即得△PEF的周长等于P1P2,此时△PEF的周长最小.

三、已知两点在两条相交直线的内部

例3某中学八(1)班的班会课上,桌子摆成如图8所示两直排(图中的OA、OB),OA桌面上摆满了苹果,OB桌面上摆满了糖果,站在C处的学生小明先拿苹果再拿糖果,然后到D处座位上,请你帮助他设计一条行走路线,使其所走的总路程最短.

【解析】如图9,作C点关于OA的对称点C1,作D点关于OB的对称点D1;连接C1D1,分别交OA、OB于点P、Q,则由轴对称的性质得:CP+PQ+QD=C1P+PQ+QD1=C1D1. 故小明沿C→P→Q→D的路线行走,所走的总路程最短.

【变式训练】已知∠MON内两点A、B,请你在OM、ON上分别找一点C、D,使得AC+CD+BD+AB最短.

【点拨】分别作点A、B关于OM、ON的对称点A1、B1,连接A1B1,分别交OM、ON于点C、D,即得点C、D就是所求的两点.

网络图形最短路径算法分析与研究 篇10

目前,在求网络图形最短路径的问题上主要有四种算法,它们是Dijkstra算法、逐次逼近算法、矩阵算法、Floyed算法,它们分别出现在数据结构、运筹学、图论等课程中。其中前两种算法都是求图上从某一点至另一点的最短路径,而后两种算法是求出网络图上所有节点之间的最短路径。由于这些算法分别出现不同的学科课程中,因此人们不易将它们进行统一的归纳总结与分析比较。

Dijkstra算法与逐次逼近算法解决的是从某一个节点到另一节点之间的最短路径问题,算法的时间复杂度是O(n2)。如果想得到每一对节点之间的最短路径,则需要多次调用算法进行计算。显然,这种方式对于求网络图中每一对节点之间的最短距离就显得过于麻烦。

矩阵算法与Floyed算法较好地解决了这方面的问题,它可以通过算法的一次调用直接计算出网络中每一对节点之间的最短路径值,因而弥补了前两种算法在这方面的不足。它们通过一个图的权值矩阵求出每两点间的最短路径矩阵。从图的带权邻接矩阵A=[a(i,j)]n×n开始,逐渐扩展,最终找到所有节点间的最短路径。矩阵算法与Floyed算法的时间复杂度是O(n3)。

事实上,许多人混淆了后两种算法,认为它们是同一个算法,原因是它们不但功能相同,而且都是采用矩阵运算的形式进行最短路径的求解。其实,它们在处理方法上还是有很大区别的,在此基础上分析它们的附加功能也是不同的。本文将着重对这两种算法进行分析与讨论,以求在实际应用中对读者起到参考借鉴的作用。

2. 矩阵算法与Floyed算法的分析与研究

2.1 两种算法的说明

2.1.1 矩阵算法

矩阵算法的主要思想是首先构造初始距离矩阵,然后进行逐次迭代。首先进行第一次迭代,求出网络图中任意两个节点之间最多经过1个中间节点的最短距离;再进行第二次迭代,求出任意两个节点之间最多经过3个中间节点的最短距离;如此进行直至第k次迭代,求出任意两个节点间最多经过(2k-1)个中间节点的最短距离或当相邻两次迭代结果相同的时候停止迭代过程。

具体步骤:

(1)首先构造距离矩阵Dn×n(以距离为权的权值矩阵)。矩阵给出了所有节点之间只经过一步(一条边)的最短距离。

(2)设置途经的节点路径矩阵Rn×n内的所有元素rij(i,j=1…n)均为空字符。

(3)对距离矩阵进行如下的迭代运算:

(第一次迭代r=1,以后逐次加1。)

式中:

n----网络节点数;

D(0)为初始的距离矩阵;

*----矩阵逻辑运算符,dij=min[dik+dkj](k=1,2,3,…,n)。dik,dkj----距离矩阵D(r-1)中的元素,分别为上次迭代后节点i、k之间、节点k、j之间的最短距离。dij为本次迭代后节点i,j之间经过k节点的最短距离(k=1,2,3,…,n)。

(4)保存本次迭代当前最短路径的途径节点序列。具体方法是:

如果本次迭代计算出的当前最短路径为dij=dik+dkj,则进行下面的操作:

如果为第一次迭代则令rij=“i k j”,否则,则令rij=rik&rkj(其中符号“&”为字符串连接运算符)。

(5)重复第(3)--(4)步操作,直至第k次迭代(k的值满足或者满足D(r+1)=D(r)。

(6)最终得到任意两点间的最短路径值及其相应途经的节点序列。

此算法适用于所有无向图与有向图。

本人为此编制了程序以解释其原理。用以下有向图实例(如图1所示)来加以说明:

(1)定义图形

如图2所示,其中表格内的数值表示两点间的权值,空位置处表明两点之间没有直接路径。

(2)生成网络图形邻接矩阵(如表1所示)

(3)第一次迭代

第一次迭代的结果是两个节点之间最多跨接1个节点(如表2所示)。

注:其中“∞(n,m)”表示从n点到m点之间的距离为∞,以下相同。

(4)第二次迭代

第二次迭代的结果是两个节点之间最多跨接3个节点(如表3所示)。

(5)第三次迭代

第三次迭代的结果是两个节点之间最多跨接5个节点。在本例中本次迭代与上次结果相同(如表3所示),此矩阵内存储的数据即为最终结果,迭代过程就此结束。

2.1.2 Floyed算法

具体算法描述:

{da.cost为带权有向图的邻接矩阵,length[i,j]为从vi到vj的最短路径的长度,path[i,j]为相应的最短路径}

Floyed算法的目的是求出具有n个节点的图中每一对节点之间的最短路径。算法思想是:

假设求节点vi到vj的最短路径。如果从vi到vj有弧,则从vi到vj存在一条长度为cost[i,j]的路径,该路径不一定是最短路径,尚需进行n次试探。

首先考虑路径(vi,v1,vj)是否存在(即判别弧(vi,v1)和(v1,vi)是否存在)。如果存在,则比较(vi,vj)和(vi,v1,vj)的路径长度取长度,较短者为从vi到vj的中间节点的序号不大于1的最短路径。

在此基础上再考虑增加一个节点v2,也就是说,如果(vi,…,v2)和(v2,…vj)分别是当前找到的中间节点的序号不大于1的最短路径,那么(vi,…,v2,…vj)就有可能是从vi到vj的中间顶点的序号不大于2的最短路径。将vi与vj之间所有中间节点的序号不大于2的最短路径和中间节点的序号不大于1的最短路径进行比较,选出最短的路径,从而得到中间节点序号不大于2的最短路径。

在此基础上再考虑增加一个节点v3,继续进行试探,从而得到vi与vj之间的中间节点序号不大于2的最短路径。

以此类推,直到增加最后一个节点,找到vi与vj之间的中间节点序号不大于n的最短路径。

按此方法,可以同时求得各对节点间的最短路径。

现通过一个实例结合本人用此算法的编制的程序说明其处理过程。此算法本应三重循环一气呵成,但是为了演示并说明处理过程,特在程序中设置了间断点,以方便理解算法的原理。

演示步骤(篇幅所限,用图表表示):

(1)输入两点之间的权值(距离)(见图1);

(2)生成邻接矩阵(见图2);

(3)处理序号为1的节点,结果如表5所示。

(4)依次处理序号为2、3、4、5的节点。由于篇幅所限,仅列出5号节点处理后的结果如表6所示。

至此,图中每一对节点之间的最短路径全部找到。

2.2 两种算法的联系与区别研究

(1)两种算法的相同点

两种算法均采用邻接矩阵的方式来存储原始权值、中间结果及最终结果,在寻找最短路径的过程中都采用对矩阵内数据元素进行算术及逻辑运算,从跨接1个节点的路径开始逐步扩展,最终得到所有结点之间最短路径的结果,两种算法的时间复杂度均为O(n3)

(2)两种算法的处理方法不同

矩阵算法在寻找最短路径过程中采用逐步迭代的方式进行,每次迭代可以找到任意两点间跨接的节点个数在限定范围内的最短路径。通过每次迭代最多跨接2k-1个节点(其中k为迭代的次数)的递增顺序,逐步求得两点之间的最短路径。这种算法在迭代的过程中不强调节点的顺序,而主要把精力聚焦在跨接节点的个数上,随着迭代次数的增加,跨接的节点数随之增加,直到跨接的节点数达到可能的最大值,至此最短路径全部找到。

Floyed算法在寻找最短路径的过程中采用三重循环的方式进行,运算过程依赖于节点的序号,即先计算跨接1号节点的所有当前最短路径,再在此基础上查询跨接2号节点的当前最短路径,以此类推,最终找到跨接最后一个节点的最短路径,至此找到所有最短路径结果。

两种算法虽然处理方式不同,但实践证明都是科学有效的方法。

(3)探讨两种算法的附加功能

根据上述的分析可见,矩阵算法在寻找最短路径过程中,第k次迭代的结果是得到最多跨接2k-1个节点(其中k为迭代的第次数)的最短路径,逐步迭代后最终求所有节点间的最短路径。这样做的好处是处理过程清晰明确,而且具有实用价值。例如:在公交运行查询中,乘客可以找到最多换乘n次车的最短路径。对于乘客来说,两地之间的最短路径并不意味着最方便,顾客往往希望尽量少换车次但路径尽可能短的情况。例如从A地到B地有几种走法,第一种走法是只乘1辆车即可到达终点,汽车共行驶20km;第二种走法是中途换乘1次车,汽车最短行使15km;第三种走法是中途换乘3次车,汽车最短行驶12km。年老体弱的人可能选择第一种方法,年轻人可能选择第二或第三种方法。因为换乘次数少而且距离相对较短,所以大多数人会舍弃距离更短的第三种走法而选择第二种走法。运用矩阵算法可以通过逐次迭代过程的中间结果告知乘客换乘的次数及相应的最短路径,以此方便乘客在乘车距离与换乘次数之间进行平衡。又例如在货物运输过程中,运输公司往往要在时间与距离两个方面寻找平衡点,有些路段虽然距离近但路面质量低或道路拥堵造成耗时多,而有些路段虽然距离远但行驶顺畅耗时少,针对这种情况,矩阵算法可以向运输公司提供多种路径选择方式,以更为人性化的方式提供交通信息服务。

Floyed算法在寻找最短路径的过程中采用三重循环的方式进行,运算过程依赖于节点的序号。这种方法程序实现起来容易,但是处理过程相对来讲没有运筹学的矩阵算法清晰,中间处理结果没有什么实用价值,因而几乎没有可以应用的附加功能。

(4)矩阵算法在数学解释方面有助于对Floyed算法的理解

矩阵算法采用数学中矩阵运算的方式进行最短路径的查找,逻辑清晰、推理严密,使人一目了然。

Floyed算法采用三重循环结构逐个节点递进的方式完成最短路径的查找,虽然在数学方法的支撑与论证方面有些欠缺,但通过对实际问题的分析与逻辑判断,迄今为止此算法仍然是科学有效的经典算法。同时,矩阵算法在数学解释方面有助于加深对Floyed算法的理解。

总之,最短路径问题可以采用不同的算法来解决,这些算法各有区别、各具千秋,在实际应用的过程中要结合需求选择恰当的算法,以求实用、高效、快捷。

参考文献

[1]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,1987.

[2]胡运权.运筹学基础及其应用[M].北京:高教出版社,2004.

[3]张炯民,窦亮,黄国兴.数据结构与算法教程[M].上海:华东师范大学出版社,2007.