动态最短路径

动态最短路径（精选11篇）

动态最短路径 篇1

摘要：针对动态拓扑网络的最优路径规划中存在的问题,研究了最短路径搜索算法的快速实现技术,提出了一种启发式快速最优路径规划算法。在分析经典迪杰斯特拉最短路径搜索算法和A*启发式搜索算法的基础上,利用椭圆曲线参数设定启发函数初始值,进一步缩小搜索范围。采用二叉堆结构来实现路径计算过程中优先级队列的一系列操作,从而提高了算法的执行效率。仿真试验结果表明该算法具有良好的性能。

关键词：最短路径,A*算法,二叉堆,动态拓扑

0 引 言

随着GPS(global position system)的应用领域越来越广,船舶、车辆等交通系统在利用知道自己位置的前提下进行通信显得方便易行。如果把每个实体看成是一个节点,实体间的可达通信看成是一条边,则两点间通信问题就转化为求解图的最短路径问题。

在求最短路径的方法中,目前国内外一致公认较好的算法是Dijkstra算法,然而Dijkstra采用遍历搜索,得到的是所有目标节点的最短路径,属一对多问题,不能有效解决两点间的点对点通信问题,为此,研究人员提出几十种不同的优化算法,效果较好的算法有TQQ (graph growth with two queues) ,DKA(the Dijkstra’s algorithm implemented with approximate buckets) ,DKD ( the Dijkstra’s algorithm implemented with double buckets)[1,2],可是这些算法都是针对静态网络拓扑结构的,不能有效解决动态网络的实时性要求高、规模庞大、移动节点的处理能力和系统的存储资源有限等问题。

而A*启发式[1]算法能适应网络的变拓扑特性,它采用路径规划思想,每次探寻到离目标节点更近的目标节点。选用恰当的启发函数便可使搜索范围限制在一个期望的区域,快速找到一个最优解。为此,本文提出ASPA(A* heuristic shortest path algorithm)算法,使搜索范围局限在一个椭圆曲线范围内。实验数据表明,该算法可以减少扩展的节点数目,节约计算时间,提高运算效率。

1 A*优化算法

1.1 A*算法简介

A*算法是目前广为流行的路径规划启发式算法[1],与Dijkstra算法不同之处在于它优先考虑最有希望的节点(具有最小估价函数的节点),使用了启发式信息来减少搜索空间,提高效率。定义节点的启发式估价函数为f(x) = g (x) + h(x),f (x)是假设是从起始节点S 出发,经过节点X到达目标节点T的最小代价值估计值。估价函数f (x) 由以下两部分所组成:一部分是从起始节点S 到达节点x的最小代价,记为g (x);另—部分是从节点x 到目标节点的最小代价,记为h(x)。实际过程中我们使用f (x) =LSX+dis(X,x)+ h(x),式中LSX是从原点S到当前节点X的实际最小费用,dis(X,x)是从当前节点X到扩展节点x的直线长度,h(x)是扩展节点x到目标节点T的路径长度,dis(X,x)+h(x)是启发式函数。

1.2 启发函数上限值

文献[3]利用最小角度求启发函数初始值,然而对于动态的网络拓扑结构,这种方法获得初始值是非常困难的。本文以船舶导航系统为例,设定启发函数的初值为2a,原理如下:如图1所示,节点S要和D通信,假设S知道t0时刻T的位置在(XT ,YT),其平均移动速度为v,则在t1时刻,节点T应该在以(XT ,YT)为圆心,以r=v(t1 -t0)为半径的圆内。这里设r=(2a-2c)/2=a-c,根据ITU-RM建议标准[4],速度最快的船舶通信报告周期为2s,那么上限值2a≈dis(X,T)+2r= dis(X,T)+4v,其中,dis(X,T)是X和T的直线距离;v是船舶的航行速度,即扩展节点的航行速度,取单个节点速度的平均值;加号“+”是考虑最坏时的情况,即v背离S的方向,这样从起点开始,每次扩展一个节点,每个扩展节点根据节点速度和离目标节点的距离来动态调整上限值,这样可以使搜索以限制在椭圆曲线范围内的方式不断逼近目标节点。该方法适用所有移动通信网络求启发函数初始值,具有一般性。

1.3 优化算法简要描述

有了启发函数的初始值,对每个向前搜索的扩展节点x如图1所示,判断以下二种情况:

1) dis(X,x)+h(x)≤2a,x点在椭圆曲线范围以内,如果x点是所有椭圆曲线范围节点中最小者,选定x加入到永久标记节点,LSx=LSX+LXx,当前节点扩展到x节点。剩余满足条件的所有节点,标记为临时标记节点,加入到二叉堆序列,反过来讲,二叉堆里面元素也都是临时标记节点。

2) dis(X,x)+h(x)>2a,丢弃x,说明目标不可达。由于节点的离开、故障、睡眠等原因,X没有可达邻居节点,这时向源节点S报告不可达信息,避免无效的通信探询开销。

2 ASPA算法实现

2.1 数据结构设计

(1) 网络结点数据结构 (Node_Inf)

NodeID:节点编号;Latitude:结点纬度;Longitude:结点经度;AdjacentNum:邻居节点个数;*AdjacentIndex:邻居节点索引指针。

(2) 邻居节点索引表(AdjacentIndex)

NodeID:索引节点;A rcID:索引弧段。

(3) 弧数据结构 (Arc_Inf)

A rcID:弧段编号;FirstNode:弧的起点编号;EndNode:弧的终点编号;ArcLength:弧的长度。

(4) 最短路径结点数据结构(ShortNode)

HeapID:此结点在堆中的编号;*PreNode:最短路径中此结点的前一结点;ShortestLen:源点到此结点的最短路径长度。

用这个特殊的网络数组来存储节点数据,数组类似于邻接矩阵的压缩存储方式,其内容则具有邻接多重表的特点,即一条边以两顶点表示。AdjacentIndex则相当于一个记录了顶点出度的索引表,通过它可以很容易地得到此顶点的出度和与它相连的第一条弧段在弧段数组中的位置,这样就可以在顶点已编号的情况下以最快速度搜索出与任意节点相连的边。建立Arc_Inf和AdjacentIndex两个表以及对Arc_Inf的排序其时间复杂度共为O(2n+lg(n))。

2.2 ASPA算法实现

堆排序(heap sort)的基本操作有:

· ModiyHeap (S):首先将集合S调整成完全二叉树,并设定其根结点具有最小关键字。

· InsertHeap (x,S):将元素x插入集合S,并调用ModiyHeap将其调整成完全二叉树。

· SelectHeap (S):选取具有最小关键字的元素,并调用ModiyHeap将其调整成完全二叉树。

算法的步骤如下:

1) Initialize 操作:首先搜索与源结点SourceNode 相邻的结点Adjacent [AdjacentNum],然后初始化Arc_Inf中所有邻结点的权值ArcLength[i],计算启发函数初始值2a。

2) Initialize源节点长度:计算dis(S,i)+ h(i),不大于2a转3),大于2a的转5)。

3) 选取最短距离结点操作:SelectHeap,使得ShortestLen[i]= min{dis(S,i)+ h(i), i∈Adjacent [AdjacentNum] },ShortestLen[i]加入ShortNode表,设置链接指针PreNode=Node ID[i]

4) 计算源点到当前节点最短长度:选取当前节点NodeID[i]的扩展邻节点NodeID[j],ShortestLen[j]= min{ dis(S,j)+dis(j,T)},dis(S,j)+dis(j,T)≤2a,j∈Adjacent[i]。计算ShortestLen[j]= ShortestLen[i]+dis(S,j)+dis(j,T),ShortestLen[j] 加入到ShortNode, 当前节点转移到j节点,PreNode=NodeID[j]。

5) 扩展节点约束:如果NodeID[j]邻节点dis(X,x)+h(x)>2a,则SelectHeap,从临时标记节点开始新一轮搜索,SelectHeap遍历完毕转7),否则转6)。

6) 重复步骤2),直至Node [j]=DesNode。

7) 结束。

3 算法仿真和分析

3.1 算法仿真

以网络仿真软件NS-2(Network Simulator)作为仿真平台。由源节点发出的探测包到达目的节点后返回,从返回的数据包可检测到到达目的节点的准确度及往返花费的时间,也可以分析数据包转发路径,得到临时标记节点的扩展数目。平面算法指的是类似GPRS等以平面图为基础拓扑的其它算法,表1统计数据表明,扩展节点数可以减少到改进前的54%,程序运行的时间大约为改进前的71 %。

