元胞自动机最短路径算法优化

发布时间：2019-09-27 03:23

【摘要】：概括了当前GIS中最短路径算法,分析了元胞自动机在最短路径分析算法中的原理及应用现状,并从两个方面对基于元胞自动机的最短路径算法进行优化即直线优化的元胞自动机最短路径算法。(1)将A*算法中的启发函数引入元胞自动机模型,提出了直线优化元胞自动机最短路径模型;(2)考虑道路网特征对最短路径算法的影响,得出具有道路网自适应性的最短路径分析模型。最后选取不同形态特征的shp道路网数据,验证了优化算法在实际应用中的适用性和高效性。
【图文】：

无向图,无向图,元胞

路信息，利用图论理论寻求出指定节点间的最短路径。CA最短路径算法的思想就是在此基础上将无向图的所有顶点定义为一个元胞集合，与某一元胞连通的所有节点组成该元胞的邻居集合，元胞状态根据演化规则分为未被寻路和已被寻路等若干离散状态。元胞初始状态均为未被寻路，从起始元胞开始，依据演化规则，其邻居元胞的状态发生翻转，在下一时刻相邻的元胞又依据规则并行的向各自相邻的节点演化，并记录元胞的变化信息，以此类推，直到终点元胞被寻路，最先到达目标节点的元胞演化记录就是所求的最短路径。以无向图G(图1)为例，构造CA模型:A=(d，S，N，f)，式中:元胞空间d={v1，v2，…，vn};元胞vx邻居为N(vx)={(vx，v)∈E∨(v，vx)∈E∨v=vx}。最短路径算法建立的关键是制定元胞的演化规则，并根据规则确定元胞的状态集合S。图1无向图GFig．1UndirectedgraphG学者针对元胞自动机在最短路径算法中的应用开展了广泛而深入的研究，产生了一系列研究成果。吴晓军和薛惠锋(2004)对元胞自动机在最短路径分析中的应用进行了探索，利用元胞自动机在元胞空间上的并行特性，采用元胞动态邻居、时间段自适应调整的方法，构造出一种新的基于元胞自动机扩展模型的图最短路径搜索算法，即通过简单规则的元胞状态演化，得到带权图的最短路径。定义状态集S={S_N，S_G，S_B，S_M};其中S_N表示初始状态，未被搜寻;S_G表示该元胞正在被搜寻，处于生长状态;S_B表示元胞状态正在向领导扩展，处于繁殖状态;S_M表示已经被搜寻结束，处于成熟状态。演化规则f设定为:假设t时刻，中心元胞为vx，剩余权(中心元胞到起始元胞的最短距离)记为r(vx)。(1)若vx为S_M状态，表示该点已被搜寻，状态不变。(2)?

最短路径算法,状态,状态翻转

(1)当中心元胞vx的状态为S_N时，考察邻居:若邻居存在S_B状态，，则翻转为S_G，且r(vx)=w(vn，vx)+g(vx);否则状态不变，且r(vx)=∞。(2)当中心元胞vx状态为S_M时，状态不变。(3)当中心元胞vx状态为S_B时，翻转为S_M。(4)当中心元胞vx状态为S_G时，考察邻居:若邻居存在S_B状态且g(vx)+wt－1(vn，vx)＜r(vx)，则r(vx)=g(vx)+wt－1(vn，vx);若r(vx)－min(r(vx))=0则状态翻转为S_B，否则状态不变。优化算法与原算法的元胞演化域的比较如图2所示。图2优化前与优化后基于CA的最短路径算法演化域Fig．2OptimizationbeforeandaftertheoptimizationoftheshortestpathalgorithmbasedontheCAevolutiondomain
【作者单位】：信息工程大学测绘学院;
【分类号】：P208;U495

【参考文献】