聪明文档网
最新最全的文档下载
当前位置：
首页> 最佳路径问题
最佳路径问题
时间：2022-12-16 00:11:16 下载该word文档
路径分析是GIS中最基本的功能，其核心是对最佳路径的求解。从网络模型的角度看，最佳路径的求解是在指定网络的两个结点之间找一条阻碍强度最小的路径。另一种路径分析功能是求解最佳游历方案，又分为弧段最佳游历方案求解和结点最佳游历方案求解两种。
最佳路径分析也称最优路径分析，以最短路径分析为主。这里“最佳” 包含很多 含义，不仅指一般地理意义上的距离最短，还可以是成本最少、耗费时间最短、资源流量（容量）最大、线路利用率最高等标准。很多网络相关问题，如最可靠路径问题、最大容量路径问题、易达性评价问题和各种路径分配问题均可纳入最佳路径问题的范畴之中。无论判断标准和实际问题中的约束条件如何变化，其核心实现方法都是最短路径算法。
最短路径问题从算法研究的角度考虑最短路径问题通常可归纳为两大类：一类 是所有点对之间的最短路径，另一类是单源点间的最短路径问题。
网络分析：最佳路径问题
“最佳路径”中的“佳”包含很多含义，它不仅可以指一般地理意义上的距离 最短，还可以是时间最短、费用最少、线路利用率最高等标准。但是无论引申为何种判断标准，其核心实现方法都是最短路径算法。
最短路径的数据基础是网络，组成网络的每一条弧段都有一个相应的权值，用 来表示此弧段所连接的两结点间阻抗值。在数学模型中，这些权值可以为正值，也可以为负值。由于在GIS中一般的最短路径问题都不涉及负回路的情况，因此以下所有的讨论中假定弧段的权值都为非负值。
若一条弧段(vi，vj的权值表示结点vi和vj间的长度，那么道路u＝{e1，e2 ，…， ek}的长度即为u上所有边的长度之和。所谓最短路径问题就是在vi和vj之间的所有路径中，寻求长度最小的路径，这样的路径称为从vi到vj的最短路径。
最短路径问题的算法一般分为两大类：一类是所有点对间的最短路径，另一类 则是单源点间的最短路径问题，其各自的求解方法是不同的。
5.3.2最佳路径分析
最佳路径分析也称最优路径分析，以最短路径分析为主，一直是计算机科学、运筹学、交通工程学、地理信息科学等学科的研究热点。这里“最佳”包含很多含义，不仅指一般地理意义上的距离最短，还可以是成本最少、耗费时间最短、资源流量（容量）最大、线路利用率最高等标准。很多网络相关问题，如最可靠路径问题、最大容量路径问题、易达性评价问题和各种路径分配问题均可纳入最佳路径问题的范畴之中。无论判断标准和实际问题中的约束条件如何变化，其核心实现方法都是最短路径算法。
地理网络因地理元素属性的不同而表现为同形不同性的网络形式，为了进行网络路径分析，需要将网络转换成加权有向图，即给网络中的弧段赋以权值，权值要根据约束条件而确定。若一条弧段的权表示起始结点和终止结点之间的长度，那么任意两结点间的一条路径的长度即为这条路上所有边的长度之和。最短路径问题就是在两结点之间的所有路径中，寻求长度最小的路径，这样的路径称为两结点间的最短路径。
最短路径问题的表达是比较简单的，从算法研究的角度考虑最短路径问题通常可归纳为两大类：一类是所有点对之间的最短路径，另一类是单源点间的最短路径问题。
1.最短路径算法
（1）Dijkstra算法基本思想
戴克斯徒拉（Dijkstra）算法是E.W.Dijkstra于1959年提出的一种按路径长度递增的次序产生最短路径的算法，此算法被认为是解决单源点间最短路径问题比较经典而且有效的算法。其基本思路是：假设每个点都有一对标号（dj,pj），其中dj是从起源点s到点j的最短路径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法也称标号法或染色法，其基本过程如下：
①初始化。起源点设置为ds=0，ps为空，并标记起源点s ， V5
60记k=s，其他所有点设为未标记点。
100 30V4②检验从所有已标记的点k到其直接连接的未标记的点j的V0
10 距离，并设置20 10 V1
V3dj=min［dj,dk+lkj］
5 其中，lkj为从点k到j的直接连接距离。V250③选取下一个点。从所有未标记的结点中，选取dj中最小图5.37带权的有向图的一个i
di=min［dj,所有未标记的点j］
点i就被选为最短路径中的一点，并设为已标记的点。
④找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点，记为
i=j*
⑤标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，重复步骤②③④。图5.37为某一带权有向图，若对其施行Dijkstra算法，则所得从V0到其余各顶点的最短路径以及运算过程中距离的变化情况如表5.5所示。
表