3.2 算法复杂度分析

Dijkstra算法采用广度优先的搜索策略,在访问了网络中所有的节点后,最终生成从源点到其余各点的最短路径树。算法的运行时间为O(N2)。如果Dijkstra算法搜索范围可以看成是以X为圆心的圆的面积S=4πr2,r=dis(S,T),那么启发式椭圆曲线搜索范围可看成椭圆面积S =πab≈πr2/4,圆和椭圆面积之比大约4∶1, 即二者扩展节点数目相差4倍左右。从仿真实验扩展节点数目的减少量上来看,可以说明这一点。

4 结束语

本文在分析迪杰斯特拉(Dijkstra)演变算法的基础上,提出了基于椭圆曲线的启发式搜索算法,该算法适用于变拓扑结构的网络间求最短路径问题,具有一般性。从应用于船舶无线自组网络通信系统的实际情况看,该算法表现出良好的性能。关于速度与距离的配合及对椭圆参数的影响,有待今后进一步探索。

参考文献

[1]Soltani A R,Tawfik H,Goulermas J Y,FernandoT.Path planning inconstruction sites:performance evaluation of the Dijkstra,A*,andGA search algorithms[J].Advanced Engineering Informatics,2002,16(4):291-303.

[2]Fu L,Sun D,Rilett LR.Heuristic shortest path algorithms for transpor-tation applications[J].Computers&Operations Research,2006,11(33):3324-3343.

[3]汤晓,李贻斌,王彦堂,张娟.基于Mapinfo的最短路径混合搜索算法[J].山东理工大学学报:自然科学版,2006,20(3):81-84.

[4]Recommendation ITU-R M.1371*technical characteristics for a uni-versal ship-borne automatic identification system using time divisionmultiple access in the VHR maritime band(question ITU-r 28/8)[Z].1998.

动态最短路径 篇2

用dp记忆化搜索的思想来考虑是思路很清晰的，但是困难在如何求出字典序最小的路。

因为左边到右边的字典序最小就必须从左边开始找，于是我们可以换个思路，dp时从右边走到左边，这样寻找路径就可以从左向右了。

代码：

/*

* Author: illuz

* Blog: blog.csdn.net/hcbbt

* File: uva116.cpp

* Create Date: -09-20 20:56:07

* Descripton: dp, memorial

*/

#include

#include

using namespace std;

const int MAXN = 102;

int dis[MAXN][MAXN], map[MAXN][MAXN], n, m;

int cg(int x) {

if (x == 0) x = n;

else if (x == n + 1) x = 1;

return x;

}

int dp(int x, int y) {

x = cg(x);

if (dis[x][y] != -0xffffff) return dis[x][y];

return dis[x][y] = map[x][y] + min(min(dp(x - 1, y + 1), dp(x, y + 1)), dp(x + 1, y + 1));

}

void print(int x, int y) {

if (y < m)

printf(“%d ”, x);

else {

printf(“%d”, x);

return;

}

int a[3] = {cg(x - 1), cg(x), cg(x + 1)};

sort(a, a + 3);

int tt = dis[x][y] - map[x][y];

if (tt == dis[a[0]][y + 1])

print(a[0], y + 1);

else if (tt == dis[a[1]][y + 1])

print(a[1], y + 1);

else

print(a[2], y + 1);

}

