路径分析

路径分析(Path Analysis)

　　路径分析是一种找寻频繁访问路径的方法，它通过对Web服务器的日志文件中客户访问站点访问次数的分析，挖掘出频繁访问路径。

　　路径分析是GIS中最基本的功能，其核心是对最佳路径和最短路径的求解。

　　①最佳路径

　　从网络模型的角度看，最佳路径求解就是在指定网络的两结点间，找一条阻碍强度最小的路径。最佳路径的产生基于网线和结点转角(如果模型中结点具有转角数据的话)的阻碍强度。

　　例如，如果要找最短的路径，阻碍强度要预先设定为通过网线或在结点转弯处所花费的时间；如果要找费用最小的路径，阻碍强度就应该是费用。当网线在顺逆两个方向上的阻碍强度都是该网线的长度，而结点无转角数据或转角数据都是0时，最佳路径就成为最短路径。

　　在某些情况下，用户可能要求系统能一次求出所有结点间的最佳路径，或者要了解两结点间的第二、第三乃至第X条最佳路径。

　　②最佳遍历方案

　　另一种路径分析功能是最佳遍历方案的求解。

　　网线最佳遍历方案求解是给定一个网线集合和一个结点，求解最佳路径，使之由指定结点出发至少经过每条网线一次而回到起始结点。

　　结点最佳遍历方案求解则是给定一个起始结点、一个终止结点和若干中间结点，求解最佳路径，使之由起点出发遍历全部中间结点而达到终点。

　　(1)静态求最佳路径：由用户确定权值关系后，给定每条弧段的属性，当求最佳路径时，读出路径的相关属性，求最佳路径。

　　(2)N条最佳路径分析：确定起点、终点，求代价较小的几条路径。在实际应用中仅求出最佳路径并不能满足要求，可能NN某种因素不走最佳路径，而走近似最佳路径。

　　(3)最短路径：确定起点、终点和所要经过的中间连线，求最短路径。

　　(4)动态最佳路径分析：实际网络分析中权值是随着权值关系式变化的，而且可能会临时出现一些障碍点，所以往往需要动态地计算最佳路径。

　　路径分析包含了两个基本内容：一个是路径的搜索；另一个是距离的计算。路径搜索的算法与连通分析是一致的，通过邻接关系的传递来实现路径搜索。路径的长度(距离)以积聚距离(accumulated distance)来计算。距离的计算方法为：将栅格路径视做由一系列路径段(path segments)组成，在进行路径搜索的同时计算每个路径段的长度并累计起来，表示从起点到当前栅格单元的距离。这里路径段指的是在一定的精度范围内可以以直线段模拟和计算的栅格单元集合。

　　路径分析包含两大类：一是有预定轨迹网络的路径分析；二是无预定轨迹的路径分析。前者是比较常见的类型，例如交通网络中的最短路径分析、次短路径分析、最优路径分析以及网络的最小生成树分析等等，这类分析的特点是在空间中移动的对象只能沿着既定的路线移动；后者接近于表面分析，在空间中移动的对象有全部或者部分的自由度，没有明确的路径限制，无预定路径的路径分析就是要在给定的自由度内寻找满足特定条件的路径，比如通过沼泽地的路径选择、有暗礁海域的航线规划等等都属于无预定轨迹情况下的路径分析。

　　1.有预定轨迹的路径分析

　　有预定轨迹的路径分析主要包括最短路径分析、最优路径分析和最小生成树分析等。其中，最短路径分析是基础。最短路径算法的主要设计思想是：以具有同样拓扑结构和流限制属性的虚拟网络系统代替研究对象，虚拟网络每个点都有可燃性，在起点点火，火势沿网络路径传播，最先到达终点的火焰所经过的轨迹便是最短路径。路径点数据结构如下：

struct Path Point Class
{
TPoint tpThisPoint；／／当前点的坐标
in liLastPosition；／／本路径前驱点的索引值
bool bExtFlag；／／扩张标识
float fDistance；／／本路径当前的积聚距离
}

　　算法表述如下：

　　(1)读取流的属性，根据约束集更新网络基本拓扑，对结点数组赋初值。

　　(2)扫描研究区域，找到起点S和终点C。

　　(3)记起点S的积聚路径距离(以下简称距离)为0，并放人结点路径距离数组Path DiStanCe。

　　(4)对S点以八邻域方向按以下规则进行一次扩张：若相邻像素v为黑色(未经搜索过的路径)，则将v点的坐标记人路径距离数组，记v的前驱索引值为当前点在数组中的系列值，将v路径距离记为当前点的积聚距离与v到当前点的距离之和，将v的扩张标识记为未扩张。若相邻像素v为浅灰色(已经搜索过的路径)，则接着处理下一邻域方向。当前点的八邻域方向搜索完毕以后，对当前点加已扩张标识。

　　(5)对扩张得到的结点集合按其积聚距离进行处理：

　　①若最大积聚距离值与最小积聚距离值的差超过0．5，则按与最大积聚距离的差值以0．5为阂值进行分组，对差值大于0．5的结点按(4)中的规则进行一次扩张，将扩张结果集加人到差值小于0．5的结点集中。

　　②若最大积聚距离与最小积聚距离的差值小于0．5，则直接对扩张后得到的结点集进行新的扩张。

　　(6)重复(5)直至遇到终点或结点路径距离数组中没有未扩张结点。

　　(7)考查终点的八邻域像素，如果无绿色像素则转①，否则转②。

　　①起点与终点不连通，运算结束。

　　②找到最短路径。记录最短路径距离值，路径回溯方法为：从终点开始，根据数组中记录的前驱关系回溯路径，并标以标识色(深色)染路径直至起点，结束运算。

　　下图是上述算法的示例，其中深色的轨迹就是所得到的最短路径。

　　通过以上算法可以得到起点和终点数目都为1的最短路径，计算起点到其他n - 1顶点地球信息理论和零初始化问题的最短路径，只需继续扩张直到结点数组中没有未扩张结点，然后从其他n - 1个结点分别进行回溯，找到距起点的最短路径。

　　全源最短路径的算法可以首先遍历网络，记录网络中相邻两结点间的距离，得到邻接结点间的距离矩阵，然后采用Floyd方法计算所有点对之间的最短距离矩阵。

　　2.无预定轨迹的路径分析

　　流在空间中流动时，并不一定有严格的既定线状路径限制，而具有全部或者部分的自由度。例加航空、航海的航线等、无预定轨迹的最短路径分析，是有预定轨迹路径分析的广义问题，适用范围更广。对于具有全部自由度的流流动，可以抽象成平面上全连通网络的网络分析，所有结点之间都以直线连接，从而转化为普通的图论问题。无预定轨迹的路径分析主要侧重于障碍空间的路径分析，此类分析在网络分析、机器人学、最优化方法以及计算几何等领域中有重要的价值。