最短路线问题

最短路线问题（精选10篇）

最短路线问题 篇1

2009年北京市中考题最后一题第 (3) 问是一个最小值问题, 关于本问题的解法引起同行们的兴趣。一致认为本题是“最短路线问题”的拓展, 我们曾从记忆储存中提取多种几何模型研究解决运动路程的最短距离, 如“两点之间线段最短”、“饮马问题”……但在指定路线 (一般为折线) 进行变速时, 如何才能使运动的时间最短给解答问题造成困难, 经过深度思考现给出两种解法, 供同行参考。

试题第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°角的直角三角形的基本图形, 使问题圆满解决。本法充分体现了几何法的直观形象性。

解法二 (代数法) 求问题的最小值用到了判别式法, 虽然解题过程繁杂, 但最后能直接求出G的坐标, 问题也得到了解决。本法充分体现了代数方法的抽象性。通过以上两种解法, 使我们对最短路线问题有了深度的认识。

最短路线问题 篇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

同学们，请仔细观察一下图1，你觉得它像什么图形？对了，它像一个用数组成的等腰三角形，

你能发现这些数之间的规律吗？其实，最本质的特征是，数1在两条腰上，而其余的数则等于其“肩”上的两个数之和，如第六层的第二个数5，就等于其“肩”上的两个数1、4的和.

这个三角我们叫杨辉三角，它出现在我国南宋数学家杨辉编著的《详解九章算法》一书中，杨辉指出这个方法出于《释锁算术》.在欧洲，这个三角被认为是法国数学家、物理学家帕斯卡首先发现的，被称为帕斯卡三角，

下面让我们在解决一些走最短路线的问题中找一找杨辉三角.

据说杨辉研究数学达到了如醉如痴的境界，他也非常喜欢和友人们一起研究数学问题.一天，他的一位友人甲邀请他一起讨论数学问题.杨辉有一张地图，如图2，地图上标明了从杨辉家（A）去友人甲家（B）的每条路线.杨辉发现地图上的好几条到友人甲家的路线都是最短的，而且都不会重复.同学们知道一共有几条最短路线吗？

想要搞清楚路线，先得确定从A点到B点的最短路线到底是多长，然后确定走的方向，为了保证不走“回头路”，只能向右或向下走.

有些同学很快找出了从A点到B点的

通过验证，我们确信这六条路线都是从A点到B点的最短路线.如果按照上述方法找，它的缺点是不能保证找出所有的最短路线.当然如果图形更复杂些，做到不重复也是很困难的.

那么，解决这样的问题是否有规律可循？让我们一起往下看.

1.看C点：从A点到C点，只有一条最短路线，同样道理，从A点到D点、从A点到E点、从A点到H点也都只有一条最短路线.

我们把数字“1”分别标在C、D、E、H这四个点上，如图2.，的三条最短路线.

现在再让我们来观察图2.如果我们把图2加上对角线，再把它旋转一下，就会发现它是杨辉三角的一部分，如图3.

这样，我们就可以运用杨辉三角来解决这种问题，既简单又准确.让我们再来试一试，

图4是一个由18个相同的小等腰直角三角形拼成的平行四边形，有一只蚂蚁从A点出发，沿图上的线段爬行到曰点，请求出这样爬行的最短路线有几条，

同学们能根据杨辉三角解决这个问题吗？

最短路问题的位势法 篇4

