一种用于高速公路最短路径计算的矩阵压缩算法

摘要

本发明公开了一种用于高速公路最短路径计算的矩阵压缩算法，步骤如下：步骤一，使用迪杰斯特拉算法计算出高速公路最小费用路径的矩阵图；步骤二，进行矩阵行压缩，建立行标记数组Flag[N]（初始化为全false），逐行遍历前序矩阵，对Pre数组中的每一行，压缩成一个（列号c，值v）二元组集合RowListi；步骤三，进行矩阵列压缩：逐列遍历矩阵，对Pre数组中的每一列都压缩成一个（起始值s，终止值e，值v）的三元组集合ColListk，将特殊点和重复点在矩阵内压缩并忽略；步骤四，矩阵压缩完成，通过矩阵压缩算法，将前序数组进行压缩，使其所需要的的内存大大减小，且检索效率不会降低太多。

说明书

技术领域

本发明涉及高速公路算法技术领域，具体为一种用于高速公路最短路径计算的矩阵压缩算法。

背景技术

目前，高速公路的最小费用路径计算都是使用的迪杰斯特拉算法，迪杰斯特拉算法是计算从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主的要计算过程是采用贪心算法的策略，从起始点开始，每次遍历与起始点距离最近，并且从未访问过的顶点的邻接节点，直到扩展到终点为止。

简要的高速公路路网如图2所示，可以用以下方式进行建模：高速公路的收费门架和收费站入口和收费站出口作为有向图中的点，收费门架之间以及收费门架与收费站入口/出口之间的直接连接关系作为有向图的边，小客车经过收费门架的费用作为所有以该门架为终点的边的权值，终点为收费站出口的边的权值为0。

如说明书附图2中，门架0标记为点0，门架1标记为点1，门架2标记为点2，门架3标记为点3，门架4标记为点4，门架5标记为点5，门架6标记为点6，门架7标记为点7，收费站0入口标记为点8，收费站0出口标记为点9，收费站1入口标记为点10，收费站1出口标记为点11，收费站2入口标记为点12，收费站2出口标记为点13，收费站3入口标记为点14，收费站3出口标记为点15。

点0与点4直接连接，记为边0-4，值为2；

点1与点0直接相连，记为边1-0，值为2；

点1与点9直接相连，记为1-9，值为0；

点2与点1直接相连，记为边2-1，值为3；

点2与点11直接相连，记为边2-11，值为0；

点3与点2直接相连，记为边3-2，值为2；

点3与点13直接相连，记为边3-13，值为0；

点4与点5直接相连，记为边4-5，值为3；

点4与点9直接相连，记为边4-9，值为0；

点5和点6直接相连，记为边5-6，值为2；

点5和点11直接相连，记为边5-11，值为0；

点6与点2直接相连，记为边6-2，值为2；

点6与点7直接相连，记为边6-7，值为2；

点6与点13直接相连，记为边6-13，值为0；

点7与点15直接相连，记为边7-15，值为0；

点8与点0直接相连，记为边8-0，值为2；

点8与点5直接相连，记为边8-5，值为3；

点10与点1直接相连，记为边10-1，值为3；

点10与点6直接相连，记为边10-6，值为2；

点12与点2直接相连，记为边12-2，值为2；

点12与点7直接相连，记为边12-7，值为2；

点14与点3直接相连，记为边12-3，值为2。

建模后，形成如说明书附图3所示的有向图模型。

说明书附图3中所示的有向图通过迪杰斯特拉算法计算之后，能够得到一个最短路径二维矩阵，即前序矩阵Pre

为了获取i,j两点间的最短路径，需要用以下方式从Pre

获取Pre

由于高速公路模型的特殊性，即费用包含在收费门架的属性中，所以在获取路径的同时，通过车辆类型能够同时获取到最小费用。

如要获取从点8（收费站0入）至点13（收费站2出）的最短路径，则获取逻辑如下：

1. 获取Pre

2. 获取Pre

3. 获取Pre

4. 此时已经获取了最短路径，为8,5,6,13。

当前技术方案的空间复杂度为O(n2)，主要内存占用空间为前序数组Pre

为此，我们提出一种用于高速公路最短路径计算的矩阵压缩算法。

发明内容

本发明的目的在于提供一种用于高速公路最短路径计算的矩阵压缩算法，以解决上述背景技术中提出的问题。

为实现上述目的，本发明提供如下技术方案：一种用于高速公路最短路径计算的矩阵压缩算法，步骤如下：

步骤一，使用迪杰斯特拉算法计算出高速公路最小费用路径的矩阵图；

步骤二，进行矩阵行压缩，建立行标记数组Flag

步骤三，进行矩阵列压缩：逐列遍历矩阵，对Pre数组中的每一列都压缩成一个（起始值s，终止值e，值v）的三元组集合ColList

