寻找带约束的最短路径的方法

摘要

本发明公开了一种寻找带约束的最短路径的方法。能够在一个带有约束的路网中寻找指定起点和终点间可行的最短路径。用由多个节点和边组成的图表示路网，用三个节点组成的三元组(a,b,c)表示无法从a经过b到达c的禁行规则。本发明是在寻找路径时记录每个节点可能到达的所有路径，并在寻找下一节点时只选择不违反禁行规则约束的路径。最终通过对节点的选择寻找到满足约束条件的最短路径。本发明解决了传统最短路径寻找方法无法处理禁行约束的问题，满足智能交通等领域的实际需求。

主权项

一种寻找带约束的最短路径的方法，其特征在于该方法的步骤如下：1.1在给定的路网上寻找指定起点和终点的最短路径，路网是由表示路口的节点和表示连接路口的道路的边组成，指定的起点和终点都是图中的节点；路网有额外的禁行规则约束；1.2创建两个空表，分别称为OPEN和CLOSE，将路径的起点放入OPEN表；将路径起点的g属性设为0，h属性设为起点和终点的直线距离，f属性设为g和h的和，parent属性和parent_set属性设为空；1.3若OPEN表不是空表，从OPEN表中取出其中f最小的节点，表示为v，若v不是终点则对于与v有边连通的每个节点c执行以下操作后将v移入CLOSE表：1.3.1若v不是起点，则在v的parent_set属性中找一个节点到达信息gParent，gParent的node属性代表这一节点，使得从node经过v到达c是允许的，且选择的gParent是v的parent_set中所有可行节点中使得从起点经过v到c的路径是最短的，若v不是起点且找不到gParent则放弃当前节点c，继续处理下一节点；1.3.2若节点c已有比gParent的path更短的路径，则将节点v作为c的一个可行的到达节点加入c的parent_set，若存在不允许从任意节点经过c到达其他节点的禁行规则，则此时有可能通过v经c到达，因此将c加入OPEN表以便进一步更新c的后续节点；1.3.3若gParent的path比节点c已有的路径更短，或c没有已有路径，则将其c的parent设为v，c的g属性设为此路径的长度，c的h属性设为c到终点的直线距离，c的f属性设为g和h的和；若v不是起点，则将v和gParent的路径组成的节点到达信息作为c的一条路径加入c的parent_set，否则直接将v放入parent_set，并把c放入OPEN表，以便进一步更新c的后续节点的路径；1.4若OPEN表是空表则所需路径不存在，寻找失败；若OPEN表中取出的节点v为终点则寻找成功，从终点的parent_set属性中找到对应于终点的parent属性的路径即为从起点到终点的最短路径。