int main {

while (scanf(“%d%d”, &n, &m) != EOF) {

for (int i = 1; i <= n; i++)

for (int j = 1; j <= m; j++) {

scanf(“%d”, &map[i][j]);

if (j == m) dis[i][j] = map[i][j];

else dis[i][j] = -0xffffff;

}

int Min = 0xffffff, t, rx, ry;

for (int i = 1; i <= n; i++) {

t = dp(i, 1);

if (t < Min)

rx = i, Min = t;

}

print(rx, 1);

printf(“%d”, Min);

}

return 0;

求最短路径问题的策略与方法 篇3

关键词：基本事实；数学模型；策略方法；转化

中图分类号：G633.6 文献标识码：A 文章编号：1009-010X（2015）36-0053-06

求最短路径问题是历年数学中考中的常见题型，在选择、填空和解答题中均有体现，其灵活多变的考查形式，较易与其他知识融合的显著特点，受到许多命题者的青睐。

在中考数学试题中，求最短路径问题常常以求两条线段之和最小值的形式出现，并以特殊三角形、特殊四边形和函数图象等初中数学中的核心知识为载体，以考查学生灵活运用转化、化归等数学思想方法为目的，通过操作探究、推理论证、灵活求解的方式来解决问题。此类问题的解决是以基本事实“两点之间线段最短”为依据，以探寻转化方法为核心，实现对学生综合运用数学知识解决问题能力的全面考查。此类题目充满了探究性和思辨性，常常在中档题和压轴题中出现。

如何利用基本事实“两点之间线段最短”，解决最短路径问题呢？

一、建立数学模型

基本事实“两点之间线段最短”，从宏观上说明了“两点之间的所有连线中，线段最短。”在解决问题时，此基本事实常常以下面的具体模型呈现：

数学模型：如图1，已知点A、点B在直线l 的两侧，点P是直线l上的一个动点，连接AB、PA、PB，则有PA+PB≥AB。

根据“两点之间线段最短”这一基本事实可知：PA+PB≥AB，即当点P与AB和直线l的交点O重合时，PA+PB=OA+OB的值最小，最小值即为线段AB的长。因此，在求两条动线段之和的最小值时，我们只要能够将两条线段转化为一条线上的一个动点到两个定点（在这条线的两侧）的两条线段之和的形式，就可以直接应用这个数学模型来解决问题。

二、应用数学模型

结合2015年全国各地中考数学试卷中，有关求最短路径问题的部分题目，探究解决此类问题的具体策略与方法。

（一）单动点类问题

单动点类问题是指一个点在一条直线上运动，求它到两个定点距离之和的最小值问题。在此类中考数学试题中，给出的两个定点常常是在已知直线的同侧。解决此类问题，常用的方法是：将其中的一个定点转移到动点所在直线的另一侧，使其满足动点到该定点和转移后的点之间的距离相等，这样就可运用这个数学模型，将求两条线段之和的最小值问题，转化为求一条线段长度的问题。

通性通法：（1）定点移位：根据轴对称的性质，过其中一个定点作线段，使动点所在的直线是所作线段的垂直平分线；（2）获得等线：根据线段垂直平分线的性质定理，动点到所作线段两端点的距离相等；（3）运用模型，化二为一：根据基本事实的具体数学模型，连接另一定点和所作线段的新端点，所得线段的长即为所求两条线段之和的最小值；（4）根据题设，求出结果。

1.特殊三角形为背景

【原题再现】例1（2015·四川攀枝花第15题）：如图2，在边长为 2 的等边△ ABC 中，D 为 BC 的中点，E 是 AC 边上一点，则 BE+DE 的最小值为 。

【探究方法】本题属于直接求两条线段之和的最小值问题，且两定点B、D在动点E所在线段AC的同侧，因此，可分两大步骤解决问题：（1）转化：因为点B是等边△ ABC的一个顶点，AC是点B的对边，根据等腰三角形的性质（三线合一），过点B作BO⊥AC，垂足为O，延长BO到点B′，使OB′=BO，则有AC和BB′互相垂直平分，连接EB′，则有B′E=BE；连接DB′，则线段DB′的长即为BE+DE 的最小值（如图3）。（2）求值：如图3，过点D作DG⊥AC，垂足为G，设DB′交AC于点F，则有Rt△DFG ∽Rt△B′FO，易得，OB′=BO=■×2=■， OG=■OC=■AC=■，DG=■BO=■OB′。根据相似三角形的性质，得■=■=■，所以OF=2GF=■OG=■，在R△ B′FO中，FB′=■=■■，所以DF=■FB′=■■，故DB′=■。

【思维拓展】（1）如果将点D转移到直线AC的另一侧，应如何作出所求的线段并求得结果呢？（2）你能直接求出DB′的长度吗？试试看。（事实上，过点B′作B′H⊥BC，交BC的延长线于点H，构造出Rt△ B′DH，解此直角三角形即可。）

2.特殊四边形为载体

（1）正方形

【原题再现】例2（2015·贵州安顺第17题）：如图4，正方形ABCD的边长为4，E为BC上的一点，BE=1，F为AB上的一点，AF=2，P为AC上一个动点，则PF+PE的最小值为 。

【探究方法】（1）转化：因为正方形是关于对角线所在直线对称的轴对称图形，所以作点E关于对角线AC所在直线的对称点E ′，点E ′落在BC的对应线段CD上，连接E ′F，则E ′F即为所求。（如图5）。（2）求值：如图5，过点F作FG⊥CD，垂足为G，易得，DE′=BE=1，DG=AF=2，FG=AD=4，所以在Rt△FGE′ 中，GE′=DG-DE′=1，根据勾股定理，得E′F=■。

【思维拓展】（1）如果将题目中的条件“F为AB上的一点，AF=2”改为“F为边AB上的一点，且F点到边AB端点的距离为1”时，其他内容不变，结果又如何呢？

（2）矩形

【原题再现】例3（2015·湖北孝感第16题）如图6，四边形ABCD是矩形纸片，AB=2。对折矩形纸片ABCD，使AD与BC重合，折痕为EF；展平后再过点B折叠矩形纸片，使点A落在EF上的点N，折痕BM与EF相交于点Q；再次展平，连接BN，MN，延长MN交BC于点G。

有如下结论：

① ∠ABN=60°； ②AM=1；

③■； ④△BMG是等边三角形；

⑤P为线段BM上一动点， H是BN的中点，则PN+PH的最小值是■。

其中正确结论的序号是 。

【探究方法】在本题所给的五条结论中，我们重点对结论⑤进行探究。在①中，连接AN（如图7），易得△ABN为等边三角形，所以∠ABN=60°，故①正确；在②中，易求出AM=■，所以②不正确；在③中，易得BN是MG的垂直平分线，QN是△MBG的中位线，所以BG=BM，QN=■，所以③不正确；在④中，易得∠BMG=60°，BG=BM，所以△BMG是等边三角形，故④正确；在⑤中，由于定点H，N在折痕BM的同侧，动点P在BM上，所以应先“转移定点”。因为H，E两点是等边△ABN两边的中点，因此H，E两点关于折痕BM对称，连接PE（如图7），则有PE=PH，根据基本事实的具体数学模型，当点P与点Q重合时，PN+PH取得最小值，即线段NE的长就是PN+PH的最小值；其次求值。因为NE是边长为2的等边△ABN边AB上的高，所以PN+PH的最小值为2×■=■，故⑤正确。所以本题答案是①，④，⑤。

【思维拓展】如果将结论⑤改为“P为线段GM上一动点，H是BN的中点，则PQ+PH的最小值是■。”结论⑤还正确吗？（提示：不正确，此时PQ+PH的最小值是■。）

3.函数图象为依托

（1）抛物线

同抛物线相结合的最短路径问题，常常是综合类试题中所考查的部分内容，一般情况下，双定点选取抛物线与坐标轴的交点，动点在抛物线的对称轴上。

【原题再现】例5（2015·广西柳州第26题）如图8，已知抛物线y=-■（x2-7x+6）的顶点为M，与x轴相交于A，B两点（点B在点A的右侧），与y轴相交于点C。

（1）用配方法将抛物线的解析式化为顶点式：y=a（x-h）2+k（a≠0），并指出顶点M的坐标；

（2）在抛物线的对称轴上找点R，使得CR+AR的值最小，并求出其最小值和点R的坐标；

（3）以AB为直径作⊙N交抛物线于点P（点P在对称轴的左侧），求证：直线MP是⊙N的切线。

【探究方法】重点探究解决（2）的策略和方法。（1）y=-■（x-■）2+■，M（■，■）；（2）A，C两定点是抛物线与坐标轴的交点，且在对称轴x=■的左侧，动点R在对称轴上。①转化：根据抛物线的对称性，A点关于直线x=■对称点是B点，连接BC（如图9），由基本事实的具体数学模型可知，BC与对称轴的交点即为R，连接AR，此时CR+AR的值最小，其最小值为线段BC的长。②求值：根据抛物线的解析式，求出点A、B、C的坐标，易得A（1，0），B（6，0），C（0，-3）。在Rt△OBC 中，根据勾股定理，求出BC=■=■=3■；再利用待定系数法求出直线BC的解析式为y=■x-3，当x=■时，y=-■，所以点R的坐标为（■，-■）。（3）略。

（2）双曲线

同双曲线相结合的最短路径问题，也常常是综合类试题中所考查的部分内容，一般情况下，双定点在双曲线上，动点在坐标轴上。

【原题再现】例6（2015·四川成都第19题）如图10，一次函数y=-x+4的图象与反比例函数y=■（k为常数，且k≠0）的图象交于A（1，a），B两点。

（1）求反比例函数的表达式及点B的坐标；

（2）在x轴上找一点P，使PA+PB的值最小，求满足条件的点P的坐标及△PAB的面积.

【探究方法】（1）y=■，B（3，1）。（2）A，B两点是在x轴上方双曲线上的两个定点，动点P在x轴上。①转化：作点B关于x轴的对称点B′（如图11），得到B′（3，-1），连接AB′，由基本事实的具体数学模型可知，AB′与x轴的交点即为点P，连接PB，此时PA+PB=AB′，其值最小。②求值：易得直线AB′的解析式为y=-2x+5：，当y=0时，得x=■，所以，满足条件的点P的坐标为（■，0）。设y=-x+4交x轴于点C，则C（4，0），所以，S△PAB=S△APC-S△BPC=■。

【思维拓展】如果将（2）中“在x轴上找一点P”改为“在y轴上找一点P”，其他内容不变，应如何求解呢？（答案：B（0，■），S△PAB=■。）

（二）双动点类问题

双动点类问题是指两条线段各有一个端点或一条线段的两个端点分别在两条线上运动，求两条线段之和的最小值问题。虽然此类中考数学试题，仍然需要运用上面的数学模型来解决，但是，转化到数学模型的过程需要学生具备扎实的数学基本功，以及灵活运用数学知识解决问题的能力和一定的创新意识。

1.两条线段各有一个端点在不同线上运动

【原题再现】例7（2015·天津第15题）在每个小正方形的边长为1的网格中。点A，B，C，D均在格点上，点E、F分别为线段BC、DB上的动点，且BE=DF。

（1）如图12-1，当BE=■时，计算AE+AF的值等于 。

（2）当AE+AF取得最小值时，请在如图12-2所示的网格中，用无刻度的直尺，画出线段AE，AF，并简要说明点E和点F的位置如何是找到的（不要求证明） 。

【探究方法】（1）根据直角三角形的性质，易得AE+AF=■。（2）为解决问题（Ⅱ），我们先来探究：去掉（Ⅱ）中的格点背景，如何用尺规作图的方法画出线段AE和AF。

如图13，在矩形ABCD中，点E、F分别为BC、DB上的动点，且BE=DF。当AE+AF取得最小值时，用尺规作图画出线段AE和AF。

① 画线段AE。如图13，延长DC到点D ′，使CD′=DC，连接BD′，则有∠CBD ′=∠CBD=∠ADB。以点B为圆心，DA长为半径画弧，交BD′于P点，即BP=DA。连接AP，则AP与BC的交点即为AE+AF取得最小值时点E的位置。理由：当点E在BC边上的不同位置时（分别连接AE和PE），因为BE=DF，所以△BEP≌△DFA，所以PE=AF恒成立，这就实现了将两个动点重合，两个定点分别在动点所在直线两侧的目的，因此，根据基本事实的具体数学模型，当点E与AP、BC的交点重合时，AE+AF取得最小值。

② 画线段AF。如图13，在射线DC上截取DQ=DA，过Q点作QR⊥DQ，在射线QR上截取QR=AB，连接DR，在DR上截取DG=AB，连接AG，则AG与DB的交点即为AE+AF取得最小值时点F的位置。请你尝试说明理由。

下面解决原题中的（Ⅱ）。如图14，取格点H，K，连接BH，CK，相交于点P，连接AP，与BC相交，得点E，取格点M，N，连接DM，CN，相交于点G，连接AG，与BD相交，得点F，线段AE，AF即为所求。

【思维拓展】结合在无格点背景下，用尺规作图找E、F两点的方法，请你说明在图14中，确定点E和点F的方法是正确的。

2.一条线段的两个端点在不同线上运动

【原题再现】例8（2015·湖北黄石第25题）如图15-1和图15-2，已知双曲线y=■（x>0），直线l1：y-■=k（x-■）（k<0）过定点F且与双曲线交于A，B两点，设A（x1，y1），B（x2，y2）（x1

（1） 若k=-1，求△OAB的面积S；

（2） 若AB=■■，求k的值；

（3）设N（0，2■），P在双曲线上，M在直线l2上且PM∥x轴，求PM+PN最小值，并求PM+PN取最小值时P点的坐标。

（参考公式：在平面直角坐标之中，若A（x1，y1），B（x2，y2），则A，B两点间的距离为AB=■）

【探究方法】（1）S=2■；（2）k=-2或k=-■。（3）P点在双曲线上，M、N两点在双曲线的同侧。① 转化：l1：y-■=k（x-■）（k<0）过定点F，对于直线l1，无论k取何值，都有x=■时，y=■，所以知F（■，■）。又点P在双曲线上，可设P（x，■），则M（-■+■，■），连接PF（如图16），所以PF=■=■，即PF=■=x+■-■=PM，所以PM+PN=PF+PN。连接NF（如图16），NF交双曲线于P ′点，根据基本事实的具体数学模型可知，当点P与点P′重合时，PM+PN取得最小值，最小值是线段NF的长，易得NF=2。此时NF所在的直线方程为y=-x+2■，由（1）知点P与点A重合，即P（■-1，■+1），所以，PM+PN最小值是2，此时P点的坐标是（■-1，■+1）。

【思维拓展】本题属于变式运用基本事实的具体数学模型。事实上，在基本事实的具体数学模型中，无论条件怎样给出，只要能够将具有公共动端点的两条线段，转化成动点到动点所在线两侧两个定点距离之和的形式，均可使用这个具体数学模型，来解决与两条线段之和距离最短的相关问题。

三、教学建议

基本事实“两点之间线段最短”，简洁明了，浅显易懂，简单结论之中蕴含着大智慧。因此，我们的教学应该做到“知其事，明其理，用其魂”。

知其事：在初中阶段的图形与几何中，“两点之间线段最短”是我们首先要学习的基本事实之一。联系生活实际，结合简单图形，学生较易获得这一基本事实。

明其理：要真正理解这一基本事实，需要师生一起结合具体实例来完成。如，证明“三角形两边之和大于第三边”就有助于加深对这个基本事实的理解，其中教师的教学方式（引导学生用其所知，解己所惑）却起着至关重要的作用！

用其魂：灵活运用这一基本事实解决具体问题，教材在“轴对称”中给出了求两条线段之和最小值问题的范例，不管是哪个版本的教材，其范例原型均与“将军饮马”问题有关。因此，在具体教学时，不妨用“将军饮马”问题导入，既具有较好的趣味性，又能紧扣主题，突出重点。

教学时要让学生亲身经历从实际问题抽象出数学问题的过程，并尝试建立与这一基本事实的联系。教师要为学习困难的学生搭建“桥梁”，助其领会基本事实的内涵和掌握解决具体问题的策略与方法。

总之，掌握运用基本事实解决求两条线段之和的最小值问题的策略和方法，还必须结合恰当的具体教学内容，及时渗透，经常运用。例如，在进行特殊三角形、特殊四边形、函数和圆的有关知识的教学时，要不失时机地添加相关内容，要将运用这一基本事实解决具体问题常态化、系列化，并及时归纳提升。特别是在初三复习时，不仅要在每个专题中适时渗透，同时还要进行专题训练，确保实现学生对此类问题的真正理解和掌握。

动态最短路径 篇4

数学源于生活, 又服务于生活.它是一门研究现实世界中的数量关系与空间形式的学科.当今社会, 随着物质水平的不断提高, 生活需求的不断扩大, 自然资源的不断开发利用.像天然气管道铺设问题, 厂区布局问题, 旅行费用最小问题等都已成为我们平时经济生活中的普遍问题.它们其实都可以化归为最短路线问题, 而最短路问题实质上是一个组合优化问题[1]。

动态规划方法主要是研究与解决多阶段决策过程的最优化问题, 它将求解分成多阶段进行, 不但求出了全过程的解, 还能求出后部子过程的一组解, 在求解一些生活实际问题时, 更显其优越性。为了快速、简单的计算最短路径, 节约运输时间与成本, 该文利用动态规划的思想编写了C语言程序, 解决物流运输过程中多地点的最短路径的选择问题。

2 最短路径问题

2.1 最短路径问题算法的基本思想

在求解网络图上节点间最短路径的方法中, 目前国内外一致公认的较好算法有迪杰斯特拉 (Dijkstra) 及弗罗伊德 (Floyd) 算法。这两种算法中, 网络被抽象为一个图论中定义的有向或无向图, 并利用图的节点邻接矩阵记录点间的关联信息。在进行图的遍历以搜索最短路径时, 以该矩阵为基础不断进行目标值的最小性判别, 直到获得最后的优化路径[2]。

Dijkstra算法是图论中确定最短路的基本方法, 也是其它算法的基础。为了求出赋权图中任意两结点之间的最短路径, 通常采用两种方法。一种方法是每次以一个结点为源点, 重复执行Dijkstra算法n次。另一种方法是由Floyd于1962年提出的Floyd算法, 其时间复杂度为O (n3) , 虽然与重复执行Dijkstra算法n次的时间复杂度相同, 但其形式上略为简单, 且实际运算效果要好于前者。

2.2 最短路径问题算法的基本步骤[3]

(1) Dijkstra算法基本步骤

(c) 若vk=vn则已找到v1到vn的最短路距离W (v) k, 否则令i=k从中删去vi转1。

这样经过有限次迭代则可以求出v1到vn的最短路线。

(2) Floyd算法的基本步骤

如果一个矩阵D=[dij]其中dij>0表示i与j间的距离, 若i与j间无路可通, 则dij为无穷大。i与j间的最短距离存在经过i与j间的k和不经过k两种情况, 所以可以令k=1, 2, 3, ⋯, n, n (n为节点数) 。检查dij与dik+dkj的值, 在此, dik与dkj分别为目前所知的i到k与k到j的最短距离, 因此, dik+dkj就是i到j经过k的最短距离。所以, 若有dij>dik+dkj, 就表示从i出发经k再到j的距离要比原来的i到j距离短, 自然把i到j的dij重写成dik+dkj。每当一个k搜索完, dij就是目前i到j的最短距离。重复这一过程, 最后当查完所有k时, dij就为i到j的最短距离。

(3) 动态规划算法基本步骤

我们将具有明显的阶段划分和状态转移方程的规划称为动态规划[1]。在解决多个阶段决策问题时采用动态规划法是一个很有效的措施, 同时易于实现。

根据动态规划的基本概念, 可以得到动态规划的基本步骤:1) 确定问题的决策对象。2) 对决策过程划分阶段。3) 对各阶段确定状态变量。4) 根据状态变量确定费用函数和目标函数。5) 建立各阶段状态变量的转移过程, 确定状态转移方程。