在公交网络的查询系统中, 需要查询两站点之间最节省的乘车方式。该问题可以转化为求解交通网络中两点之间的最短路问题。目前的最短路问题的算法[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.

最短路线问题 篇5

关键词：初中数学；最短路径；转化；对称；展开图

中图分类号：G633.6 文献标识码：A 文章编号：1009-010X（2016）18-0055-02

“宇宙之大，粒子之微，火箭之速，化工之巧，地球之变，日用之繁，无处不用数学。”正如前辈所说，数学与我们的生活息息相关，数学的脚步无处不在。随着课改的深入，数学更贴近生活，更着眼于解决生产、经营、建筑中的问题，于是就出现了为省时、省力而希望寻求最短路径的数学问题。其问题主要依据是“两点之间，线段最短”、“点到直线上的所有线段中，垂线段最短”以及利用轴对称的性质、平面展开图等知识来解决，特别是要用轴对称进行转换以及将空间问题转化为平面问题来解决初中数学中的最短路径问题。初中数学中最短路径问题，生动地体现了数学来源于生活，并用数学解决现实生活问题的数学应用性。在初中数学中有关最短路径的问题可分为点点之间的最短路径问题、点线之间的最短路径问题以及立体图形展开图中的最短路径问题。

一、点与点

如图，点A到点B的最短距离为：线段AB的长度。其中的数学道理我们都知道是“两点之间线段最短”。由此也就引出了三角形的三边关系：三角形两条边的和大于第三条边。

二、点与线

如图，想在河堤两岸搭建一座桥，图中搭建方式中，最短的是PB，理由垂线段最短。

三、两点一线：分为以下两种情况

情况一：两点在一条直线异侧

例：已知：如图，A，B在直线l的两侧，在l上求一点P，使得PA+PB最小。

解：连接AB，线段AB与直线l的交点P，就是所求。

（其依据：两点之间线段最短.）

情况二：两点在一条直线同侧

例：如图所示，要在街道旁修建一个奶站，向居民区A、B提供牛奶，奶站应建在什么地方，才能使从A、B到它的距离之和最短。【分析】只有A、P、B在一直线上时，才能使AP+BP最小。作点A关于直线“街道”的对称点A′，然后连接A′B，交“街道”于点P，则点P就是所求的点。

四、一点两线（一点在两相交直线内部）

例：已知：如图A是锐角∠MON内部任意一点，在∠MON的两边OM，ON上各取一点B，C，组成三角形，使三角形周长最小.

【分析】：当AB，BC和AC三条边的长度恰好能够体现在一条直线上时，三角形的周长最小。

作法：分别作点A关于OM，ON的对称点A′，A″；连接A′，A″，分别交OM，ON于点B、点C，则点B、点C即为所求。

五、两点两线

例：如图：C为马厩，D为帐篷，牧马人某一天要从马厩牵出马，先到草地边某一处牧马，再到河边饮马，然后回到帐篷，请你帮他确定这一天的最短路线。

作法：1.作点c关于直线OA的对称点点F；

2.作点D关于直线OB的对称点点E；

3.连接EF分别交直线OA、OB于点G、H；

则CG+GH+DH最短。

六、立体图形展开图中的最短路径问题

1.在圆柱中可将其侧面展开求出最短路程

将圆柱侧面展成长方形，圆柱体展开的底面周长是长方形的长，圆柱的高是长方形的宽。可求出最短路程。

例：如图所示，是一个圆柱体，ABCD是它的一个轴截面，AB=8/π，BC=3，一只蚂蚁，要从A点爬行到C点，那么最近的路程长为____。

【分析】：我们要求蚂蚁爬行的最短距离，需将圆柱的侧面展开，进而根据“两点之间线段最短”得出结果。

解：将圆柱体展开，连接A、C，AC长即为所求。

2.在长方体中可将其侧面展开求出最短路程

例：有一长、宽、高分别是5cm，4cm，3cm的长方体木块，一只蚂蚁要从长方体的一个顶点A处沿长方体的表面爬到长方体上和A相对的顶点B处，则需要爬行的最短路径长为__cm。

【分析】：将此长方体展开，在平面内，利用“两点之间线段最短”和“勾股定理”求两点A、B间的线段长，即可得到蚂蚁爬行的最短路径。

解：因为平面展开图不唯一，所以我们要分三种情况进行讨论并比较大小，从而确定出最短路径。

（1）展开前面、右面，由勾股定理得AB²=（5+4）²+3²=90；

（2）展开前面、上面，由勾股定理得AB²=（3+4）²+5²=74；

（3）展开左面、上面，由勾股定理得AB²=（3+5）²+4²=80：

总之，数学来源于生活，同时数学也服务于生活。在解决初中数学中的最短路径问题时，我们需要用数学中的“转化思想”将生活中的问题转化为“两点之间线段最短”的问题或运用轴对称的性质，通过等线段代换，将所求路线长转化为两定点之间的距离。我们还应注意：利用轴对称解决最值问题应注意题目要求，根据轴对称的性质、利用三角形的三边关系，通过比较来说明最值问题是常用的一种方法。

单源最短路问题高效算法探究 篇6

关键词：最短路,迪杰斯特拉,数据结构,标准模板库,优化算法

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.

关于课题学习最短路径问题的探究 篇7

最短路径问题的教学在初中教学中出现有几种类型, 频繁出现的主要在几何与函数知识点教学方面, 以学生能力提升为主, 教师应当在选择课题时注意此点, 采用便捷、灵活的计算方法和技巧, 优化教学方法, 提高学生解题的效率, 培养学生数学逻辑思维能力。

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)

最短路线问题 篇8

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=上的权为w (aij) =wij, 又给定D中的一个起点vs和终点vt, 设P是D中从起点vs和vt终点的一条路, 则定义路P的权是P中所有边的权之和, 记为w (P) , 即

又若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*通过边;当xij=0, 表示最短路P*不通过边;最短路P*中, 除起点和终点之外, 每个点的进出度数和为0, 起点为1, 终点为-1。目标函数为各边权数与对应决策变量xij的乘积之和的最小值。

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) .

利用轴对称变换求最短路径问题 篇9

解法:作点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。

最短路线问题 篇10

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.