步骤四，矩阵压缩完成；

步骤五，矩阵检索。

优选的，若第i行不为-1的值数量小于或等于（N/10），则将Flag

优选的，在步骤三中，对于任意一行i，若Flag

优选的，在步骤四中，若点k为收费站入口，则其他任意点都无法到达该点，列k所有的值均为-1，压缩后的三元组集合List

优选的，在步骤三中，Pre数组中，对于任意点i，Pre

优选的，在步骤五中，首先，获取行标记Flag

然后，在RowList

最后，在ColList

本发明至少具备以下有益效果：

通过矩阵压缩算法，将前序数组进行压缩，使其所需要的的内存大大减小，且检索效率不会降低太多。

附图说明

图1为本发明逻辑框图；

图2为简要的高速公路路网图；

图3为高速公路有向图模型；

图4为简单高速公路路网前序矩阵图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

请参阅图1-4，本发明提供一种技术方案：一种用于高速公路最短路径计算的矩阵压缩算法，包括：。

由于高速公路路网模型结构相对简单，大部分点只与1-2个点直接连接，少部分点会与3个或更多的点直接连接。如矩阵1所示，在迪杰斯特拉算法运行之后，前序矩阵中的每一列会有大量的重复数值，可以针对矩阵中每一列进行压缩；为了提高列压缩效率，减少列中值-1的干扰，可以先做行压缩，再做列压缩。基于这个考虑，建立以下矩阵压缩算法：

步骤一，使用迪杰斯特拉算法计算出高速公路最小费用路径的矩阵图；

步骤二，先进行矩阵行压缩：建立行标记数组Flag

步骤三，再进行矩阵列压缩：逐列遍历矩阵，对Pre数组中的每一列都压缩成一个（起始值s，终止值e，值v）的三元组集合ColList

若点k为收费站入口，则其他任意点都无法到达该点，列k所有的值均为-1，压缩后的三元组集合List

Pre数组中，对于任意点i，Pre

步骤四，矩阵压缩完成。

通过这个压缩算法，对矩阵1进行压缩，可以得到以下行标记数组：

Flag

得到以下16个行集合表（Flag

RowList0:[]

RowList1:[]

RowList2:[]

RowList3:[]

RowList4:[]

RowList5:[]

RowList6:[]

RowList7:[(15, 7)]

RowList8:[]

RowList9:[]

RowList10:[]

RowList11:[]

RowList12:[]

RowList13:[]

RowList14:[]

RowList15:[]

以下16个列集合表：

ColList0:[(0, 6, 1), (8, 8, 8), (10, 14, 1)];

ColList1:[(0, 8, 2), (10, 10, 10), (12, 14, 2)];

ColList2:[(0, 1, 6), (3, 3, 3), (4, 10, 6), (12, 12, 12), (14, 14,3)];

ColList3:[(0, 12, -1), (14, 14, 14)];

ColList4:[(0, 14, 0)];

ColList5:[(0, 6, 4), (8, 8, 8), (10, 14, 4)]

ColList6:[(0, 8, 5), (10, 10, 10), (12, 14, 5)]

ColList7:[(0, 10, 6), (12, 12, 12), (14, 14, 6)]

ColList8:[]

ColList9:[(0, 0, 4), (1, 3, 1), (4, 4, 4), (5, 6, 1), (8, 8, 4), (10,14, 1)]

ColList10:[]

ColList11:[(0, 1, 5), (2, 3, 2), (4, 5, 5), (6, 6, 2), (8, 10, 5),(12, 14, 2)]

ColList12:[]

ColList13:[(0, 2, 6), (3, 3, 3), (4, 12, 6), (14, 14, 3)]

ColList14:[]

ColList15:[(0, 14, 7)]

检索矩阵的方式由之前通过ij两点直接取Pre

1.获取行标记Flag

2.在RowList

3.在ColList

如在上面的压缩结果中查找Pre

1.确定行标记Flag

2.ColList

3.对列表前半部分折半获得三元组ColList

本发明的技术关键点在于：

1.对高速公路路网模型在应用时占用的内存按照算法进行压缩，以满足门架系统内存的要求；

2.在做矩阵压缩的同时，通过优化查找算法提高矩阵检索的速度。

本发明实验得到的效果：

本发明针对某省高速路网进行测试，该省高速路网具有530个收费门架，199个收费站，1267个直接连接关系，体现到高速模型中，有向图模型中具有530+199*2=928个点，1267条边。

针对该有向图进行两点间的最短路径查询测试，得到以下结果：

该算法能够有效压缩高速公路路网模型中的前序数组，压缩比例为95.8%，平均耗时由0.011毫秒增长至0.023毫秒，高速公路门架收费计算时间上限为250毫秒，压缩算法能够完全满足高速公路通行的时限需求。

需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。

尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同物限定。