根据动态规划的基本模型, 确定用动态规划方法解题的基本思路, 是将一个n阶段决策问题转化为一次求解n个具有递推关系的单阶段的决策问题, 以此来简化计算过程.其一般步骤如下:

用于衡量所选决策优劣的函数称为指标函数.指标函数有有阶段的指标函数和过程的指标函数之分.阶段的指标函数是对应某一阶段状态和从该状态出发的一个阶段的某种效益度量, 用vk (xk, uk) 表示。在本文里用dk (xk, uk) 来表示某一阶段的决策的最短路径。过程的指标函数是指从状态xn (k=1, 2, ..., n) 出发至过程最终, 当采取某种子策略时, 按预定的标准得到的效益值。这个值既与xk本身的状态值有关, 又与xk以后所选取的策略有关, 它是两者的函数值, 记作dk, n (xk, uk, xk+1, uk+1, ⋯xn, un) 。过程的指标函数又是它所包含的各阶段指标函数的函数。本文研究的过程的的指标函数是其各阶段指标函数的和的形式.当xk的值确定后, 指标函数的值就只同k阶段起的子策略有关。对应于从状态xk出发的最优子策略的效益值记作fk (xk) , 于是在最短路问题中, 有fk (xk) =mindk, n。动态规划求解最短路径程序流程图如图2所示。

