最短路问题（精选12篇）
最短路问题 篇1
0引言
在公交网络的查询系统中, 需要查询两站点之间最节省的乘车方式。该问题可以转化为求解交通网络中两点之间的最短路问题。目前的最短路问题的算法[1,2,3,4,5,6,7,8,9]均来源于Bellman方程, 其中有Dijkstra算法、Ford算法、Floyd算法以及标号修正法等。对于正权网络, Dijkstra算法是公认的有效算法。Dijkstra算法用于解决公交网络的查询系统无疑是最佳的选择 (当然根据公交问题的特点要改进Dijkstra算法) 。但是, 在计算过程中, Dijkstra算法需要始终对每个站点进行迭代, 针对规模庞大且稀松的公交系统网络, 这种计算方式显得效率较低。因此, 需要寻找一种新的算法来解决公交系统的最短路问题, 该算法应该在迭代过程中只调用离起点较近的站点的信息, 而不管离起点较远的站点也能计算出到达终点的最短路。我们根据线性规划的对偶原理得到的位势法利用弧割技术, 就能够通过与已求出最短路的站点相邻的站点的信息找到新的站点的最短路, 而不去调用较远的站点的信息, 这节省了存储空间和计算时间, 提高了计算效率。
1最短路问题
正权简单有向图D= (V, A, W) 中, V (D) ={v1, v2, …, vn}为D的顶点集, A (D) ={aij|vi, vj∈V (D) }为D的弧集, W={wij|aij∈ A (D) , wij∈R+}为D的权集。点弧交错序列称为链, 点不重且弧首尾相连的链为路。设P为从v1到vn的一条路, 则路P的权定义[8]为:W (P) =∑ (wij:aij∈P) 。从v1到vn的权值最小的路为最短路。最短路问题就是从v1到vn的所有路中选择最短路径的问题。
最短路问题的数学模型为0-1整数规划模型Ⅰ:
Min W (P) =∑ (wij×xij:aij∈A (D) )
s.t.∑ (x1j:a1j∈A (D) ) -∑ (xj1:aj1∈A (D) ) =1 (1)
∑ (xnj:anj∈A (D) ) -∑ (xjn:ajn∈A (D) ) =-1 (2)
∑ (xij:aij∈A (D) ) -∑ (xji:aji∈A (D) )
=0 (i=2, 3, …, n-1) (3)
xij=0或1 (4)
2最短路问题的位势法
2.1最短路问题的位势法的基本原理
定理1 从v1到vn的路P为最短路的充分必要条件为:∀vi∈V (D) , ∃pi≥0, 满足条件Ⅰ:
(1) 对pj-pi<wij, 有xij=0;
(2) 对pj-pi=wij, 有xij=0或1。
其中当aij∈P时, xij=1;当aijP时, xij=0。
证明 考虑如下线性规划模型Ⅱ:
s.t.
Min W (P) =∑ (wij×xij:aij∈A (D) )
∑ (x1j:a1j∈A (D) ) -∑ (xj1:aj1∈A (D) ) =1 (5)
∑ (xnj:anj∈A (D) ) -∑ (xjn:ajn∈A (D) ) =-1 (6)
∑ (xij:aij∈A (D) ) -∑ (xji:aji∈A (D) ) =0 (7)
i=2, 3, …, n-1
0≤xij≤1 (8)
的条件Ⅱ:
(1) 对pj-pi<wij, 有xij=0;
(2) 对pj-pi>wij, 有xij=1;
(3) 对pj-pi=wij, 有0≤xij≤1。
令第1组约束对应的对偶变量为-p1;第2组约束对应的对偶变量为-pn;第3组约束对应的对偶变量为-pi;第4组约束对应的对偶变量为-rij, 则此问题的对偶问题为:
Maxzf =p1-pn-∑ (rij:aij∈A (D) )
s.t.
pj-pi-rij≤wij (aij∈A (D) ) (9)
rij≥0 (aij∈A (D) ) (10)
pi 无限制 (vi∈V (D) ) (11)
因此, 互补松紧条件为:
xij× (pj-pi-rij-wij) =0 (12)
(xij-1) ×rij=0 (13)
取rij=max{0, pj-pi-wij}, 由条件Ⅱ, 当pj-pi<wij时, 有xij=0和rij=0, 即条件 (12) 、 (13) 成立;当pj-pi>wij时, 有xij=1和 (pj-pi-rij-wij) =0, 即条件 (12) 、 (13) 成立。当pj-pi=wij时, 有rij=0和 (pj-pi-rij-wij) =0, 即条件 (12) 、 (13) 成立。因此, 条件Ⅱ成立时, 条件 (12) 、 (13) 成立。
当pj-pi<wij时, (pj-pi-rij-wij) ≠0, 由条件 (12) , 有xij=0;当pj-pi>bij时, rij≠0, 由条件 (13) , 有xij=1。而当pj-pi=bij时, rij= (pj-pi-rij-wij) =0, 则xij无约束。因此, 条件 (12) 、 (13) 成立时, 条件Ⅱ成立。
因此, 条件Ⅱ与条件 (12) 、 (13) 等价。由互补松紧原理, 模型Ⅱ的最优解的充分必要条件为条件Ⅱ。
线性规划模型Ⅱ为以v1为发点, 以vn为收点, 以W为费用集, 所有弧容量为1的网络的最小费用流问题的数学模型。根据网络流的整流定理, 条件Ⅱ等价于条件Ⅲ:
(1) 对pj-pi<wij, 有xij=0;
(2) 对pj-pi>wij, 有xij=1;
(3) 对pj-pi=wij, 有xij=0或1。
在求解该网络的最小费用流时, 从零流开始计算, 此时有pj-pi≤wij。由于弧的容量为1, 因此, 第一条增广链 (迭代1次) 就是最短路, 即在找增广链时始终在xij=0 (pj-pi≤wij) 的弧上调整pi值。因此在计算的始终任意点的pi值必须满足条件pj-pi≤wij, 即pj-pi>wij不会出现。因此条件Ⅱ、条件Ⅲ等价于条件Ⅰ。
根据网络流的整流定理, 线性规划模型Ⅱ与0-1整数规划模型Ⅰ等价。证毕。
对任意vi∈V (D) , 称非负实数pi为顶点vi的势, p={pi}为网络D的势。在网络D中, 任意两点vi和vj均有pj-pi≤wij, 则p={pi}称为网络D的可行势。按照定理1, 可设计求最短路的算法, 该算法划分顶点集为S和T, 从某个可行势开始, 在I={aij|pj-pi=wij}上找增广链, 将所有存在增广链的顶点放入S中, 并修改T中的势, 将一个可行势变为另一个可行势, 从而扩大S中的顶点数目。这里的增广链就是最短路。设V=S∪T, S∩T=ϕ, 网络D的弧割就是尾在S中, 头在T中的弧集为弧割 (S, T) 。
定理2 在某可行势p={pi}下, S为在D[I]上存在以v1为起点的增广链的所有顶点组成的集合, 其中D[I]为弧导出子图, I={aij|pj-pi=wij}, T= V (D) -S。则:
(1) 在正整数权网络D中, 对∀vi∈S, 置p′i=pi;对∀vi∈T, 置p′i=pi +1, D的势p′={p′i}还是可行势。
(2) 若 (S, T) ≠ϕ, 则对∀vi∈S, 置p′i=pi;对∀vi∈T, 置p′i=pi+δ, D的势p′={p′i}也是可行势, 且S′⊇S∪R。其中δ=min{wij+pi-pj|aij∈ (S, T) }, R={vj|p′j-p′i=wij∧aij∈ (S, T) }。
(3) 若 (S, T) =ϕ, 且vnS, 则不存在从v1到vn的最短路。
(4) 若p1=0, 则S中每一点vi的势pi为从v1到vi的最短路程, 到达点vi的增广链为从v1到vi的最短路。
证明 根据S的定义, 对∀aij∈ (S, T) , 有pj-pi<wij, 而对∀aji∈ (T, S) , 有pi-pj≤wji。
(1) 在正整数权网络D中, 对∀aij (S, T) ∪ (T, S) , 有p′j-p′i=pj-pi≤wji;对∀aij∈ (S, T) , 有p′j-p′i=pj+1-pi<wij+1≤wij;对∀ aji ∈ (T, S) , 有p′i-p′j=pi-pj-1≤wji-1<wji。因此, D的势p′={p′i}还是可行势。
(2) 当 (S, T) ≠ϕ时, 由于对∀aij∈ (S, T) , wij+pi-pj>0, 有δ=min{wij+pi-pj|aij∈ (S, T) }>0。与1同理可证, D的势p′={p′i}还是可行势。在I′={aij|p′j-p′i=wij∧aij ∈ (S, T) }上, vi∈S为标号未检查点, 对vj∈T进行标号, 得到从v1到vj的增广链, 即vj∈ S′。因此, S′⊇S∪R。
(3) 当 (S, T) =ϕ时, 没有从S到T的路, 即不存在从v1到vn的路。
(4) 根据S的定义, 存在从v1到vi的增广链。若对增广链上的弧aij, 令xij=1, 其他的弧aij, 令xij=0, 则根据定理1, {xij}为0-1整数规划模型Ⅰ的最优解。即该增广链为从v1到vi的最短路。由pi的确定过程可得到:当p1=0时, pi为该增广链的长度, 即为v1到vi的最短路程。证毕。
2.2最短路问题的位势法
正整数权网络D= (V, A, W) 中, V (D) ={v1, v2, …, vn}为D的顶点集, A (D) ={aij|vi, vj∈V (D) }为D的弧集, W={wij|aij∈A (D) , wij∈N+}为D的权集。最短路问题的位势法具体计算步骤如下:
步骤1 对所有vi∈V (D) , 置pi=0, 得到势p={pi}, 并置S={v1}, T=V (D) -S。
步骤2 对∀vj∈T, 若pj-pi=wij (∃vi∈S) , 则S=S+{vj}, T=T-{vj}, 记λj=i。
步骤3 若vn∈S, 则用反向追踪法, 得到从v1到vn的最短路, 结束;否则, 对vi∈T, 置pi=pi+1, 返回步骤2。
2.3最短路问题的位势法的改进1
该最短路问题的位势法的不足之处是:第一, 当网络不存在从v1到vn的最短路时, 算法无法终止;第二, 该位势法中T中的每一点位势相同, 增加了存储和计算的负担。因此, 该算法可以进行改进。改进要点是:取消T中的位势;对S中的点进行标号: (势, 路由) , 以方便计算;增加终止条件, 使算法在有限步终止。最短路问题改进的位势法具体计算步骤如下:
步骤1 置p1=0, p=1, 并置S={v1}, v1标号为: (0, 1) 。
步骤2 若 (S, V (D) -S) =ϕ, 则不存在从v1到vn的最短路, 结束。
步骤3 对∀vjS, 若wij=p-pi (∃vi∈S) , 则置S=S+{vj}, vj标号为: (p, i) , 即pj=p, λj=i。
步骤4 若vn∈S, 则用反向追踪法, 得到从v1到vn的最短路, 结束;否则, 置p=p+1, 返回步骤2。
2.4最短路问题的位势法的改进2
由于vi的势pi为v1到vi的最短路程, 若从v1到vn的最短路程为L, 则上述改进的最短路问题的位势法的算法复杂性为O (nL) 。计算量较大是因为需要迭代L次, 若每次迭代计算出δ=min{wij+pi-pj|aij∈ (S, T) }, 并置p=p+δ, 则迭代次数变为O (n) 。另外, 上述改进的位势法中的第二步并不需要对V (D) -S中所有的点进行检验, 只需要检验V (D) -S中与S中某点相邻的点, 即弧割 (S, V (D) -S) 生成的子图D[ (S, V (D) -S) ]中在V (D) -S中的点。而且, 也要注意到:该算法仅适用于整数费用网络, 若每一次更新p采用公式:p=min{wij+pi|aij∈ (S, V (D) -S) }, 则算法的使用范围可以扩大。因此, 该算法还可以继续改进。正权网络D= (V, A, W) 中, V (D) ={v1, v2, …, vn}为D的顶点集, A (D) ={aij|vi, vj∈V (D) }为D的弧集, W={wij|aij∈A (D) , wij∈R+}为D的权集。新的最短路问题位势法具体计算步骤如下:
步骤1 置p1=0, S={v1}, v1标号为: (0, 1) 。取p=min{w1i|a1i∈V (D) }。
步骤2 若 (S, V (D) -S) =ϕ, 则不存在从v1到vn的最短路, 结束。
步骤3 计算R={vj|p-pi=wij∧aij∈ (S, V (D) -S) }, 置S=S∪R。
步骤4 ∀vj∈R, ∃vi∈S, 使wij=p-pi, vj标号为: (p, i) , 即pj=p, λj=i。
步骤5 若vn∈S, 则用反向追踪法, 得到从v1到vn的最短路, 结束;否则, 计算p=min{wij+pi|aij∈ (S, V (D) -S) }, 返回步骤2。
2.5若干计算问题的计算方法
在新的最短路问题位势法中, 要考虑集合 (S, V (D) -S) 的计算问题和步骤3、步骤4的计算问题。下面分别给出这些问题的计算方法。
(S, V (D) -S) 的计算步骤:
步骤1 将网络D用邻接表表示法表示。不妨设S={v1, v2, …, vk}, 置i=1, 置 (S, V (D) -S) =ϕ。
步骤2 设vi的出弧集合为{aii (1) , aii (2) , …, aii (t) }。置j=1。
步骤3 若vi (j) S, 则 (S, V (D) -S) = (S, V (D) -S) ∪{aii (j) }。
步骤4 若j≤t-1, 则置j=j+1, 返回步骤3。
步骤5 若i≤k-1, 则置i=i+1, 返回步骤2;否则, 输出 (S, V (D) -S) , 结束。
步骤3、步骤4的计算方法:
1) 每个顶点vi附加两个存储单元, 分别存储势pi和路由λi。不妨设 (S, V (D) -S) ={ai (1) j (1) , ai (2) j (2) , …, ai (q) j (q) }, 置k=1。
2) 若wi (k) j (k) =p-pi (k) , 则置S=S∪{vj (k) }, pj (k) =p, λj (k) =i (k) 。
3) 若k≤q-1, 则置k=k+1, 返回2) 。
3标号法
该算法的计算过程可通过在图上标注顶点的标号来完成迭代。为说明算法的有效性和可行性, 对如图1所示的费用网络用标号法求解从v1到v7的最短路。在图1中:
V (D) ={v1, v2, v3, v4, v5, v6, v7}
A (D) ={a12, a13, a14, a24, a25, a34, a36, a45, a46, a47, a57, a67}
W (D) ={2, 3, 4, 5, 5, 2, 7, 5, 1, 6, 1, 3}
首先对v1标号为: (0, 1) , 置S={v1}, 计算:
p=min{w12, w13, w14}=w12=2 R={v2}
对v2标号为: (2, 1) , 置S={v1, v2}, 完成第一次迭代。计算:
p=min{p2+w24, p2+w25, w13, w14}
=w13=3 S={v1, v2, v3}
对v3标号为: (3, 1) , 计算:
p=min{p2+w24p2+w25p3+w34p3+w36, w14}
=w14=4 S={v1, v2, v3, v4}
对v4标号为: (4, 1) , 完成第三次迭代。得到如图2所示的计算结果。
以后的迭代, 计算:
p=min{p2+w25, p3+w36, p4+w45, p4+w46, p4+
w47}=p4+w46=5
S={v1, v2, v3, v4, v6}
对v6标号为: (5, 4) , 计算:
p=min{p2+w25, p4+w45, p4+w47, p6+w67}
= p2+w25=7
S={v1, v2, v3, v4, v5, v6}
对v5标号为: (7, 2) , 计算:
p=min{p5+w57, p4+w47, p6+w67}
=p6+w67或p5+w57=8
S={v1, v2, v3, v4, v5, v6, v7}
对v7标号为: (8, 5) 或 (8, 6) 。v7∈S, 反向追踪法, 得到从v1到v7的最短路为v1→v2→v5→v7或v1→v4→v6→v7, 最短路程为8。最后的计算结果如图3所示。
4与Dijkstra算法的比较与结束语
最短路问题位势法与Dijkstra算法的比较, 具有以下特点:
(1) Dijkstra算法与最短路问题位势法的算法复杂度相当。
(2) Dijkstra算法要求对网络中全部顶点进行标号, 并将标号分为两类:永久性标号和临时性标号, 其中永久性标号与最短路问题位势法中的顶点势相同, 且迭代过程通过对全部临时性标号的修改和比较来完成, 因此, Dijkstra算法的计算具有全局性;而最短路问题位势法只对确定了最短路的顶点标注位势, 而不考虑其他的点 (距离起点更远的点) 的位势, 而且在迭代过程中也仅考虑与确定了最短路的顶点相邻接的顶点, 而不考虑更远的顶点, 因此, 最短路问题位势法的计算具有局部性。
(3) Dijkstra算法每迭代一次只能确定一个顶点的永久性标号;而最短路问题位势法在一次迭代中能确定一个顶点集合的位势, 该顶点集的顶点数目会超过1。
(4) Dijkstra算法只能计算出一条最短路;而最短路问题位势法可以计算出全部最短路。
(5) 对规模小且稠密的网络, Dijkstra算法与最短路问题位势法没有区别。而当网络的规模巨大, 或网络很稀松时, 最短路问题位势法将更有效。
通过以上分析:最短路问题位势法是求解最短路问题的有效算法。关于最短路问题, 我们提供了两种位势法, 可以根据不同的问题和不同的需要选择其中一种算法。这两种算法均先计算一个标准势, 再用标准势进行比较的方法按照位势由小到大的顺序逐步寻找顶点并确定其位势和路由。两种算法主要差别就是标准势的计算不同。第一种位势法采用原标准势加1的修改法, 该算法虽然计算简单, 但算法仅适用于正整数费用情形;第二种位势法利用弧割的概念寻找最小标准势来代替原标准势, 该算法适用于正费用情形, 扩大了算法使用范围。
公交网络的查询系统中, 该网络的特点是公交站点多, 公交线路复杂, 公交综合费用为正整数。基于以上特点采用最短路问题位势法是最好的选择。
参考文献
[1]谢金星, 邢文训.网络优化[M].北京:清华大学出版社, 2000.
[2]刁在筠, 郑汉鼎, 刘家壮, 等.运筹学[M].2版.北京:高等教育出版社, 2001.
[3]Sheperd Bruce, Zhang Lisa.A cycle augmentation algorithm for mini-mum cost multicommodity flow on a ring[J].Discrete Applied Mathe-matics, 2001, 110:301-315.
[4]Orlin James B.A polynomial time primal network simplex algorithm for minimum cost flows[J].Mathematical Programming, 1997, 78:109-129.
[5]周康.一类LP问题算法的改进[J].武汉工业学院学报, 2005, 24 (4) :104-106.
[6]周康, 同小军, 许进.路序问题基于表面的DNA算法[J].华中科技大学学报:自然科学版, 2005, 33 (8) :100-103.
[7]周康, 王子成, 许进.最大流问题的DNA计算两阶段法[J].华中科技大学学报:自然科学版, 2005, 33 (8) :104-107.
[8]周康, 同小军, 许进.最优指派问题DNA算法[J].系统工程与电子技术, 2007, 29 (7) :1183-1187.
[9]周康, 刘文斌, 许进.TSP的DNA计算算法[J].系统工程与电子技术, 2007, 29 (2) :316-319.
最短路问题 篇2
网络分层用于最短路问题的算法研究
提出了一种基于Dijkstra方法的网络分层算法,实现了两点间节点数最少条件下最短通路的求取,并与传统Dijkstra算法进行了比较,得到了一些有益的结论.
作 者：付江缺 高井祥 段春燕 孙正明 FU Jiang-que GAO Jing-xiang DUAN Chun-yan SUN Zheng-ming 作者单位：付江缺,高井祥,孙正明,FU Jiang-que,GAO Jing-xiang,SUN Zheng-ming(中国矿业大学环境与测绘学院,江苏徐州,221008)段春燕,DUAN Chun-yan(中国矿业大学理学院,江苏徐州,221008)
刊 名：测绘科学 ISTIC PKU英文刊名：SCIENCE OF SURVEYING AND MAPPING 年，卷(期)：2009 34(3) 分类号：P282 关键词：邻接矩阵 最短网络层 Dijkstra算法最短路问题 篇3
关键词：最短；假设；转化；平移；对称
中图分类号：G633.6 文献标识码： A 文章编号：1992-7711（2016）18-059-02
0
众所周知，转化思想是数学中最基本的数学思想。而假设法也是一种重要的数学思维方法，在问题的转化过程中，假设起“桥梁”作用。下面我们以数学人教版八年级“课题学习——最短路径问题”为例，来体验一下假设法对于问题转化的重要性。
一、模型1——在直线上求作一点与直线同侧的两点所连线段之和最小
例1：如图1-1，点A，B分别是直线异侧的两个点，在上求作一点C，使CA+CB最短。
解决策略：连接AB，与直线的交点即为所求。
这是最基本的数学模型。下面我们用假设法对这个模型进行举一反三、拓展应用。
二、模型1“变形记”——模型2
模型2：在直线上求作一点与直线异侧的两点所连线段之和最小
例2：如图2-1，点A，B分别是直线同侧的两个点，在上求作一点C，使CA+CB最短。
如图2-2，假设把河面看作一面镜子，点B反射到另一侧点B'处，则A、B'两点位于直线异侧，“模型2”就转化为“模型1”。当然，作点A的对称点也可。
解决策略：先作其中一个点关于这条直线的对称点，再连接对称点与另一个点，与该直线的交点即为所求。要证CA+CB最短，如图2-3，在直线上另外任取一点C'，然后证明AC+BC三、模型1再“变身”
提到“河”，人们会想到“桥”。下面就来谈谈人们熟悉的造桥选址问题。
例3：如图3-1，从A地到B地经过一条小河（河岸a∥b），现要在河上建一座与两岸垂直的桥MN，桥造在何处才能使从A地到B地的路径AMNB最短？
分析：造的桥要与河垂直，由于路径AMNB中的MN的长度是个定值（等于河宽），因此只需使AM+NB最小即可。
（一）法1——条件假设，变“因”导“果”
在本例中，假如河的宽度变为零，这个问题就转化成前面所讲的“模型1”。
如图3-2，将点A向与河岸垂直的方向平移一个河岸宽度到A1，我们可以假想直线a也平移到了直线b并与a重合，由于点A1和点B分别位居直线b两侧，由“模型1”可知，只需连接A1B，交河岸于点N，在此处造桥MN，所得路径AMNB就是最短路径。
略证：如图3-3，如果在不同于MN的位置造桥M1N1.由于M1N1=MN=AA1；又根据“两点之间，线段最短”，AN1+N1B>A1N+NB，故路径AMNB要短于AM1N1B.
（二）法2——结论假设，执“果”索“因”
如图3-2，从A到B可行走的路线是A→M→N→B，假设在此路线中AM+BN最短，现来找一找它应该满足的条件.要使AM+BN最短，需将两线段拼在一条直线。因为两点之间，线段最短，故将AM平移到A1N，使A1、N、B三点共线，A1N+NB最小.此时，AM∥A1N且AM=A1N，可证四边形AMNA1是平行四边形，则AA1=MN；因此，需要先将点A向垂直于直线b的方向平移一个河岸宽度到A1处。
四、模型1拓展记
（一）情景设疑
如果一条河变成两条河，需要驾两座桥或更多座桥，又该如何选址呢？
例4：如图4-1，从A地到B地经过两条小河，现要在河上建两座与河岸垂直的桥，则在何处建桥才能使从A地到B地的路径最短？
（二）解法展示
法1：将其中的点A或点B连续平移两次
如图4-2，先将点A沿与河流河岸垂直的方向平移一个河宽到A1，再沿与河流2河岸垂直的方向平移一河宽到A2，连接A2B，交河流2河岸于N，此处建桥MN；连接A1M，交河流1于P，在此处建桥PQ，所得路径AQPMNB最短。
法2：将点A、点B分别平移一次
如图4-3，将A沿与河流1垂直的方向平移一个河宽，得到A1，再将B沿与河流2河岸垂直的方向平移1个河的宽度得到B1，连接A1B1与河流1、河流2分别相交于N、P，分别作桥MN、PQ，所得路径AQPNMB最短。
（三）归纳小结
由上可知，造桥选址问题，要使所得到的路径最短，通过平移变换（向垂直于河岸的方向平移），使除了桥长不变外所得到的其他路径平移后在一条直线上。
五、模型1、模型2“融合記”
分析：本例是平移变换和轴对称变换的综合题，同样也可以用假设法解决。如图5-2，假设PQ的长度为零，将点B沿平行于直线的方向朝左平移PQ的长（定长）至B'，再在直线上找一点P，使AP+PB'最小（转化为模型2），最后作点A关于直线的对称点A'（转化为模型1），连接A'B'，交直线于P；最后在直线上截取线段PQ等于定长。则此时AP+PQ+BQ最小，原理如图5-3所示（证明略）。
综上所述，在解决最短路径问题时，我们可以用假设法，利用轴对称、平移等变换把不在一条直线上的几条线段转化到一条直线上，从而得出最短路径。这样将未解决的问题转化为另一个较易解决的问题或已经解决的问题，真正实现了化难为易，化未知为已知，从而迅速找到问题的突破口，提高解题能力。
[参考文献]
[1]义务教育数学课程标准.2011年版.北京师范大学出版社，2012.01.
最短路线问题的深度认识 篇4
试题第3问 (改编题)
如图 (1) 在平面直角坐标系xoy中, △MAB是等边三角形, 且, 设G为y轴上一点, 点P从M点出发, 先沿y轴到达G点, 再沿GA到达A点, 若P点在y轴上运动的速度是它在直线GA上运动速度的2倍, 试确定G点的位置, 使P点按照上述要求到达A点所用的时间最短。
解法一: (几何法)
分析:一方面:要使P点按指定路线从M到A所运动的时间最少, 我们可以设P点在直线GA上运动速度为v, 则它在y轴上运动的速度是2v, 时间最小时, 时间最小问题可以转化为如下的路线最短问题。
已知A为直线OM外一点, A到OM的垂足为O, G为线段OM上任一点, 确定点G的位置, 使最小。
另一方面:构造等于的线段, 简化问题结论是点G在OM上移动的过程中, 的大小不断变化, 但注意到∠OMB=30°, 过点G作GN⊥BM, 形成RtΔMGN, (如图 (2) 易知, 。因此, 问题转化为“探究点G在定直线OM上的位置, 使点G到定点A和点G到直线BM的距离的和GN+AG最小”, 于是问题解决。
确定点G位置的方法: (如图3) 过A点作AH⊥BM于点H, 则AH与y轴的交点为所求的G点, 进而确定满足条件的G点坐标为。
解法二: (代数法)
详解:设P点在一直线GA上运动速度为k, 则它在y轴上运动的速度是2k, (k>0) 。再设AG长为x, 若点P从M点出发, 运动到G点再到点A处所用时间为t, 在RtΔOAG中 (如图4)
即2kt=MG+2GA
将MG、GA用含x的式子代换得到下列方程:
两边平方得:
整理成关于x的一元二次方程为:
此方程有实数根, 则:
于是得到时间t的最小值为:
把代入方程 (1) 中整理得:
小结:解法一 (几何法) 把时间最短问题转化为“最短路线”问题, 并且巧妙构造出一个含有30°角的直角三角形的基本图形, 使问题圆满解决。本法充分体现了几何法的直观形象性。
最短路径教案 篇5
教学目标：
1.理解并掌握平面内一条直线同侧两个点到直线上的某一点距离之和为最小值时点的位置的确定。
2.能利用轴对称平移解决实际问题中路径最短的问题。
3.通过独立思考，合作探究，培养学生运用数学知识解决实际问题的基本能力，感受学习成功的快乐。
教学重点：
将实际问题转化成数学问题，运用轴对称平移解决生活中路径最短的问题，确定出最短路径的方法。
教学难点：
探索发现“最短路径”的方案，确定最短路径的作图及原理。
导学过程：
一、创设情景，引入新知。
前面我们研究过一些关于“两点的所有连线中，线段最短”、“连接直线外一点与直线上各点的所有线段中，垂线段最短”等的问题，我们称它们为最短路径问题．现实生活中经常涉及到选择最短路径的问题，本节将利用数学知识探究实际生活中的最短路径问题。
二、自主学习，探究新知。
问题1（将军饮马问题）
牧马人从A地出发，到一条笔直的河边L饮马，然后到B地，牧马人到河边什么地方饮马，可使所走的路径最短？
2、探索问题：
教师提出问题，引导学生思考：
（1）如何将这个实际问题转化为数学问题？转化的要点是什么？
（2）回忆以前学过的“最短”的知识点，（两点之间，线段最短；垂线段最短），思考：这个问题中的“最短”和以前学过的知识有什么相同点和不同点？（3）、如何把“不同点”化为“相同点”？（4）、如何用图形将问题展现出来？
【学生活动】：学生独立思考，画图分析，并尝试回答，相互补充，师生共同归纳：（1）、将A、B两地抽象为两个点，将河L抽象为一条直线（如图2），则问题转化为：如何在L上找一点C，使AC与BC的和最小（如图3）。转化时要注意条件和结论的转化，以及点、线的抽象。
（2）、相同点：都是两点间的最短距离问题。
不同点：一个是两点在L的同侧；一个是两点在L的异侧，并画图比较（如图4）。（3）利用轴对称的知识找出B点关于直线L的对称点B′,就可以满足C B′= CB,再连接A B′，则A B′与直线L的交点C极为所求。
【教师板书并画图】（如图5）
第一步：作出B点关于直线L的对称点B′
第二步：连接A B′，与直线L的交点为C,则C点即为所求。
证明：略
问题二（造桥选址问题）如图,A和B两地在一条河的两岸,现要在河上造一座桥MN.桥造在何处可使从A到B的路径AMNB最短?（假定河的两岸是平行的直线,桥要与河垂直.)
将实际问题中A，B两地与笔直的河L抽象成 点A.点B和直线a，b.如图：
分析：AM+NB最短，要先确定点N在直线b的位置，如果我先将A点往直线a的垂直方向平移MN个单位 后到A′，由于MN垂直直线a，N点就是M点往直线 b的垂直方向平移MN个单位后到的点，由图形平移后 的对应点之间的线段是平行且相等的，得到AM=A′N.AM+NB最短即A′N+NB最短.转变成了直线b上是找 到一点N，使A′ N+NB最短,连结A′,B,与直线b相交的 一点为N点.证明略.三、巩固练习：
1.∠WXZ内有一点Z，在WZ，ZY上分别有点A，B,当△ABZ的周长最小时，请在图中作出点A，B的位置.2.如图，A、B两地之间有两条河，现要在两条河上各造一座桥MN和PQ.桥分别建在何处才能使从A到B的路径最短？（假定河的两岸是平行的直线，桥要与河岸垂直）
四、课堂小结
1、本节主要知识点：
轴对称的对称知识和两点间的最短距离在“最短路径”这类问题中的运用。实际问题与数学问题的转化。
2、提出问题： 这节课你们学到了什么？还有哪些疑惑？
五、布置作业
最短路问题 篇6
1．1 两个已知点在已知直线的同一侧
例1 如图1所示，要在街道旁修建一个奶站，向居民区A，B提供牛奶，奶站应建在什么地方，才能使从A、B到它的距离之和最短？
作法 （1）作点B关于街道的对你点C；
（2）连结AC交街道于点P．
故奶站应建在点P 处．
证明 在街道上任取一点N，连结AN、BN、CN、PB．
因为点B和点C关于街道对称，
所以PB=PC，BN= CN．
又因为AC
所以AP+PB
故奶站建在点P 处，A、B到它的距离之和最短．
例2 如图2所示，要在街道旁修建一个奶站，向居民区A，B提供牛奶，奶站应建在什么地方，才能使从A、B到它的距离相等？
作法 （1）连结AB；
（2）作线段AB的垂直平分线CD，交街道于点M．故奶站应建在点M处．
证明 连结AM、BM．
因为点M在线段AB的垂直平分线上，所以AM=BM．
故奶站建在点M处，A、B到它的距离相等．
1．2 两个已知点在已知直线的两侧
例3 如图3所示，要在街道旁修建一个奶站，向居民区A，B提供牛奶，奶站应建在什么地方，才能使从A、B到它的距离之和最短？
作法 连结AB，交街道于点E．
故奶站应在点E 处．
证明 在街道上任取一点G，连结AG、BG．
因为AB
所以奶站建在点E处，A、B到它的距离之和最短．
例4 如图4所示，要在街道旁修建一个奶站，向居民区A，B提供牛奶，奶站应建在什么地方，才能使从A、B到它的距离相等？
作法 （1）连结AB；
（2）作线段AB的垂直平分线CD，交街道于点F．
故奶站应在点F 处．
证明 连结AF、BF．
因为点F在线段AB的垂直平分线上，
所以AF=BF．
故奶站建在点F处，A、B到它的距离相等．
2 与街道的宽度相关的作图
例5 如图5，甲、乙两个单位分别位于一条封闭式街道的两旁，现准备合作修建一座过街的天桥．问：
（1）桥建在何处才能使由甲到乙的路线最短？注意桥必须与街道垂直．
（2）桥建在何处才能使甲、乙到桥的距离相等？
解 （1）如图6，将点A向垂直于街道的方向平移到点A1，平移的距离为街道的宽度，连结A1B交街道的边缘于点M，所以桥应建在MN处（MN与街道垂直），就能使由甲到乙的路程AN+NM+MB最短．
证明 假设桥建在不同于MN的任意一处FP（FP与街道垂直），过点B作与街道垂直的直线BC与街道边缘的垂足分别为C、E，延长AN交BC于点D，连结AF、PB、FD．
因为AA1=MN，AA1∥MN，所以四边形A1MNA为平行四边形．所以AN=A1M，ND∥MB．又因为MN∥BD，所以四边形MBDN为平行四边形．所以MB=ND．易证四边形MECN为矩形．所以ME=NC．所以△MBE≌△NDC．
所以BE=DC．易证四边形PECF为矩形．所以PE=FC．所以△PBE≌△FDC．所以PB=DF．因为AD
故桥建在MN处，由甲到乙的路线最短．
（2）如图7，作点B关于街道的对称点B1，B1B与街道边缘分别交于点C、D．连结AB1，作线段AB1的垂直平分线交街道的边缘于点F，所以桥建在FE（FE与街道垂直）处，就能使甲、乙到桥的距离相等．
证明 连结AF、B1F、BE．
因为点F在线段AB1的垂直平分线上，所以AF=B1F．易证四边形ECDF为矩形．所以EC=FD．又因为B和B1关于街道对称，所以BC=B1D．所以△BCE≌△B1DF．所以BE=B1F．所以AF=BE．
故桥建在FE处，甲、乙到桥的距离相等．
以上实例的解答过程共用到了以下12个方面的数学知识：（1）作已知点的轴对称点的方法；（2）轴对称的性质；（3）三角形三边的关系；（4）作线段中垂线的方法；（5）线段中垂线的性质；（6）平移一个点的方法；（7）平行四边形的判定；（8）平行四边形的性质；（9）矩形的判定方法；（10）矩形的性质；（11）全等三角形的判定方法；（12）全等三角形的性质．显然，像这样的题组式的教学不仅让学生体验到了变式给他们带来的乐趣和挑战，同时大量的数学知识得到了运用与巩固．
プ髡呒蚪榧本刊2008年第10期（总第222期第58页）.
单源最短路问题高效算法探究 篇7
关键词：最短路,迪杰斯特拉,数据结构,标准模板库,优化算法
1 引言
最短路问题是一个经典问题,过程涉及算法设计、数据结构、运筹学、图论等多方面的知识,有很深远的理论研究意义,并在许多学科中有重要应用。在实际生活以及工程实际应用中,最短路问题的求解算法也尤为重要,例如交通路线的选择、公用设施的地点布局、管道线路的安排、智能机器人的路线选择、最短时间规划等等。
实际问题中又以单源最短路问题居多,解决单源最短路问题有比较优秀的迪杰斯特拉算法,著名的E.W.Dijkstra在1959年提出该算法,是图论中求解最短路问题的一个经典算法。由单源最短路问题可以引申出更多类似的问题,比如时间规划问题、成本预算问题、收益最大化问题等,这些与最短路同构的问题,往往可以应用Dijkstra算法得到满意的结果。
随着计算机技术的发展,绝大多数算法问题已经转变为在计算机平台上实现,其中又以使用计算机程序处理为主。在计算机编程实现的过程中,程序往往不够优化,达不到令人满意的结果,效率瓶颈突出。本文通过分析Dijkstra算法的本质,透彻分析计算机语言的特点,加之合理的数据结构,并使用C++语言实现优化的Dijkstra算法,达到了一般意义下的时间复杂度和空间复杂度的下限。
2 迪杰斯特拉算法
2.1 迪杰斯特拉算法基本思想
单源最短路问题是指在一个有权的图中求出源点到其他所有点的最短路径,而Dijkstra算法是解决单源最短路问题的有效算法,在图中不存在负环(即一条从源点到源点不经过重复的边并且权值之和为负的路径)的情况下,可以得到正确的结果。其基本思想是算法中的贪心思想:每次找到一条最短的未知路径,然后用该路径更新其他未知路径的最短距离,直到不存在未知路径为止。
2.2 迪杰斯特拉算法数学描述
步骤如下:
图G=(V,E),其中V为点的集合,E为边的集合,源点为src,已经求得最短路的目的点集设为S,源点到点i的距离d[i]
2.3 迪杰斯特拉算法复杂度分析
分析2.2的数学描述,算法的时间消耗主要在循环上,而每次循环耗费时间的就是步骤4),即找未探索点中的最近点。设n=|V|,即n表示图中顶点的个数;m=|E|,即m表示图中边的条数。则最多循环n次,因为每次循环将使得S中的点数增加一个;同时,每次循环中找最近点的过程需要找n次,因为总共有n个点。综合考虑后,传统迪杰斯特拉算法的时间复杂度为O(n2)。空间消耗主要在图的存储上,如果采用邻接矩阵表示图,则空间复杂度为O(n2)。
3 算法优化探究
3.1 使用链表优化
从上面的分析可以得到空间复杂度为O(n2)的算法,似乎空间复杂度不是很高,然而对于顶点很多,而边却很少的稀疏图,用邻接矩阵表示的图在空间利用率上会相当低。因此,我们考虑到了使用基于链表的邻接表来表示图,从而将空间复杂度从O(n2)转变为O(m),对于处理稀疏图,有很大优势。
在访问图中的边时,若采用邻接表,则访问的次数也会有所降低,这是因为用邻接矩阵表示图的时候,对于边的访问,必须从一个顶点循环枚举到所有顶点的边,然而由于图的稀疏性,一个点所连接的边可能很少,甚至出度为0,此时用邻接表就要明显优于邻接矩阵表示的图。
3.2 使用静态内存的链表优化
链表具有灵活和高效的特点,然而的实际应用过程中往往不那么容易。一方面是因为早期的C语言不具有链表数据结构,必须自己手动编写链表结构,程序很容易出错。对于参加程序设计大赛的选手来说,手写代码量较大的数据结构,除非在万不得已时,一般是不会手写数据结构代码的,因为容易出错,对于程序的正确性难以保证。在最短路问题中,若用邻接表来表示图,只需要编写创建链表和访问链表的函数,所以程序量在该算法中不是很大。
经常写程序的话,就会体会到使用动态内存的数据结构,不但容易出错,在效率上更是会明显地降低。以约瑟夫问题举例来说,使用链表数据结构按照理论应该是比数组直接简单模拟的算法要快,然而在实际过程中就会发现两者无太大差别,在数据量比较大的时候,数组反而比链表快得多。实际上这是链表使用了动态内存的原因,申请动态内存将会占据大量的时间。这就留给我们一个问题,在使用链表的过程中,是否可以使用静态内存?对于程序设计很熟悉的人员,马上可以想到,先申请一个很大的数组,然后将该数组作为动态数据申请的数据段,就可以实现静态内存的链表。这样优化之后,可以在很大程序上减少程序的运行时间,同时也可以减少系统管理动态内存出错导致的问题。该优化措施的有效性可以在后面的实验中得到验证。
设有权有向图G=(V,E),V是顶点的集合,|V|=n;E是边的集合,|E|=m。下面给出使用静态内存链表的定义过程,申请内存过程,以及创建邻接表的过程,使用C++代码表示如下:
3.3 使用高级数据结构进行优化
上面两个步骤的优化都是行之有效的方法,然而在使用了静态内存链表的数据结构后,我们仍不能降低该问题的理论时间复杂度上限O(n2)。再来透彻地分析一下原始的迪杰斯特拉算法,我们发现对于每次循环查找最近点的过程,最坏情况下循环上限是n次,查找问题是算法中一个典型的问题,我们通常会想到使用哈希表来查找,这样可以将查找的的复杂度降低至O(1)的复杂度,然而哈希技术一般是针对数字方面的查找,对于从给定集合中查找最小值的问题,似乎束手无策,那么还有什么好的技术可以使用呢?
二杈搜索树BST(Binary Search Tree)的查找过程和插入过程以及其他一些常用操作都只需要O(log n)的时间复杂度,常用的二杈搜索树有AVL、Treap、Splay、红黑树等等,这些高级数据结构都有着很高执行效率,在解决算法问题的过程中得到了广泛的应用,在数据库技术中也有很多应用,是数据处理技术的理论基础。然而要想自己写出这些高级数据结构的全部操作,对于一般的程序设计者来说,还是有相当大的困难,虽然可以花费长时间来写出模板,然后在以后应用过程中直接调用即可,但是在程序设计比赛等一些特殊场合来说,程序的精简性尤为重要。
说到程序的精简性,我们一定会想到STL(Standard Template Library),即标准模板库。STL中包含了很多种数据结构的通用模板,使用起来尤为方便,程序简洁,且不容易出错。例如上面提到的BST,在C++STL中使用了红黑树来实现,虽然不能实现BST的所有操作,但是对于处理最短路问题,使用C++STL中的BST数据结构set,可以满足要求。set具有插入,查找,删除等操作,完全可以胜任最短路问题中的查找要求。
回头再来思考Dijkstra算法,过程中主要的操作就是查找最小值,以及删除最小值。只是对最小值处理的话,其实我们有更简单的数据结构来处理,这就是被称作“堆”的数据结构,堆支持查找最小值,删除最小值,插入某个数值等操作,在最短路算法过程中使用堆的数据结构,不仅程序编写量小,更重要的是查找效率比BST高得多,查找的时间复杂度可以降低至O(1)。可见,如果使用的堆来查找,可以极大的降低时间复杂度,查找的时间复杂度为O(1),删除最小值的时间复杂度为O(log n),总共循环n次,可见时间复杂度已经降低至O(n*log n),相比于原先的O(n2),有了很大的提高。
5 使用优先队列全面优化程序
一个好的程序,不仅要求效率高,还要求容易实现,容易编写,这也是为什么即使计算机的运算速度达到无限快时,我们还要继续研究算法的原因。堆的数据结构实现起来并不困难,但是对于不熟悉的人来说还是有一定难度。其实这里我们可以继续使用STL来简化程序,简化后的程序程序量小,简洁易懂,应用价值很高。
STL中拥有heap的数据结构,也就是堆,但是STL中的heap并没有封装成类,在通用性和安全性上还存在问题,使用起来也不是很方便。STL同时提供优先队列priority_queue,实际上就是把heap进行类的封装,以方便使用。需要注意的是priority_queue默认为大根堆,而我们需要的是小根堆,所以需要自行编写比较函数,以使用小根堆,具体的C++代码如下:
6 算法效率评价
6.1 理论复杂度分析
再来分析一下上述算法的空间复杂度和时间复杂度。由于采用链表存储,因此实际使用的内存不会超过2×m×sizeof(data),空间复杂度为O(m)。算法需要循环查找n次,而每次查找过程需要O(1)时间,删除最小值需要O(log n)时间,整体时间复杂度为O(n*log n)。
6.2 实际效率分析
程序的效率最终体现在是否能在最短时间内得到正确结果,实际效率受到的影响因素较多,同一程序,同一时间,在同一台机器上运行同样的程序,其执行时间可能有不小差别,但是实际的运行时间体现了一般意义下的实际效率,值得研究。
编写一般的Dijkstra最短路算法,和我们上面所写的程序进行对比,在Visual Studio 2005中运行,得到如图1结果。
可见,在图的顶点数比较多的情况下,优化后的算法优势明显,原始的算法已经很难接受了。
7 结论
单源最短路问题是一个经典问题,在交通运输、生产规划、人工智能等方面有广泛的应用。通过该文章的分析以及总结,我们对单源最短路问题已经得到了令人满意的解答。将时间复杂度从O(n2)降低至O(n*log n),极大的减少了运行时间,在实际应用中可以得到更好的应用,即使在一些实时系统,我们也可以运用文章描述的优化算法,算法的实际运行时间基本上在毫秒级别,保证了时间上的高效。通过STL标准模板库,使得算法的编写也变得很容易,即使在一些特殊环境中,也能得到应用。
对问题的优化探究,往往来自于对问题的深刻认识,对工具的灵活运用,以及多学科之间的综合分析,这是我们在科学研究中应该时刻铭记的。
参考文献
[1]Leiserson C E,Rivest R L,Stein C.算法导论(影印版)[M].2版.北京:高等教育出版社,2002:580-619.
[2]Sahni S.数据结构、算法与应用——C++语言描述[M].北京:机械工业出版社,2000:408-408.
[3]魏宝刚,陈越,王申康.数据结构与算法分析[M].浙江:浙江大学出版社,2004:224-227.
[4]陈媛,何波,涂晓红,等.算法与数据结构[M].北京:清华大学出版社,2005:165-168.
[5]朱承学,李锡辉.数据结构(C/C++描述)[M].北京:中国电力出版社,2004:131-135.
[6]陈明.数据结构实用教程[M].北京:清华大学出版社,2004:143-144.
[7]Bondy J A,Murty U S R.图论以及应用[M].北京:科学出版社,1984.
[8]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1997.
关于课题学习最短路径问题的探究 篇8
最短路径问题的教学在初中教学中出现有几种类型, 频繁出现的主要在几何与函数知识点教学方面, 以学生能力提升为主, 教师应当在选择课题时注意此点, 采用便捷、灵活的计算方法和技巧, 优化教学方法, 提高学生解题的效率, 培养学生数学逻辑思维能力。
1.课题学习原则
课题学习属于新颖的学习方式, 课题学习课堂上教师需要对教科书或者是相同类型的课题、题型进行有效整合, 通过教师的教学引导, 综合运用各种解题方法对课题进行解决, 积累更多课题知识, 提高自主探究能力, 拓展学生学习交流, 引发更多学习创新方法, 课题学习有关特征主要有四种:主体性, 课题学习可以充分体现出学生在学习的过程中是要通过合作讨论、自主探索的学习方式, 才可以在解决数学问题有清晰的解题步骤和思考思维, 以问题作为出发点, 然后主动思考问题, 体现了学生主体地位突出;探究性, 课题学习教学需要教师引导学生对问题进行探究, 绝不可直接解答题目反而遏制了学生探究思维的开发, 必须要体现课题学习的探究性;综合性, 课题学习所涉及的内容比较广泛, 如果是在初中三年级的话, 学习最短路径问题就会涉及到整个初中数学知识体系, 包括的范围广, 或者还接触到其他学科中去, 体现课题学习的综合性强的特点;开放性, 课题学习不局限与教材的内容, 学习本来就具有融会贯通的思维能力, 没有持久不变的题目, 只有永恒的逻辑思维, 当遇到相类似的题型, 就需要学生使用解题技巧和数学理论知识结合起来, 教师亦当如此。
2.强化对“课题学习”理论的认识的理解
教师在进行“课题学习”的课堂之前, 帮助学生对各个类型的知识点进行回顾, 把相关的数学概念和定理整理归纳好, 思考各个类型知识点和问题的解决途径和技巧。同时, 教师也需要加固课题学习所涉及的数学知识点和教学的相应技巧与教学方法, 充分做好备课工作, 深刻认识到“课堂学习”的重要教学理念和实际的教学目标, 做好课堂的教学规划和改善课堂教学流程。
3.规划“课题学习”教学方案
此次“课堂学习”的教学内容是关于初中数学最短路径的问题, 教师需要根据学生所学过的知识内容进行规划后课堂教学的方案, 分配好各个知识点的最短路径问题在课堂上利用的时间, 知识点的难易程度、解题方法和教学方式会决定所耗费的时间长短。关于最短路径的问题教师首先收集好典型且具有意义性的题目, 并且了解如何进行解答。例如教师可以从蚂蚁沿正方体、长方体、圆柱、圆锥外侧面吃食, 其原理是线段之和最短的问题或者是数模、函数等方面进行收集相关的数学题目, 此外, 在题目中还需要对该知识进行拓展, 或者构思不同方式的题目, 拓展学生思维的界限, 教师还应强调由易到难的教学观念。
例如:
问题一、如图1, 要在河边修建一个水泵站, 分别向张村、李庄送水, 水泵站修在河边什么地方可使所用的水管最短。
此问题的要求就是要在直线上找到一个点, 这一点要使得直线同侧的两个定点到这点的距离之和要达到最短, 此题利用到“两点间的所有连线中, 线段最短”的理论来进行论证求解。除了这一题外还有其他相同类型的题目比如:蚂蚁的爬行问题, 如图2 是一个长方体木块, 已知AB=5, BC=3, CD=4, 假设一只蚂蚁在点A处, 它要沿着木块侧面爬到点D处, 则蚂蚁爬行的最短路径是多少?
这都属于最短路径的数学题目, 涉及到几何体的内容, 需要拆开的方式来求证。
问题二、数学知识点不仅仅只有这点, 还有关于几何方面的知识都有最短路径的探究:
如图3, AB是⊙O的直径, AB=2, OC是⊙O的半径, OC⊥AB, 点D在弧线AC上, 弧AD等于2 倍的弧CD, 点P是半径OC上的一个动点, 求AP+PD的最小值是多少?
这类型的题目需要结合到几何定理知识来求解。
教师在进行“课题学习”之前就需要对这些类型的题型完全把握好, 分析几何型和数形结合的问题, 理清解题的过程, 贯穿到哪些方面的数学定理、概论。结合到题目的难易程度或者知识点范围, 可以规划几个课时才可以解决, 制定明确的课堂流程。
4.利用教学方法促成“课题学习”教学
教师进行改善教学方法, 需要考虑到“课题学习”的主要特点来制定相应的教学方法, 就从它有主体性的特点来思考。教师可以展开小组合作讨论活动, 对最短途径问题进行探索, 为学生提高情境教学的环境, 提高学生课题学习课程的兴趣, 培养学生探索思维, 创新思维。例如在“问题一”中的第二类型的题目上展开小组讨论活动, 由于问题难度不算高, 教师可以一两人为一小组, 提倡学生利用上现有制作的数学模型展开讨论, 可以把制作好的长方体标记好有字母的标记, 让学生进行思考探索, 学生在探索思考过程中, 加上动手的操作, 就可以理解到如何进行解决问题。从小组讨论的教学方式来说, 极好地体现了“课题学习”教学的有效性。此外, 教师还应该采用数形结合法来教学, 图像的表达可以把抽象的数学条件, 诱导出形象的图像, 加快学生解题速度。
结语:综上所述, 数学问题万变不离其宗, 所有题目或者题型的变化, 都可以找到问题的突破口, 结合数学理论知识就可以把问题解答, 课题学习的关键作用使得学生在学习过程中对知识点的回顾, 加深对知识的理解, 同时可以培养学生的创新思维和探索精神。
参考文献
[1]叶澜.《“新基础教育”探索性研究报告集》, 三联书店, 1996年版
[2]戴向阳.动点下的线段最值解法探微.中学数学教学参考, 2014 (3)
[3]朱启州, 张兴侠.一道课本例题的教学探讨.中学数学教学参考, 1999 (4)
最短路问题 篇9
1.“规划求解”工具
1.1 关于“规划求解”
Microsoft Excel的“规划求解”工具取自于德克萨斯大学奥斯汀分校的Leon Lasdon和克利夫兰州立大学的Allan Waren共同开发的非线性最优化代码。“规划求解”是Execl中的一个加载宏, 借助规划求解, 可求得工作表上某个单元格中的公式的最优解。
1.2 如何加载“规划求解”
安装Office的时候, 系统默认的安装方式不会安装宏程序, 需要用户根据自己的需求选择安装。加载“规划求解”宏的步骤如下:
1) 打开Excel文件, 在“工具”菜单上, 单击“加载宏”。
2) 在弹出的对话框中的“可用加载宏”列表, 选定“规划求解”, 然后单击“确定”。单击“确定”以后, “工具”菜单下会出现一项“规划求解”。
2. 最短路问题
引例 (最短路问题) 如图1所示, 用点表示城市, 现有v1、v2、v3、v4、v5、v6、v7、v8共8个城市。点与点之间的连线表示城市间有道路相连。连线旁的数字表示道路的长度。现计划从城市v1到城市v8铺设一条天然气管道, 请设计出最小价格管道铺设方案。
本例的实质是求从城市v1到城市v8的一条最短路。
定义1给定一个赋权有向图D= (V, A) , D中每一条边aij=
又若P*是D中从vs和vt的一条路, 且满足
则称P*为从vs和vt的最短路, w (P*) 为从vs和vt的最短距离。
在一个图中D= (V, A) 中, 求从起点到终点的最短路和最短距离的问题称为最短路问题。
定义2设D= (V, A) 是一个有向图, 以点v为起点的边数称为点v的出度, 记为deg+ (v) ;以v点为终点的边数称为点v的入度, 记为deg- (v) ;点v的出度与入度的差deg+ (v) -deg- (v) 称为点v的进出度数和, 记为d (v) 。
3. 利用Excel“规划求解”求解最短路问题
3.1 用Excel求解最短路问题的原理
设决策变量为xij, 当xij=1, 表示最短路P*通过边
3.2 最短路模型
约束条件:0燮d (vi) 燮1;
d (vi) 为整数;
1燮i燮n
3.3 用Excel求解最短路问题
1) 在Excel上建立模型
以引例为例, 在Excel上建立模型图2所示, 决策变量xij与进出度数和d (V) 的初始值为0。如图2所示。
2) 添加约束条件
在“工具”菜单上, 单击“规划求解”, 弹出“规划求解参数”对话框, 在弹出的对话框中, 设置目标单元格C19、可变单元格D2至D16和约束条件, 如图3所示。
3) 模型求解
点击“规划求解参数”对话框中的“求解”选项, 得出结果如图4所示。
图4中, 变量xij的值为1的边就是所求最短路P*通过的边, 即
最短路距离为12。
参考文献
[1]邓成梁.运筹学的原理和方法[M].武汉:华中理工大学出版社, 2001.
[2]顾运筠.Excel规划求解的两类应用[J].计算机应用于软件, 2005, (1) .
[3]陈生萍, 田宏秀, 黄天强.Excel规划求解在决策分析中的应用[J].吉首大学学报, 2006, (2) .
利用轴对称变换求最短路径问题 篇10
解法:作点B关于直线l的对称点B′, 连结AB′, 与直线l相交于点P, 连结BP。骑马少年沿折线A-P-B的路线行走时路程最短。
证明:如图, 在直线l上任取一点P′ (与点P不重合) , 连结AP′, BP′, B′P′.
由轴对称的性质知, BP=B′P, BP′=B′P′
∴AP+BP=AP+B′P=AB′, AP′+BP′=AP′+B′P′
在△AB′P′中, AB′<AP′+B′P′
∴AP+BP<AP′+BP′。
即AP+BP最短。
“最短路径问题”的原型就来自于“饮马问题”, 要解决这一问题, 是利用作对称点把折线问题转化成直线问题, 它离不开构建与转化“两点之间, 线段最短”的数学公理。在日常生活、工作中, 也经常会遇到有关行程路线的问题, 我们把这类求近道的问题统称最短线路问题, 出题者通常以直线、角、三角形、特殊四边形、坐标轴等对称图形为背景。本文就在“最短路径”中探寻一番, 举例分析, 帮助同学们学习。
【迁移与拓展】
1.一点两线 (相交) 解决周长最短。
如图所示, 点P为一处马厩, ON为草原的边缘 (下方为草原) , OM为一条河流。清晨, 骑马少年要从马厩牵马先去草地吃草, 然后到河边饮水, 最后再回到马厩。请帮他设计一条最近的行走路线。
解析:依据两点之间线段最短, 可分别作点P关于OM, ON的对称点分别为P1、P2, 连P1P2交OM、ON于点A、B。此时ΔPAB的周长PA+PB+AB=P1P2为最小。 (证明略)
2.二点两线 (相交) 解决周长最短。
如图所示, P为帐篷, Q为马厩, 骑马少年某天要从马厩牵出马, 先到草地边ON的某一处牧马, 再到河边OM饮水, 然后回到帐篷, 请你帮他确定这一天的最短路线。
解析:如图分别作点P、Q关于OM, ON的对称点为P′、Q′, 连P′Q′, 交OM、ON于点A、B。此时四边形PABQ的周长PA+AB+BQ+PQ=P′Q′为最小。 (证明略)
3.一点两线 (相交) 解决距离之和最短。
如图所示, A为马厩, 骑马少年某天要从马厩牵出马, 先到河边OM的某处P饮水, 再到草地ON边某处B牧马, 请你帮他设计一条路线, 使AP+BP最短。
解析:如图作点A关于OM的对称点A′, 过A′作ON的垂线交OM于P, 交ON于B, 则A→P→B为最短路线。 (证明略)
【应用与延伸】
1.如图, 一次函数y=kx+b的图象与x、y轴分别交于点A (2, 0) , B (0, 4) , ?O为坐标原点, 设OA、AB的中点分别为C、D, P为OB上一动点, 求PC+PD的最小值, 并求取得最小值时P点坐标。
解析:作点C关于y轴的对称点C', 连接C'D, 交y轴于点P则C'D=C'P+PD=PC+PD。C'D就是PC+PD的最小值, 连接CD, 则CD=2, CC'=2。在直角△C'CD中, 根据勾股定理C'D=2求直线C'D的解析式, 由C' (-1, 0) , D (1, 2) 得y=x+1当x=0时, y=1, 则P (0, 1) 。
2.如图, 已知直角梯形ABCD中, AD∥BC, AB⊥BC, AD=2, BC=DC=5, 点P在BC上移动, 则当PA+PD取最小值时, △APD中边AP上的高为_____。
3.如图, 已知⊙O的直径CD为4, ∠AOD的度数为60°, 点B是弧AD的中点, 在直径CD上找一点P, 使BP+AP的值最小, 并求这个最小值。
解析:作点B关于AD的对称点B', 过点B'作B'E⊥AB于点E, 交AD于点F, 则线段B'E的长就是BM+MN的最小值在等腰Rt△AEB'中, 根据勾股定理得到:B'E=4。
最短路问题 篇11
关键词：最短路径 Java Johnson算法 算法实现
最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：确定起点的最短路径问题。即已知起始结点，求最短路径的问题；确定终点的最短路径问题。与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题；确定起点终点的最短路径问题。即已知起点和终点，求两结点之间的最短路径；全局最短路径问题——求图中所有的最短路径。
一、最短路径算法的实现策略
用于解决最短路径问题的算法被称作“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。
所谓单源最短路径问题是指：已知图G＝（V，E），我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。
首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。
笔者以3Dijkstra算法为例，Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它计算的节点很多，所以效率低下。Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合，以E表示G中所有边的集合。(u,v)表示从顶点u到v有路径相连，而边的权重则由权重函数w:E→[0,∞]定义。因此，w(u,v)就是从顶点u到顶点v的非负花费值（cost），边的花费可以想象成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(例如最短路径)。这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。
二、代码实现
importjava.util.Scanner;
publicclassMain{
privatestaticintn;//G图中的顶点个数
privatestaticint[]distent=null;//最短路径长度
privatestaticint[]previous=null;//前驱顶点集合
publicstaticvoiddijkstra(intv,int[][]a,int[]dist,int[]prev){
//单源最短路径问题的Dijkstra算法
intn=dist.length-1;//问题的规模，0号元素未使用
if(v<1||v>n)return;//源不在图中，则返回
boolean[]s=newboolean[n+1];//判断点是否在集合S中
//初始化
for(inti=1;i<=n;i++){
dist[i]=a[v][i];//源到点i的最短特殊路径长度
s[i]=false;//点i现在不在集合s中
if(dist[i]==-1)
prev[i]=0;//若最短路径长度恒为-1表示无通路，则让点i的前驱点为0
else
prev[i]=v;//有通路则让点i的前驱指向源
}
dist[v]=0;
s[v]=true;//源放入集合s中
for(inti=1;i inttemp=Integer.MAX_VALUE; intu=v; //在剩下的点中除了没有通路的点中找到最容易到达的，并把最容易到达的放入u中 for(intj=1;j<=n;j++){ if((!s[j])&&(dist[j] u=j; temp=dist[u]; } } s[u]=true;//u放入s集合中 for(intj=1;j<=n;j++){ if((!s[j])&&(a[u][j])!=-1){ //源到点j通过点u的最短特殊路径长度newdist intnewdist=dist[u]+a[u][j]; if(newdist //或当此路不同时执行循环中的语句 dist[j]=newdist;//更新源到点j的最短长度，dist[j]减少了 prev[j]=u;//点j的前驱指向点u } } } //System.out.println("从1出发到2、3、4、5的最短路径依次为:"); for(intk=2;k System.out.print(dist[k]+""); } System.out.println(dist[n]); } /?鄢?鄢 ?鄢@paramargs ?鄢/ publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstub intv=1; Scannersc=newScanner(System.in); Stringline=sc.nextLine(); n=Integer.parseInt(line); distent=newint[n+1]; previous=newint[n+1]; int[][]a=newint[n+1][n+1]; for(inti=1;i<=n;i++){ line=sc.nextLine(); String[]str=line.split(""); for(intj=1;j<=str.length;j++){ a[i][j]=Integer.parseInt(str[j-1]); } } dijkstra(v,a,distent,previous); intx=previous[5]; inty=previous[x]; intz=previous[y]; //System.out.println("从1到5最短路径经过的点为："); System.out.println(z+""+y+""+x+""+"5"); } } //输入测试值 /?鄢5 -110-130100 -1-150-1-1 -1-1-1-110 -1-120-160 -1-1-1-1-1?鄢/ //运行结果 /?鄢10503060 1435?鄢/ 三、结束语 本文系统讲述了递归的基本概念、使用递归进行程序设计的好处以及如何设计递归程序，结合Hanoi塔问题、N皇后问题等经典实例介绍了通过降阶、分治及回溯构造递归函数的一般化方法，并对递归使用过程中可能存在的问题进行了说明。总的来说，递归作为一种重要的程序设计方法可使得编码清晰易懂，但存在运行效率较低的问题，在实际应用当中，建议仅当传统方法不方便求解时使用递归。 参考文献： [1]王晓东.计算机算法设计与分析[M].北京：电子工业出版社,2007. 1 问题描述及建模 设G=(V,A)为有向网络图，V={v1,v2,…,vn}为节点集合，A={aij|aij=(vi,vj),vi,vj∈V}为有向边集合。R为资源种类集合，|R|≥1。Wr为资源r(r∈R)的消耗量上限。对G中的每一条有向边aij∈A，定义长度为cij(cij≥0)，资源消耗向量为wij={w1ij,w2ij,…,wrij}，且wrij≥0(∀r∈R)。令P为G中的一条路径，A(P)为组成路径的有向边集合，定义路径的长度路径的资源消耗向量则约束最短路问题可以描述为在指定的两个节点之间寻找一条路径P，使得C(P)最小且 为求解该问题，不妨设v1和vn分别代表起点和终点。并引入决策变量xij，若有向边aij包含在路径中，xij=1;反之，xij=0。那么，问题可以表示为： 式(1)为目标函数，要求路径的长度最小。式(2)～式(4)为流平衡约束。式(5)为资源消耗约束，要求路径的资源消耗量不得超过规定的上限。式(6)为变量取值约束。 2 求解算法 2.1 相关定义 介绍标号设定算法之前，先给出如下定义： 定义1令Pi为由起点至节点vi的一条代价为c(Pi)和资源消耗向量为w(Pi)的路径，路径Pi的标号L(Pi)=(c(Pi),w1(Pi),…,wr(Pi))。节点的不同标号对应着从起点到该节点的不同路径。 定义2令L(Pi)和L(Pi’)为自起点到节点vi的两条不同路径Pi和Pi’各自对应的标号。若c(Pi)≤c(Pi’)，w1(Pi)≤w1(Pi’)，…，wr(Pi)≤wr(Pi’)，且两个标号不相等，称L(Pi)支配L(Pi’)。 定义3若对∀r∈R，路径P的资源消耗量不大于Wr，即称路径P为可行路径，称其对应的标号L(Pi)为可行标号。 定义3令节点vi的可行标号为L(Pi)，且未被节点的其它标号支配，称L(Pi)为有效标号，称其对应的可行路径Pi为有效路径。 定义5令节点vi的标号为L(Pi)，对于有向边aij∈A，扩展标号L(Pi)就是生成节点vj的标号L(Pj)=(c(Pi)+cij,w1(Pi)+w1ij,…,wr(Pi)+wrij)，记为L(Pi)aij。 2.2 算法流程 基于上述定义，标号设定算法的基本思想是遍历生成G中所有节点的有效标号。对节点vi，令Ui为所有标号的集合，Di为已扩展标号的集合。初始化起点的标号为(0,…,0)，其它节点的标号集合为空。算法迭代的由集合中选择标号L(Pi)，将其加入Di，并沿有向边aij扩展L(Pi)生成L(Pj)，若L(Pj)为有效标号，则将其加入Uj，并删除Uj中被L(Pj)支配的标号，直至算法的关键步骤为选择标号、标号扩展和标号支配检查。 1、选择标号：为提高算法寻优效率，本文提出一种凝聚函数以选择将被扩展的标号。 定义6令L(Pi)为节点vi的标号，L(Pi)的凝聚函数F(Pi)=α1c(Pi)+α2w1(Pi)+…+αr+1wr(Pi)。其中，α1,…,αr+1为权重系数。 算法由集合中选择凝聚函数值最小的标号进行扩展。 2、标号扩展：将节点vi的标号L(Pi)沿有向边aij∈A扩展，生成节点vj的标号L(Pj)。并检查L(Pj)是否为可行标号，即对∀r∈R，是否满足wr(Pi)+wrij≤Wr。 3、标号支配检查：判断L(Pj)是否被Uj中的标号支配。若被支配，删除该标号;反之，保存L(Pj)至Uj，并将Uj中被L(Pj)支配的标号删除。 得标号设定算法的具体步骤为： 步骤1初始化，令 步骤2判断是否为空集。若是，算法结束，根据vn的有效标号可以获得满足资源约束的最短路径;否则转到步骤3。 步骤3选择标号L(Pi)，满足 步骤4遍历aij∈A,L(Pj)=L(Pi)aij，若L(Pj)为可行标号，转到步骤5。遍历结束，转到步骤6。 步骤5若L(Pj)被Uj中的标号支配，删除该标号;否则，L(Pj)为有效标号，Uj=Uj∪{L(Pj)}，并将Uj中被L(Pj)支配的标号删除。转到步骤4。 步骤6 Di=Di∪{L(Pi)}，转到步骤2。 3 实验与结果分析 3.1 实验 为了验证本文提出算法的有效性，随机生成三个有向网络图作为算例进行实验。算例的相关统计数据如表1所示。其中，|V|、|A|和|R|分别表示节点数量、有向边数量和资源种类数量。 为比较算法性能，引入选择字典序最小的标号进行扩展的标号算法[6](LLSA)，将其与本文算法(ALSA)一起求解上述算例。 计算平台：Intel 3.00 GHz CPU+1G RAM+Win XP。采用MATLAB编码。 4.2 结果分析 表2记录了算法求解结果。其中，S为最优解的长度，P为标号扩展次数，T为计算时间，单位为s。可以看出，网络规模较小时，两种算法均可在较短时间内生成满足资源消耗约束的最短路径;但随着网络规模的扩大，ALSA的计算时间和标号扩展次数逐渐少于LLSA。可见，ALSA的算法性能优于LLSA;引入凝聚函数能够有效加快算法收敛速度、减少计算量。 5 结论 约束最短路问题是网络分析中的一个重要问题，被应用于现实生活中的诸多领域。本文采用标号设定算法求解约束最短路问题，设计一种凝聚函数以确定标号扩展次序，避免生成未来将被支配的标号，达到改善算法性能的目的。实验结果表明，改进的标号设定算法能够有效求解约束最短路问题。 摘要：为了提高标号设定算法求解约束最短路问题时的寻优效率,引入一种凝聚函数,综合考虑长度因素和资源消耗因素以确定标号扩展次序,避免生成将被支配的标号,达到改善算法收敛速度、减少计算量的目的。实验结果表明:改进的标号算法能够有效求解约束最短路问题。 关键词：约束最短路径,标号设定,凝聚函数,有效标号 参考文献 [1]罗宏伟,吴斌,况中林,等.快速启发式多约束优化路径算法研究[J].自动化与仪表,2008,9(1):5-8. [2]胡耀民,刘伟铭.多约束最短路径模型与求解[J].湖南科技大学学报:自然科学版,2010,25(1):87-90. [3]何方国,齐欢,范琼.有约束的随机最短路问题模型及算法[J].武汉理工大学学报(交通科学与工程版),2008,32(6):1125-1128. [4]宿洁,韩强.一类多约束最短路问题的模拟退火算法[J].计算机工程,2004,30(19):21-22. [5]王莹,刘军,苗建瑞.客运专线乘务交路计划编制的优化模型和算法[J].铁道学报,2009,31(1):15-19. [6]Boland N,Dethridge J,Dumitrescu I.Accelerated label setting algorithms for the elementary resource constrained shortest path problem[J].Operations Research Letters,2006,34(1):58-68.最短路问题 篇12