算法如下：

　　令E={V0｝，K=F{V0｝;

　　第一步，通过堆排序将K集合调整为小顶堆，取数组首元素为堆顶点a，并将a存入E中;

　　第二步，更新a的邻接点集合与E集合的差集(F{a｝-E)中的任一点的最短路径值;

　　第三步，查找E中所有节点的邻节点并集(F(E)并集)与E集合的差集，依次存入数组K中，覆盖原数组节点，设置一计数器i纪录节点个数;

　　第四步，将数组中前i个元素按当前最短路径调整为小顶堆，取堆顶点为下一个节点添加至E中;

　　直至所有节点都加入E中。

　　通过堆排序算法，改变数据组合方式和纪录空间，使得与传统的无序搜索相比，节约时间和执行效率。

　　4.2.2最短路径诱导算法

　　智能诱导的关键技术是最短时间路径的选取。传统的算法以Dijkstra和Floyd算法为主，忽略网络结构和时间权重变化。然而交通领域中时间权重时刻变化，单独使用该算法与实际最短时间路径相差较大。在路径选择时，比较实时交通路段权重与历史路段权重以达到最短时间[6]。因此传统的算法所得的最短时间路径实用性差。本文在FCM聚类预测基础上，构造时间权重，同时采用矩形搜索算法减少搜索范围，改进传统Dijkstra算法。

　　对于时间权重的选取，常选取出行时间、费用和距离。本系统选取时间，为结合实际路网状况，将路段长度与聚类分析的车流速度比值定义为时间权重。

　　矩形区域搜索算法[7,8]，考虑到实际路网中的起终点都是固定的，从而最短路径对应的最大距离也是固定的。通过以起终点坐标和统计分析长轴建立极限椭圆方程，该椭圆的最小外接正矩形就是具体的搜索范围。具体算法如下：

　　第一步，起终点代表性节点集合A和B，C=A×B={(a,b)a ƐA，b ƐB}，C为节点对;

　　第二步，C中节点对的欧式距离L和最短路径长度P，K为两者比值;

　　第三步，对C进行统计分析，当K中总数满足一定的置信水平的元素，K不大于某一特定值t， 则椭圆长轴为2m=t×L;

　　第四步，起终点(x1，y1)和(x2，y2)，得出极限椭圆为：

　　式4

　　式中：

　　求得x和y的极值为式5，搜索区域为椭圆的外接矩形(图3)。改进Dijskra算法步骤(图4)，通过矩形搜索算法减少搜索区域，再分析实时数据是否突发状况，若是采用实时权重，否则采用FCM聚类时间权重，最后采用Dijkstra算法进行最短路径预测。对比于传统算法与动态交通算法，提高实时性和减少存储量。

　　式5

　　图3 矩形搜索算法区域图 图4改进Dijskra算法流程图

　　Figure 3 Rectangular area map search algorithm Figure 4 Improved Dijskra algorithm flowchart

　　5算法评价

　　5.1 复杂度的分析

　　对于空间复杂度而言，传统Dijkstra算法采用图论中的邻接矩阵算法，因而存储量为n2，其空间复杂度为O(n2)。而本文改进Dijkstra算法采用邻接表的链式存储结构，对于无向图，其存储量为O(T+2n)(T为节点表中相连的边数)，同时采用L(n)存储起点到其他节点的最短路径值，K(n)表示待排序节点，总的空间复杂度为O(T+4n)。由于n>>T，故该矩形搜索算法较传统算法节省空间，利用率有所提高。

　　对于时间复杂度而言，传统Dijkstra算法采用广度搜索，遍历所有节点，生成最短路径，运算时间为n2，其时间复杂度为O(n2)。改进Dijkstra算法采用查找待排序和堆排序，由于待排序的集合为所有已标记的节点的并集与标记集合的差集，最多为T次;排序过程中，调整次数最大为二叉树的高度log(n)，执行n次，运行时间为O(nlog(n)+Tn)。矩形时间复杂度远远减少运算时间，提高运算速率。

　　由此可见，改进Dijkstra算法减少计算节点和计算时间，对于实际线网中大量节点，其优势较为明显，效率很高。

　　5.2 效率分析

　　传统Dijkstra算法是一种广度搜索，即全方向性搜索，由计算机模拟可得其搜索范围类似于圆形，如图6所示。而改进Dijkstra算法如图6所示，搜索范围类似于椭圆形。可以从宏观上观察出改进Dijkstra算法减少运算范围，达到优化结果。

　　图5 传统Dijkstra算法搜索区域 图6 改进算法搜索区域

　　Figure 5 traditional Dijkstra Figure 6 improved Dijkstra

　　algorithm search range algorithm search range

　　由公式4-5，可得出传统Dijkstra算法和改进Dijkstra算法的面积分为如式6和式7。分析可得改进Dijkstra算法搜索面积的极值。为对比搜索效率，将改进Dijkstra算法极大值与传统Dijkstra算法进行对比，得出改进Dijkstra算法面积仅占传统Dijkstra算法的10%左右。由此可见改进Dijkstra算法路径搜索较传统算法减少90%左右。

　　式6

　　式7

　　式8

　　式9

　　通过传统Dijkstra算法和改进Dijkstra算法的对比分析，可知改进Dijkstra算法从时间空间和范围上，均优于传统Dijkstra算法，可行性较强。

　　6 总结

　　通过分析现有管理模式问题，提出新型解决“停车难”的技术手段—智能交通。从泊位预约和智能诱导两个阶段介绍智能停车的具体操作。然后，介绍关键技术：FCM聚类算法预测车流速度、最短路径诱导算法(改进Dijskra算法)。最后通过对传统Dijkstra算法和改进Dijkstra算法的对比分析可知该诱导系统的实时性和可行性，可以很好的缓解“停车难”问题。

 2/2   首页 上一页 1 2