3 最短路径态规划实际应用举例

设某物流配送网络图由12个配送点组成, 点1为配送中心起点, 12为终点, 试求自终点到图中任何配送点的最短距离。图中相邻两点的连线上标有两点间的距离[4]。

首先用动态规划法来讨论图3的最短路径, 由图可知:

1) 集合ξ4中有点9、10、11, 它们在一步之内可到达点12;

2) 集合ξ3中有点6, 7, 8, 它们不超过两步就可达到点12;

3) 集合ξ2中包括点2、3、4、5, 不超过三步就可到达点12;

4) 集合ξ1中包括点1, 不超过四步可到达点12;

按照动态规划法类推, 得到最优路径长为16, 径路通过点为1, 2, 7, 10, 12和1, 3, 6, 10, 12。

根据动态规划算法编写C语言计算程序[5,6], 计算得到实验结果如下图4所示:

由图4可以看出程序得到的结果与本文推出的结果一样。证明了本文编写的C语言程序是正确的。

4 结束语

综上所述, 用动态规划解决多阶段决策问题效率高, 而且思路清晰简便, 同时易于实现.我们可以看到, 动态规划方法的应用很广泛, 已成功解决了许多实际问题, 具有一定的实用性。此种算法我们用动态规划思想来编程, 并解决相应的问题, 其在VC环境下实现, 能方便快速的计算出到达目的地的最短距离及路径, 节省更多的运输时间与成本。不过, 该文只考虑了动态规划算法在生活中的简单运用, 在实际生活中可能存在多个目的地或者更复杂的情况.因此我们可以考虑将其进行改进或者结合启发式算法, 使之更好的运用在实际生活中, 这有待于以后的继续研究。

参考文献

[1]杜彦娟.利用动态规划数学模型求解最短路径[J].煤炭技术, 2005 (1) :94-95.

[2]蒋琦玮, 陈治亚.物流配送最短径路的动态规划方法研究[J].系统工程, 2007 (25) :27-29.

动态最短路径 篇5

一、实验目的：

理解最短路径分析的基本原理，学习利用arcgis软件进行各种类型的最短路径分析的操作。

二、实验准备

1、实验背景：

最短路径分析是空间网络分析中最基本的应用，而交通网络中要素的设置对最短路径的选择有着很大的影响。实验要求根据不同的权重，给出到达指定目的地的路径选择方案，并给出路径长度。

 在网络中指定一个超市，要求分别求出在距离、时间限制上从家到超市的最佳路径。

 给定访问顺序，按要求找出从家经逐个地点达到目的地的最佳路径。

2、实验材料：

软件：ArcGIS Desktop 9.x，实验数据：文件夹ex6中，一个GeoDatabase地理数据库：City.mdb，内含有城市交通网、超市分布图，家庭住址以及网络关系。

三、实验内容及步骤

首先启动ArcMap，选择ex6city.mdb，再双击后选择将整个要素数据集“city”加载进来，然后将“place”点状要素以“HOME”字段属性值进行符号化，1值是家，0值是超市。

第1步 无权重最佳路径的选择  加载 “设施网络分析”工具条（“视图”>>“工具条”，勾选“设施网络分析”），点选旗标和障碍工具板下拉箭头，将旗标放在家和想要去的超市点上。

第2步 加权最佳路径选择

 在设施网络分析工具条上，点选旗标和障碍工具板下拉箭头，将旗标放在家和想去的某个超市点上。

 选择“分析”下拉菜单，选择“选项”按钮，打开“分析选项”对话框，选择“权重”标签页，在“边权重”上，全部选择长度“length”权重属性。 点选“追踪任务”下拉菜单选择“查找路径”。单击“执行”键，则以长度为比重为基础的最短路径将显示出来，这条路径的总成本将显示在状态列。

 上述是通过距离的远近选择而得到的最佳路径，而不同类型的道路由于道路车流量的问题，有时候要选择时间较短的路径，同样可以利用网络分析进行获得最佳路径。

第3步 按要求和顺序逐个对目的点的路径的实现

 在设施网络分析工具条上，点选旗标和障碍工具板下拉箭头，将旗标按照车辆访问的顺序逐个放在点上。

 选择“分析”下拉菜单，选择“选项”按钮，打开“分析选项”对话框，选择“权重”标签页，在“边权重”上，全部选择长度“length”权重属性。 点选“追踪任务”下拉菜单选择“查找路径”。单击“执行”键，则从起点按顺序逐一经过超市最后回到家的最短有效路径将显示出来，这条路径的总成本将显示在状态列。

同样是经过这11个地点，换成权重是时间的，由于道路车流量的不同，如在市中心车流量特别大，车速慢，故而为节约时间，所以使得路径发生很大的改变。

第4步 阻强问题

这里的阻强是指网络中的点状要素或线状要素因为实际中遇到的例如修路，或那个时段车辆饱和，十字路口发生事故等一些缘故而使得要素不可运行，这时原来获得的最短路径就需要进行修正，具体操作如下： 修路的情形出现，即某个路段不可运行，这在网络中的表现是设置阻强，方法有两种，一种是永久性的，直接将网络边要素的属性修改成不可运行。选择要进行设置的边要素，将其属性中的“Enabled”字段改成“False”即可；另一种是暂时性的，设置边要素障碍。即利用边要素障碍添加工具将边设置。



动态最短路径 篇6

关键词：最短路径 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.

动态最短路径 篇7

车载导航系统是智能交通系统(Intelligent Transportation System,ITS)的一个重要组成部分。随着我国汽车产业的迅猛发展,越来越多的人开始投入到车载导航系统方面的研究开发中。但是,当前投入使用的车载导航系统基本上都属于基于静态交通信息和历史数据的自主导航系统,缺乏动态交通信息服务的支持。构建自主知识产权的动态车载导航系统是我国车载导航系统发展的必然趋势。动态车载导航系统可以帮助系统用户在即时变化的动态交通环境下,寻找到更具实用意义上的最优路径。另一方面,建设基于动态交通信息的车载导航系统,对于完善城市智能交通系统的建设,充分发挥交通诱导在均衡交通流、减少交通拥堵、节约出行时间等方面的作用具有重要意义。

如今,基于位置服务(Location-Based Service,LBS)已经能通过环状检测器、车辆探测器及录像监视系统获取即时交通信息。相比之下,作为车载导航系统核心技术的动态最短路径算法却仍处于滞后阶段。目前在车载导航中常用的最短路径算法主要是Dijkstra算法及A*算法,此外还有双向搜索、分层搜索、在线搜索等方法。但此类算法都未考虑车辆行进中路段行程时间动态变化的特性,且只能搜索两点间的唯一最短路径,不能满足车载导航的实际需要。本文将针对其中效率较高的A*算法及A*在动态环境中的改良算法LPA*算法进行研究,提出进一步的改良方案。

1 算法介绍

1.1 A*算法

A*(A-star)算法是一种启发式(heuristic)算法,是静态最短路径中最受欢迎的算法之一。它的整体框架是一个网络的遍历搜索,采用启发函数来估计地图上任意节点离目标节点的远近程度。A*算法希望通过将搜索方向指向目标点来提高搜索效率。具体可描述为:用f(n)=g(n)+h(n)作为新节点插人队列的排序标准,这里,g(n)表示源点到当前节点的实际代价,h(n)是当前节点的启发值,如果h(n)=0,则A*就是普通的Dijkstra算法[1]。

算法能否成功找到最短路径的关键就在于对估价函数h(n)的选取,估价值与实际值越接近,估价函数就越好。常用的估计函数有曼哈顿距离和欧几里德距离。虽然A*(A-Star)算法是静态路网中求解最短路径最有效的方法,但将其直接用在动态环境时,由于对没有变化的结点仍须重复计算从而导致计算效率不高,于是就有了LPA*算法。

1.2 LPA*算法

A*终身计划(Lifelong Planning A*,LPA*)是A*的一个优化算法。它能在路况改变时,重复利用早先查询的结果,较快地获取新的最短路径。LPA*的搜索过程分两步,初始步骤与A*相同,其后的搜索保留前一次搜索中与新搜索树相一致的部分,即从起始点开始到尚未发生任何改变的节点之前的搜索树。

