论文部分内容阅读
摘 要：首先本文简单概括的论述了传统Dijkstra算法的基本思想；其次提出了该算法在实现方法上存在的一些不足之处，然后从数据存储结构和搜索方式上对其进行优化，并利用Matlab对改进算法进行了相应的仿真分析与测试，结果表明，改进的Dijkstra算法在实际交通中具有可行性。
关键词：智能交通系统；最短路径；Dijkstra算法
中图分类号：TP311.52
针对城市交通拥堵我们提出了智能交通系统，而最短路径算法是智能交通系统最关键的问题之一[1]。目前大家公认的最经典的路径规划算法是Dijkstra算法，它是1959年荷兰著名的科学家艾兹格.迪科斯彻提出来的，并以其名字命名的，它是建立在抽象的图论模型上，把路网抽象为图论中的边，以边的权来表示路网中的相关信息。它也可用来找出图中指定节点到其他节点的最短距离，其主要思想是从源点求出长度最短的一条路径，然后通过对路径长度迭代得到从源点到其他目标节点的最短路径。
如果按照传统的Dijkstra算法，网络图会比较复杂、顶点和边数也会比较多，这样会造成计算量很大、时间开销非常大，从而影响了算法的速度、降低了算法的效率。本文针对Dijkstra算法在实现方法上存在的一些不足之处对其进行改进，改进的Dijkstra算法在实际交通中具有可行性。
1 传统的Dijkstra算法
1.1 算法简单介绍
1.2 算法存在的不足
传统Dijkstra算法虽然比较简单，容易实现，理论上用该算法解决最短路径问题已经很成熟[2]，但是通过仔细分析与研究可知该算法在实际应用中其存在以下几点不足：
（1）虽然该算法用邻接矩阵表示路网中结点和路段的特征在数据结构上简单明了而且容易实现，但是其存储量为N×N；如果结点数较多时，将会有大量的无效的0元素和∞元素，这会占用计算机巨大的存储空间，如果再进行矩阵间的运算，那么运行速度会非常的慢；另外邻接矩阵也不能全面地表示真实路网中的许多信息，如结点属性信息及路段的属性信息等等。
（2）在Dijkstra算法实现的过程中，它主要步骤就是从数组lengs的结点中选择一个权值最小的结点，这是一个循环比较的过程；如果不采用任何措施，在算法的每次迭代中数组lengs中的结点将以无序的形式存储；那么要选择一个权值最小的结点就必须把所有的结点都全部扫描一遍，在大数据量的情况下，这无疑是一个制约程序运行速度的关键因素。
（3）用数组存放结点的最短路径权值，在搜索过程中应选择最小的路径权值加入到数组know中。这个选择没有考虑目标结点所处的位置和它的有向性，这是贪心算法的思想，即在每一步骤都保证局部最优，但从整体来看可能不是最优的结果。
2 Dijkstra算法的优化
根据上面分析得传统Dijkstra算法的三点不足之处，然后从数据存储结构和搜索方式上对其进行优化。
2.1 从数据存储方式上优化——采用改进型前向关联边存储方式
我们把电子地图道路网络层简称为路网，它有两个基本要素是：第一：结点（node）；第二：路段（segment）。结点包括道路的交叉口或路头的断点；路段一般包含边（edge）或弧段（arc），两结点之间的路段称为边，假若我们规定了路段的方向，就称为弧段。更具路网的两个基本要素，改进型前向关联边存储结构用到的存储单元有三个：
（1）指针数组：按节点编号的顺序对每个结点分配一个指针，用来存储由此结点发出的第一条弧在弧集中的起始位置，设长度为m；
（2）结点序列数组：指针数组中的指针所指向的结点序列，它是按照弧段权重值的大小排列的，设长度为n；
（3）弧段权重数组：对应指针数组的下标和结点序列数组元素合在一起所描述的弧段，存储该弧段所代表路段上的道路长度，设长度为n。
改进型前向关联边存储结构优势归结为如下三点：
（1）电子地图的路网数据结构更加清晰。虽然改进型前向关联边存储结构占用的存储空间为m+2n，但是此方法可以将节点与弧段的关系清晰的表达出来；也可方便地对某一给定结点发出的所有弧段进行操作，提高了算法的搜索效率。
（2）在弧段权重数组中已对各弧段的权值按大小进行排序了这就使得路径搜索时不再需要比较弧段权重值，搜索速度加快了。
（3）暗含了交叉口行为。这是以往其它存储结构所不具备的特性例如车辆在给定交叉口时允许采取的操作如直行、左转、右转等等也通过该存储结构隐含地表达出来。
2.2 从搜索方式上优化——双向搜索方式
图1 双向搜索算法基本思想
3 算法改进后仿真结果
本文利用MATLAB对优化后的Dijkstra算法和传统Dijkstra算法进行测试和实验对比。为了更好地说明优化后的Dijkstra算法的有效性，本文自行用MATLAB语言编制了最短路径搜索程序并进行了仿真和测试。采用自绘制的地图，共5张，第一张图16个节点，共24条弧；第二张图32个节点，共55条弧；第三张图45个节点，共75条弧；第四张图64个节点，共111条弧；第五张图80个节点，共139条弧。计算结果如表1所示。从表1可以看出，两种算法的计算量有很大的区别，优化后的Dijkstra算法较之传统的Dijkstra算法在运算量方面有很大幅度的减少，而且这种减少的程度在结点数目增加或者地图更大、更复杂时会变得越来越明显。对于实际的智能交通系统来说，由于实际的地图会很大，使用优化后的Dijkstra算法效果会非常显著。
4 结论
本文自行编制的MATLAB程序对算法的两点优化进行了验证和对传统的Dijkstra算法进行了对比，实验结果发现：传统的Dijkstra算法与优化后的Dijkstra的计算结果相当，但优化后的算法的运行速度比传统的Dijkstra算法的运行速度要快一些，更能快速找出从源点到目标结点的最短路径。
参考文献：
[1]百度百科 Dijkstra算法：http：//baike.baidu.com/view/7839.htm.
[2]蔡俊，李钦富，王金泉.一种Dijkstra优化算法的研究与实现[J].信息与技术，2011，（4）：104-107.
[3]李臣波，刘润涛.一种基于Dijkstra的最短路径算法[J].哈尔滨理工大学学报，2008，（3）：35-37.
[4]周培德.交通道路网中任意两点之间最短路径的快速算法[J].计算机工程与科学，2002，24（2）：35-37.
作者简介：杜雪（1987-），女，河南驻马店人，中原工学院计算机学院2011级硕士研究生，计算机应用技术专业，研究方向：图像图像处理；刘卫光（1966-），河南新乡人，计算机学院副院长，教授，博士，硕士生导师。
作者单位：中原工学院，郑州 450007
关键词：智能交通系统；最短路径；Dijkstra算法
中图分类号：TP311.52
针对城市交通拥堵我们提出了智能交通系统，而最短路径算法是智能交通系统最关键的问题之一[1]。目前大家公认的最经典的路径规划算法是Dijkstra算法，它是1959年荷兰著名的科学家艾兹格.迪科斯彻提出来的，并以其名字命名的，它是建立在抽象的图论模型上，把路网抽象为图论中的边，以边的权来表示路网中的相关信息。它也可用来找出图中指定节点到其他节点的最短距离，其主要思想是从源点求出长度最短的一条路径，然后通过对路径长度迭代得到从源点到其他目标节点的最短路径。
如果按照传统的Dijkstra算法，网络图会比较复杂、顶点和边数也会比较多，这样会造成计算量很大、时间开销非常大，从而影响了算法的速度、降低了算法的效率。本文针对Dijkstra算法在实现方法上存在的一些不足之处对其进行改进，改进的Dijkstra算法在实际交通中具有可行性。
1 传统的Dijkstra算法
1.1 算法简单介绍
1.2 算法存在的不足
传统Dijkstra算法虽然比较简单，容易实现，理论上用该算法解决最短路径问题已经很成熟[2]，但是通过仔细分析与研究可知该算法在实际应用中其存在以下几点不足：
（1）虽然该算法用邻接矩阵表示路网中结点和路段的特征在数据结构上简单明了而且容易实现，但是其存储量为N×N；如果结点数较多时，将会有大量的无效的0元素和∞元素，这会占用计算机巨大的存储空间，如果再进行矩阵间的运算，那么运行速度会非常的慢；另外邻接矩阵也不能全面地表示真实路网中的许多信息，如结点属性信息及路段的属性信息等等。
（2）在Dijkstra算法实现的过程中，它主要步骤就是从数组lengs的结点中选择一个权值最小的结点，这是一个循环比较的过程；如果不采用任何措施，在算法的每次迭代中数组lengs中的结点将以无序的形式存储；那么要选择一个权值最小的结点就必须把所有的结点都全部扫描一遍，在大数据量的情况下，这无疑是一个制约程序运行速度的关键因素。
（3）用数组存放结点的最短路径权值，在搜索过程中应选择最小的路径权值加入到数组know中。这个选择没有考虑目标结点所处的位置和它的有向性，这是贪心算法的思想，即在每一步骤都保证局部最优，但从整体来看可能不是最优的结果。
2 Dijkstra算法的优化
根据上面分析得传统Dijkstra算法的三点不足之处，然后从数据存储结构和搜索方式上对其进行优化。
2.1 从数据存储方式上优化——采用改进型前向关联边存储方式
我们把电子地图道路网络层简称为路网，它有两个基本要素是：第一：结点（node）；第二：路段（segment）。结点包括道路的交叉口或路头的断点；路段一般包含边（edge）或弧段（arc），两结点之间的路段称为边，假若我们规定了路段的方向，就称为弧段。更具路网的两个基本要素，改进型前向关联边存储结构用到的存储单元有三个：
（1）指针数组：按节点编号的顺序对每个结点分配一个指针，用来存储由此结点发出的第一条弧在弧集中的起始位置，设长度为m；
（2）结点序列数组：指针数组中的指针所指向的结点序列，它是按照弧段权重值的大小排列的，设长度为n；
（3）弧段权重数组：对应指针数组的下标和结点序列数组元素合在一起所描述的弧段，存储该弧段所代表路段上的道路长度，设长度为n。
改进型前向关联边存储结构优势归结为如下三点：
（1）电子地图的路网数据结构更加清晰。虽然改进型前向关联边存储结构占用的存储空间为m+2n，但是此方法可以将节点与弧段的关系清晰的表达出来；也可方便地对某一给定结点发出的所有弧段进行操作，提高了算法的搜索效率。
（2）在弧段权重数组中已对各弧段的权值按大小进行排序了这就使得路径搜索时不再需要比较弧段权重值，搜索速度加快了。
（3）暗含了交叉口行为。这是以往其它存储结构所不具备的特性例如车辆在给定交叉口时允许采取的操作如直行、左转、右转等等也通过该存储结构隐含地表达出来。
2.2 从搜索方式上优化——双向搜索方式
图1 双向搜索算法基本思想
3 算法改进后仿真结果
本文利用MATLAB对优化后的Dijkstra算法和传统Dijkstra算法进行测试和实验对比。为了更好地说明优化后的Dijkstra算法的有效性，本文自行用MATLAB语言编制了最短路径搜索程序并进行了仿真和测试。采用自绘制的地图，共5张，第一张图16个节点，共24条弧；第二张图32个节点，共55条弧；第三张图45个节点，共75条弧；第四张图64个节点，共111条弧；第五张图80个节点，共139条弧。计算结果如表1所示。从表1可以看出，两种算法的计算量有很大的区别，优化后的Dijkstra算法较之传统的Dijkstra算法在运算量方面有很大幅度的减少，而且这种减少的程度在结点数目增加或者地图更大、更复杂时会变得越来越明显。对于实际的智能交通系统来说，由于实际的地图会很大，使用优化后的Dijkstra算法效果会非常显著。
4 结论
本文自行编制的MATLAB程序对算法的两点优化进行了验证和对传统的Dijkstra算法进行了对比，实验结果发现：传统的Dijkstra算法与优化后的Dijkstra的计算结果相当，但优化后的算法的运行速度比传统的Dijkstra算法的运行速度要快一些，更能快速找出从源点到目标结点的最短路径。
参考文献：
[1]百度百科 Dijkstra算法：http：//baike.baidu.com/view/7839.htm.
[2]蔡俊，李钦富，王金泉.一种Dijkstra优化算法的研究与实现[J].信息与技术，2011，（4）：104-107.
[3]李臣波，刘润涛.一种基于Dijkstra的最短路径算法[J].哈尔滨理工大学学报，2008，（3）：35-37.
[4]周培德.交通道路网中任意两点之间最短路径的快速算法[J].计算机工程与科学，2002，24（2）：35-37.
作者简介：杜雪（1987-），女，河南驻马店人，中原工学院计算机学院2011级硕士研究生，计算机应用技术专业，研究方向：图像图像处理；刘卫光（1966-），河南新乡人，计算机学院副院长，教授，博士，硕士生导师。
作者单位：中原工学院，郑州 450007