LPA*有三个参考值:一个是每个节点s的起始距离g(s),在后面的查询中它直接对应于A*算法中的g值,且可重复利用;第二个是节点到目标节点sgoal间的近似距离,它与A*算法中的h值意义相同,都是为了朝着目标方向来运行查询进程;最后一个是起始距离的另一个估计值,即基于前一次查询的g值的rhs值。他们通常遵循以下关系式:当s是起始节点时,rhs(s)=0;否则,rhs(s)=Mins'∈pred(s)(g(s")+c(s,s'))。如果它的g值等于rhs值,则LPA*算法中的每个节点都是局部一致的。如果所有的节点是局部一致的则所有节点的g值等于它们的起始距离。事实上在LPA*中没有必要使所有的节点都局部一致。相反,它使用启发式h(s)来整合查询方向,并仅更新与sstart到sgoal之间的最短路径估计值有关的g值。

LPA*算法中有一个总是包含有局部不一致结点的优先队列,这些结点需要不断更新从而保持局部一致。A*算法中结点参照f值输入优先队列中,与A*算法相似,LPA*算法在优先队列中以最小的关键值(f值)来扩展结点。结点s的关键值k(s)由两部分组成:k(s)=[k1(s);k2(s)],其中k1(s)=Min(g(s),rhs(s))+rhs(s),k2(s)=Min(g(s),rhs(s))。简单来说,由于LPA*算法中的g值和rhs值对应于A*算法中的f值,所以k1(s)值直接对应于A*算法中用到的f值(f(s)=g(s)+h(s)),而k2(s)对应于A*算法中的g值。与A*算法相似,LPA*算法中按照最小的k1值(f值)将结点输入优先队列中,并向着k2值最小的结点方向来断开其它的连结。LPA*与A*的发生行为也很相似。LPA*算法直到sgoal局部一致且其次扩展的结点集的关键值等于目标结点sgoal的关键值才能结束结点扩展。

1.3 LPA*算法在道路网中的路径搜索

图一所示是在一个表示简单道路网的图表中找到从A到K的最短路径。左上角的图给出了每条弧段的权值[2]。为了举例方便,起始距离和启发式也被标注在每个结点附近。当LPA*执行第一次查寻时,它将所有结点的g值和rhs价值初始化为无限。实际上我们不能将一大幅地图的每个结点初始化,而是在搜索时只对我们遇到的结点进行初始化。在接下来的迭代中,每个结点都带有一个括号,其中的两个值分别代表了k1值和k2值。括号上方的数值表示起始距离(g值),而括号中单独的数值表示该结点在本地一致时的g值。黑色方块表示当前迭代所拜访的结点在本例中,我们使用所有结点到目标结点的曼哈顿距离作为LPA*的启发式且从优先队列中被选中。同样搜索扩展到结点C、H和G。在这一步迭代中,由于它的相邻点最小的g值为g(B)=10,故rhs(C)值被更新为20,父节点为B。因此,我们记录下从起始点到各个被访问结点作为最短路径。最终,从优先队列中获取到结点H(k1=38)。当找到结点K,搜索终止,且结点K也是本地一致的,因为从K扩展的任何结点的关键值都不会比K的关键值小。

图二是一个描述了当弧段的权重发生改变的实例。在例子中弧段EH的权重增加10。为适应这个变化,我们先检测弧段EH周边结点的估计值(g,rhs),这些估计值是潜在的最受其影响的估计值。最靠近该弧段的结点为E、H。虽然结点E不受该变化的影响,但结点H的起始距离和rhs值会随之变化。更新后,它的起始距离变为44,rhs值变为34。由于结点K变得局部不一致,故下一步就是更新到结点K。到目前为止,从最优队列中获取结点G,通过扩展结点G到结点H和J,这种搜索方式的最短路径可以避免拜访许多不受该变化影响的不必要的结点。LPA*算法可重复利用最后一次搜索的计算结果,并通过逐步更新不一致的结点使得路线的重新计算更加方便快捷。

LPA*的主要优点是能够推进起始距离(g值)且在一次次的搜索中对其进行重复利用。虽然LPA*算法能高效地应对动态环境,但它并不能作用于起始结点位置随时间变化而变化的状况。当移动用户沿着预先的最短路径移动并询问新的能适应环境变化的最佳路径时,LPA*算法并不能很好地进一步搜索,因为现在起始结点变化了故起始距离g值也不再有效。当前的结构下为这些结点重新建立g值是不可能了,除非放弃LPA*之前的结果,从头执行一次独立的搜索查询。

2 改良LPA*算法用于道路网中的路径搜索

虽然LPA*算法能高效地应对动态环境,但它并不能作用于起始结点位置随时间变化而变化的状况。当移动用户沿着预先的最短路径移动并询问新环境的最佳路径时,LPA*算法并不能很好地进一步搜索,因为起始结点发生了改变。故起始距离g值也不再有效。除非放弃LPA*之前的结果,从头执行一次独立的搜索查询,否则不可能重新建立这些节点的g值。

通常观测的目标结点都是保持不变的,而起始结点却是不断变化的移动物体。基于这一点,我们将LPA*算法修订如下:当用户计划从结点v移动到结点w时(v,w∈s)并计算这两点间的最短路径,在计算最短路径时我们可以交换查询方向。也就是说,我们将w视为起始点,以从结点w查询到v来代替从结点v到w的查询。在交换方向后,源结点处于最短路径搜索树的根部不在变化,仅仅是目标结点(原来的起始结点)发生变化。因此,所有结点的标记起始距离能在到随后的搜索中被用到并能在搜索中反复利用。

为了进一步提高算法的效率,我们用最小界矩形来限制搜索的范围,减少改良后的LPA*算法的查询空间。由于椭圆是除圆形以外可以用在距离问题上最简单的几何图形,我们首先讨论如何用椭圆的一些特征来减少改良LPA*算法的查询空间。椭圆是到两个给定位置(即椭圆的两个焦点)的距离之和固定的点的轨迹,距离和的固定值等于椭圆的长轴长度。它的一个重要特征是椭圆内所有的点都比椭圆边界上的点要更接近两个焦点,椭圆上的点又都比椭圆外的点更接近。

在图三中,如果我们知道图中两个结点s和g之间的网络距离d,将结点s、g作焦点,d作长轴长度构建一个椭圆,就可以得出。如果s、g两点间存在最短路径,该路径就须在椭圆的范围内。为证明这个说法,我们假设一个结点v在s、g的最短路径上,v的位置在椭圆之外;我们可以计算出│sv│+│sg│>d。所以假设s、v与v、g之间存在直线路径,那个路径长度也必定大于d。所以结点v不在s、g之间的最短路径上。基于这个原理,我们可以用椭圆来修剪那些不可能出现在最短路径上的点。

我们需要解决的下一个问题是如何确定这个椭圆的大小。回顾改良LPA*算法的搜索过程中,我们能在网络中弧段权重动态更新的基础上获取起始点到目标结点间的网络距离,因而限定一个以网络距离为长轴,起始结点和目标结点为焦点的椭圆是可行的。因此,如果在起始结点与目标结点之间存在一个较短的替代路径,则路径上所有的点都必须在该椭圆的范围内。椭圆外的所有结点都能安全的从搜索范围中删除,改良LPA*算法在搜索过程中的效率得以进一步提高。

在实际运算中,直接利用椭圆形的边界为搜索区域的边界效率较低,因为它牵涉了太多幂运算。为此,我们使用限定椭圆形的最小界矩形(MBR)来简化计算。给定椭圆形的MBR计算过程如下:假定一个椭圆形两个焦点为(x1,y1)和(x2,y2)和长轴,该椭圆形表示如等式(3)。如果使用椭圆等式的x、y的局部衍生,我们能从等式获得极值xm、ym。椭圆被顶角为xms和yms的MBR包围。

其中:

且

3 结束语

本文将A*终身计划这种新方法用到解决导航服务中的最短路径问题中,并对其进行了改良。改良后的LPA*算法在二个方面进行了改善。首先,在一个弧段权重发生改变的网络中,通过交换从起始节点到目标节点间的查询方向,保留前一次搜索中最短路径树上节点的所有信息;第二,我们根据椭圆的特性推出了最小界矩形来进一步限制待检测节点的搜索空间,从而进一步改进了改良LPA*算法。

摘要：车辆导航的一个基本问题是如何在一个即时的动态交通网中找到最优路径,现有的算法不是太复杂,就是不能很好地处理当移动物体的位置及交通环境同时发生变化所造成的复杂环境。本文推荐一种A*算法的变种——A*终身计划(Lifelong Planning A*,LPA*),并在该算法的基础上进行了改良,提出了采用特定椭圆修剪不必要的查询节点,以提高动态搜索的速度。

关键词：LPA*,导航,动态最短路径

参考文献

[1]陆锋.最短路径算法:分类体系与研究进展[J].测绘学报,2001,30(3).

[2]Nils J Nilsson.人工智能[M].北京:机械工业出版社,2000.

[3]B.Huang a;Q.Wu b;F.B.Zhan.A shortest path algorithm with novel heuristics for dynamic transportation networks[J].in-ternational journal of geographical information science,2007,(06):625-644.

[4]HUANG,B.and WU,Q.,2007,A spatial indexing ap-proach for high performance location based services[J].Journal of Navigation,2007,(60).

最短路径的教学 篇8

《数据结构》课程是计算机类信息类专业的基础核心课程, 这门课程掌握的程度影响到其它后续课程的学习, 相关知识也会应用在实际的软件开发中。大多数院校在低年级开设这门课程, 低年级的学生一般只学过一门高级程序设计语言, 如C语言, 对面向对象程序设计、面向对象编程思想、抽象类型、数学模型、解决实际问题的算法了解甚少。笔者长期从事《数据结构》课程的教学, 对这门课程的教学有一套自己的方法。本文以最短路径的教学为例, 论述了《数据结构》中抽象类型--图的教学思路。

1. 问题的提出

随着生活水平的提高, 汽车已经进入千家万户, 工薪阶层拥有汽车已经成为可能。假期上班族开着自己的汽车到外地旅游已经成为一种时尚。在旅游的过程中, 如何缩短路程减少费用, 成了人们关心的问题。如, 旅客要自己开车从福州到乌鲁木齐, 怎样选择线路, 才能使路径的总和最短, 从而费用总和最少。

2. 数学模型

在上面的问题中, 可以把城市看成顶点, 城市之间若有路可到达的话, 在城市对应的顶点之间加上一条边, 在边上加上权值表示两个城市之间的距离, 这样可以构成一个图 (我们称为无向网络) 。在构造无向网络的过程中, 只要考虑感兴趣的城市 (也就是说只要把感兴趣城市对应的顶点加入到无向网络中) , 同样道理, 也只要把感兴趣的线路加入到无向网络中。

3. 存储结构

G.kind存储的值有四种DG, DN, UDG, UDN。DG表示有向图, DN表示有向网络, UDG表示无向图, UDN表示无向网络。G.vertexnum存储的值表示顶点的个数 (或者说是城市的个数) 。G.edgenum存储的值表示边的条数 (或者说是线路的条数) 。G.edges[j][k]存储的值表示两个城市之间的距离。G.vertexs[i]存储的值是城市的名称。

最终, D[j][k]存放从第j个顶点到第k个顶点的最短距离, P[j][k][t]存放从第j个顶点到第k个顶点的最短路径上的顶点的下标, N[j][k]存放从第j个顶点到第k个顶点的最短路径上的顶点的个数。

4. 实现算法

5. 问题的解决

调试过程如下 (带下划线的字符为从键盘输入的数据) :

要创建图, 请输入图的类型,

0表示有向图 (DG) , 1表示有向网络 (DN) , 2表示无向图 (UDG) , 3表示无向网络 (UDN) :3

要创建无向网络 (UDN) , 请输入顶点的数目:25

要创建无向网络 (UDN) , 请输入边的数目:30

要创建无向网络 (UDN) , 请输入25个顶点:

福州南昌上海徐州天津大连沈阳长春哈尔滨北京郑州武汉株州广州深圳南宁柳州贵阳昆明成都西安呼和浩特兰州西宁乌鲁木齐 (回车)

要创建无向网络 (UDN) , 请输入25*25的矩阵, 有边用权值, 无边用0:

请输入起点城市:

请输入终点城市:

从福州到乌鲁木齐的最短路径为:福州---南昌---株州---武汉---郑州---西安---兰州---乌鲁木齐 (5011)

继续吗?请输入 (Y或y表示继续, N或n表示终止) :

请输入起点城市:

请输入终点城市:

从南宁到乌鲁木齐的最短路径为:南宁---柳州---株州---武汉---郑州---西安---兰州---乌鲁木齐 (4949)

继续吗?请输入 (Y或y表示继续, N或n表示终止) :

摘要：本文论述了《数据结构》图论部分最短路径这一小节教学过程当中的一些体会。从实际问题出发, 提出相关的数学模型, 建立相应的存储结构, 在建立的结构上编写算法, 从而达到解决实际问题。

关键词：数据结构,抽象类型,最短路径,教学方法

参考文献

[1]《数据结构 (C语言版) 》, 严蔚敏吴伟民编著, 清华大学出版社, 1997.4

A*寻找最短路径算法及实现 篇9

关键词：C#语言,A*算法,寻找最短路径

1 引言

A*算法是静态路网中求解最短路径最有效的一种方法, 公式表示为f (n) =g (n) +h (n) , 其中f (n) 是从初始节点经由节点n到目标点的估价函数, g (n) 是从初始节点到n节点的实际代价, h (n) 是从n到目标节点最佳路径的估计代价。因为g (n) 是已知的, 找到最短路径关键在于估计函数h (n) 的选取, 下文h (n) 选择为n到目标节点的Hamilton距离。

2 设计思路

利用C#语言实现A*寻找最短路径算法, 如图1所示, 除了窗口界面类外设计了两个类。

一是模型类 (MapMode) , 功能为建立网格数据模型和实现A*算法。建立网格数据模型包括:建立网格节点结构模型 (Grid) , 实现模型的构造 (MapMode (int[, ]_map) ) , 初始化网格节点 (InitMapGrid () ) ;实现A*算法包括:AstarFindPath (int_startGridId, int_end GridId) , AStarFindPath_step (int_startGridId, int_endGridId) 。

二是画图类 (Draw) , 功能为绘制起点 (DrawStaPoint (int x, int y) ) , 绘制终点 (DrawEndPoint (int x, int y) ) , 绘制障碍 (DrawHinderPoint (int x, int y) ) , 绘制路径 (DrawPathPoint (int x, int y) ) , 绘制游戏场景 (DrawBackground () ) , 清空游戏背景 (BackgroundClear () ) 。

网络资料上, A*算法的搜索过程一般为创建两个表, OPEN表保存所有已生成而未考察过的节点, CLOSE表记录已经访问的节点。以下实现过程没有创建表, 而是在网格节点 (Grid) 中包含字段open (表示该节点是否在计算列表中) , 字段close (表示该节点是否在行走路径中) 。通过计算节点相邻的上下左右4个节点的f (n) 的值, 并维护节点的字段open、close的值, 在字段open为true的所有节点中选择f (n) 最小的值为下一步格子, 实现最短路径搜索。该方法仅针对网格节点进行计算和维护, 使程序流程更加清晰。

3 实现代码

3.1 窗口界面类

3.2 MapMode类

3.3 Draw类

4 结语

基于邻接矩阵的最短路径算法 篇10

关键词：最短路径,定界,活节点

0 引言

最短路径问题是给定有向图G、节点V的集合及边上的权值求源点到目标点最短距离。目前解决这个问题的算法很多, 其中最有名的算法是Dijkstra算法, 其余的方法大都是利用Dijkstra算法或者改进它, 例如:王江晴使用dijkstra算法计算动态路径, 而李洪波只是利用矩阵计算路径上的节点数, 没有涉及到路径上的权值。本文把邻接矩阵的计算用于解决最短路径, 提供了一种解决最短路径问题的新方法, 特别对于邻接矩阵是稀疏矩阵的情况下非常适合。

1 相关概念

已知:一个有向图G= (V (G) , E (G) , W (G) ) , 其中G表示图, V (G) 表示图G的节点集合, E (G) 表示图G边的集合, W (G) 表示边上路径的权值。设节点集合为V (G) = (v1v2…vn) vi为节点, E (G) = (…eij…) eij表示邻接节点vi、vj边上的权值, W (G) = (…wij…) wij表示从节点vi到vj的路径上权值累加和。求一条从v1到vn的最短有向路径的长度。

设n个顶点的邻接矩阵为:A (G) = (aij) =A

令B= (bij) 表示图G的可达性矩阵

其中:Aj= (ajst) , ajst表示矩阵A的j次幂的第s行第t列位置的元素s, t=1, …, n。

对于大规模稀疏矩阵的时候, 由于数据元素或者为1或者为零, 因此, 只需要存储非零数据元素的行和列的位置, 而不需要存储元素的值。本文将采用下面所示二元组的顺序表和行逻辑连接的顺序表存储数组元素:

2 路径构造的方法与策略

2.1 通路的构造

设A和Ar (r

2.2 中间节点的选取原则

每次从可选取的节点中, 选择一个邻接边长最短的节点, 但不构成回路。

2.3 更新活节点集

更新的方法是把刚刚添加到路径中的新节点从活节点集合中删除;同时, 把新节点的子节点添加到活节点集合中;这个过程表示为:active=active-{新添加的节点}∪{新添加的节点的子节点}。

Active表示活节点集合。

2.4 定界

定界分两种情况考虑:

情况1:如果算法计算到某一步骤, 已经产生一条从始节点v1到终节点vn的通路, 设通路的有向路径的长度为w1。而另一条正在搜索的路路径长度为w2, 不管正在计算的路径是否已经搜索到通路, 如果满足:w1≤w2, 那么这条正在搜索的路径应该去掉;如果满足w1>w2, 那么搜索继续。

情况2:设vj有k个分支点vj+1, …vj+k, 如下图1所示, 设ejj+1是其中邻接边长最短的, vn到vj比目前找出来的最短路径短, 而从vn到vj+1比目前的最短路径要长, 那么, 按照情况1, vj+1应该不在最优路径上, 应该删除, 事实上这时经过vj的每一条路径都比经过vj, vj+1要长, 所以更应该删除, 因此vj应该被删除。

2.5 计算路径长度

设第一搜索点为vn, 已经搜索到vi, 而vj是要加到这条路径上的vi的邻接点, 那么:wnj=wni+eij。

另外, 本算法采取从最后一个节点逆向搜索节点, 本算法假设寻找vi到vn的最短路径, 对于其余情况也是类似的。

3 搜索算法

初始化:给A赋初值

第一步计算矩阵A的幂

令活节点集

active={vi│vi为指向vn的邻接点, 并且vi在起点到终点的通路上}

第二步深度搜索优先, 寻找第一条通路。按深度搜索优先原则, 根据2.1和2.2增加邻接边, 按2.3更新活节点集合, 按照2.5计算路径长度, 重复这个步骤直到找到第一条从源点到目标点的通路, 并且令这条路是当前的最短路径。

第三步宽度搜索优先, 选择新的分支点。按宽度搜索优先原则, 根据2.1和2.2增加邻接边;按照2.5计算准路径的长度, 转第四步。

第四步定界。如果准路径长度大于当前最短路径, 根据定界2.4删除相应的活节点;如果准路径长度小于等于当前最短路径的长度, 按2.3更新活节点集合active, 然后分两种情况:

(1) 准路径是从源点到目标点的通路, 准路径为新的当前最短路径;

(2) 准路径不是从源点到目标点的通路, 则转第三步。

第五步输出最短路径节点集和最短路径长度。

4 实例

上图2为一个有向路径图, 求标号为0的节点v0到标号为4的节点v4的最短距离。

首先给出邻接矩阵:

计算A的幂其中乘法为普通乘法, 加法为逻辑相加:

有:a04=1, a204=1, a304=1

对应于a304=1, 有a202=1, a24=1, 所以v2、v4为邻接点, e24=10

对应于a204=1, 有a03=1, a34=1所以v3、v4为邻接点, e34=60

对应于a04=1, 有e04=100

min{e04, e24, e34}=e24=10, 所以v4的邻接点为v2, 对应active={v1, v3}。

以v2进行深度搜索得到节点v1, e12=50, 继续得到节点v0, e01=10所以通路为:T={v0, v1, v2, v4}, w0, 4=70 active={v3}。

第三步从active={v3}中取出v3, 而w34=60, w34+w03=90>70, 舍弃e04=100>w04, 舍弃。

所以:T={v0, v1, v2, v4}, w0, 4=70 active={v3}。

5 结束语

从上面的实例可以看出v5虽然与v4邻接边长最短, 但是, 由于它不在从目的点到源点的通路上, 所以v5不在活节点集合中, 这样会减少很多搜索的计算量, 故, 本算法的第一条是只有在通路上的节点才是活节点。本算法与Dijksta算法不同之处在于:Dijkstra算法只要跟源点是连通的点都是活节点, 而本算法只有从源点到目的点通路上的点才是活节点;Dijkstra算法把源点到其余每一点的最短路径都求出来, 本算法直接求源点到每个目的点的最短路径, 因此从这个角度来说本文节省了大量的计算量。当然由于要计算矩阵的幂, 会增加计算量, 并且一般情况下, 这个计算量很大;但是, 当邻接矩阵是稀疏矩阵时, 矩阵幂的计算量会大大减少。因此本文算法适合于邻接矩阵是稀疏矩阵的情况。

参考文献

[1]吴晓红.关于最短路径问题的一种有效算法[J].系统工程与电子技术, 1999 (11) .

[2]段凡丁.关于最短路径的SPFA快速算法[J].西南交通大学学报, 1994 (2) .

[3]伍建华.单源最短路径问题的Seidel迭代法[J].计算机应用, 2001 (8) .

[4]乐阳, 龚健雅.Dijkstra最短路径算法的一种高效率实现[J].武汉测绘科技大学学报, 1999 (3) .

[5]孙强.Dijkstra的一种改进算法[J].计算机工程与应用, 2003 (3) .

[6]王江晴.动态车辆路径问题中的实时最短路径算法研究[J].武汉理工大学学报 (交通科学与工程) , 2007 (1) .

[7]李洪波.Floyd最短路径算法[J].计算机工程与应用, 2006 (34) .

经纬网格寻址中最短路径算法优化 篇11

对经纬网格进行二维剖分, 进而利用最短路径的方法, 求两个之间的最短距离, 是解决天气数值预报中模式计算的核心问题。进行最短路径的计算, 就必须首先将其按结点和边的关系抽象为图的结构, 这称为构建网络的拓扑关系。只有建立了拓扑关系, 才能进行网络路径分析。于是最短路径计算实现的关键在于网络拓扑结构的建立和高效能最短路径算法。文中针对解决实际最短路径问题较为有效的Dijkstra算法进行并行优化。即如图1所示从源点甲地出发, 到达图上丁地的最短路径。

2 流程伪代码

这里采用了贪心的策略, 利用宽度优先一层层搜索, 直到遍历所有结点或已经找到最短路径。算法伪代码如下:

2.1 优化一

对Dijkstra (G, w, s) 取最短路径是运用map-reduce方法, 对D的更新在main函数中进行。

2.2 优化二

对阵列D进行更新的时候运用map-reduce方法, 对D的更新采用了一种单map多个reduce的暴力方法:

Step1:用map函数获取D[i]!=INFINITY且没有取得最短路径的所有节点及其邻接节点的信息。

Step2:采用多个reduce函数同时对阵列D进行更新, 输出 (路径长, 节点) 的元组, 通过后台进行排序, 获取一次迭代得到的最短路径。

3 实验结果

程序都进行了相对严谨的测试。对于不同N值的程序得到了相同的结果, 跟串行程序的结果也一样。程序结果列举如图2所示。图1为N=10时, 零点到所有顶点的最短路径结果显示。根据上方的邻接矩阵可以很容易匹配上下面的打印结果。图3为N=1024时的打印结果, 两个程序结果一致, 另外本人还写了一个串行的求单点最短路径的程序, 输出结果均与之相符。

4 结论

依据最短路径算法分析, 采用贪心策略和MapReduce编程模型实现路径计算过程中优先级队列的一系列操作, 从而提高算法的计算性能。解决数值预报中地理空间范围内两点间的最短路径求解难题, 该结果的合理应用为数值预报模式中最短路径求解提供参考依据。

摘要：最短路径分析地理信息系统中的空间经纬网络寻址中的计算瓶颈, 对其算法进行优化很有必要。针对最短路径中经典的Dijkstra算法, 采用贪心策略和MapReduce编程模型实现路径计算过程中优先级队列的一系列操作, 从而提高了算法的计算性能。