大规模图上具有约束的多起点路径规划算法_普林发.pdf

2023，59（6）图作为一种重要的数据模型，常常用来刻画真实世界中两个实体之间的关系。图数据管理中，最短路径规划是一类基本且重要的研究问题，其在现实世界中具有广泛的应用，例如：在道路交通网中，最短路径规划可为用户提供起点和终点之间的最优路径；在社交网络网络中，最短路径规划反映了两个指定用户之间发生最直接联系的方式。现实应用中的路径规划往往并非简单的，而是具有约束的。例如，在交通网络图中，用户需要从甲地到达乙地，且要求在到达乙地的过程中经过v1,v2,vn地，大规模图上具有约束的多起点路径规划算法普林发1，2，3，杨雅君1，2，3，王鑫21.人民网传播内容认知国家重点实验室，北京 1007332.天津大学 智能与计算学部，天津 3003503.天津大学 国际工程师学院，天津 300350摘要：路径规划查询是图数据上的一个基本问题，在众多的领域都有重要的应用价值。通常在实际问题中查询的路径是具有约束的，例如在外卖配送和共享出行问题中路径具有节点约束，其路径需要满足节点之间的先后关系约束。目前对于具有节点约束的路径查询问题，大多数的工作都在研究单起点的节点约束路径查询，但很难拓展到多起点节点约束问题中。因为具有节点约束的多起点路径查询问题是NP-hard的，所以该问题的大多数已有方法是使用贪心增量处理，但对于处理静态规则集拓展性不足。因此，提出了基于子路径的启发式算法和基于约束集拓展的精确算法，并在真实数据集上验证了算法的有效性。实验结果表明，启发式算法能够给出问题的精确解，而启发式算法能快速给出较好的近似解。关键词：图数据；路径查询；最优化问题；启发式算法文献标志码：A中图分类号：TP311.1doi：10.3778/j.issn.1002-8331.2109-0496Constrained Multi-Start Path Planning Algorithm on Large-Scale GraphsPU Linfa1，2，3,YANG Yajun1，2，3,WANG Xin21.State Key Laboratory of Communication Content Cognition,Beijing 100733,China2.College of Intelligence and Computing,Tianjin University,Tianjin 300350,China3.Tianjin International Engineering Institute,Tianjin University,Tianjin 300350,ChinaAbstract：Path planning query is a basic problem on graph data,which has important application value in many fields.Usually,the path queried in actual problems is constrained.For example,in the problems of food delivery and shared travel,the path has node constraints,and the path needs to meet the constraints of the sequence relationship between nodes.Atpresent,for the path query problem with node constraints,most of the work is on the single-start node-constrained pathquery,but it is difficult to extend to the multi-start node constraint problem.Because the multi-start path query problemwith node constraints is NP-hard,most of the existing methods for this problem use greedy incremental processing,but itis insufficient for processing static rule sets.Therefore,a heuristic algorithm based on sub-paths and an accurate algorithmbased on constraint set expansion are proposed,and the effectiveness of the algorithm is verified on the real data set.Theexperimental show that the heuristic algorithm can give an accurate solution to the problem,and the heuristic algorithmcan quickly give a better approximate solution.Key words：graph data;path querying;optimization problem;heuristic algorithm基金项目：传播内容认知国家重点实验室课题资助项目（A32003）。作者简介：普林发（1997），男，硕士研究生，CCF学生会员，研究方向为图数据管理、图的查询问题，E-mail：；杨雅君（1983），男，博士，副教授，CCF普通会员，研究方向为图数据管理、图挖掘；王鑫（1981），男，博士，教授，CCF高级会员，研究方向为图数据管理、图挖掘。收稿日期：2021-09-29修回日期：2021-11-17文章编号：1002-8331（2023）06-0283-08Computer Engineering and Applications计算机工程与应用283Computer Engineering and Applications计算机工程与应用2023，59（6）同时用户要求在经过某些vj之前需要先经过某些vi，寻找满足这样约束的最短路径问题被称为具有约束的最短路径规划问题。目前，关于具有约束的路径规划问题主要集中于单起点的具有约束的路径规划，即给定一个起点vs和一个终点ve以及约束规则R，计算从vs到达ve的满足约束规则R的最短路径。然而，随着现实业务场景变化越来越复杂，多起点的具有约束的路径规划也变得越来越重要。例如，在道路交通网络上的外卖配送业务场景中，多个配送员处在不同位置开始配送。在业务场景中，多个商家的外卖商品需要配送给多个相应用户，如何以多个配送员所在位置作为起点，规划多条路径经过业务中的全部商家和用户位置，且每条路径上均满足商家在其提供服务的用户之前经过。在该实例中，道路交通网络被刻画成一张图G()V,E，该问题可形式化描述为：给定一个起点的集合Vs和一个约束规则集合R，为每个起点规划一条路径得到一个路径集合，使得路径集合共同经过约束规则集合中的全部顶点，且满足规则全部规则。该问题被称为具有节点约束的多起点路径规划问题。具有约束的单起点路径规划问题是具有约束的多起点路径规划问题的平凡情况。具有约束的单起点路径规划问题已被证明是NP-hard问题，如果直接拓展具有约束的单起点路径规划算法解决多起点路径规划，效率很低，因为将规则集R(|R=n)进行划分并分配给不同的起点集Vs,(|Vs=m)中的起点将会产生至少mn个单起点节点约束问题，而通常m和n的值非常大。对于多起点节点约束路径查询，目前解决多起点的节点约束路径查询问题的精确算法的基本思想1可归纳为：将规则集视为随时间到来的流数据，当一个约束节点到来的时候，计算所有可能的情况并取达到最小代价的方案。该方法会存在以下两个缺点：（1）现实的情况下，约束集的顺序并不是固定的。约束集之间有相互影响而关系；（2）在增量计算过程中，需要遍历所有可能的情况，而最后只需要选择其中增量值最小的路径，从而造成了计算开销的提高。另一类解决多起点节点约束的路径查询问题的方法2-3是设计启发式算法，但是其并不能够保证算法的结果总是可接受的，并不一定能够得到精确解。因此本文考虑约束之间的相互影响，对约束集全局规划而不是规定执行顺序设计了基于约束集拓展的尽早过滤的解空间缩减精确算法，同时因为该问题是NP-hard问题，因此设计了基于子路径的启发式算法。并在不同的真实数据集上进行了大量实验验证算法的有效性。实验结果表明，相比已有的算法该算法能够得到更优的解。本文的主要贡献如下：（1）设计了可求解节点约束的多起点路径查询问题精确解的基于约束集拓展的解空间缩减精确算法。（2）设计了可快速得到近似解的基于子路径的启发式算法，在可接受的时间内能够提供更好的近似解。（3）在不同的真实数据集上进行大量实验验证了算法的有效性，并与已有算法进行比较，实验结果验证了本文算法有效性。1问题形式化定义无向加权图可以表示为G(V,E,w)（简称G），V=vi表示图G中节点的集合；EVV表示图G中全部边的集合，任一条边eE可以表示为e=(vi,vj)，其中，vi,vjV；w是权重函数，并为图G中的每条边e=(vi,vj)E指定非负权重wi,j，即wi,j=w(vi,vj)。分别用|V和E|表示图G中节点的数目和边的数目。定义1（起点集）SV，表示图G中可将之作为起点构建路径的节点集合，即S=s1,s2,sm，其中，siV(1im)，|S=m表示起点集合的大小。定义 2（约束集）R是偏序关系的集合，即R=r1,r2,rn，其中，rk=(1kn),vi,vjV，表示vivj。|R=n表示约束偏序的数目。注意：约束集R中不存在环，即R中不存在一个,的约束子集，其中v1,v2,vk-1,vkV。定义3（具有约束的多起点路径集）给定图G(V,E,w),起点集S，约束集R，如果存在路径集P满足以下条件，则称其为起点集S基于约束集R的路径集。（1）|P=|S|，且对于每个节点viS，在P中有且仅有一条以vi为起点的路径piP。（2）对于每个偏序关系R，在P中有且仅有一条存在从vi到vj的子路径vivj的路径piP。本文主要解决具有节点约束的多起点路径查询问题，给定图G上的一个起点集S，以及约束集R，返回起点集S基于约束集R的最优路径集，表示为P*S,R，是指起点集S基于约束集R的所有路径集中路径集权重w()P=piPw(pi)最小的路径集。文献1-2证明了单起点的规则路径是一个NP-hard问题。而单起点规则路径是本文定义的多起点约束路径当|S=1时的特殊情况，因此本文定义的多起点约束路径问题也是一个NP-hard问题。2基于约束集拓展的精确算法整体的思想是：构建每个节点的所有可能后缀路径，然后从后缀路径集选择满足约束集的后缀路径组合，再将选择出来的后缀路径分配给起点集。2842023，59（6）2.1生成满足约束R的后缀路由集合用偏序关系ri=R表示为ri=，即，v=r+i,u=r-i。令IR表示规则点集，表示R中所有出现的节点的集合，即IR=r+1,r-1,r+2,r-2,r+n,r-n。用per(IR)表示IR的所有排列的集合，如果有一个序列A，若AIR，且|A=l，A中无重复元素，则称序列A是集合IR的一个l-排列，记Cl2n(IR)为集合IR的所有l-排列的集合，其中2n=|IR|。定义4（满足约束集的路由）路由Rt是满足约束集R的路由，当且仅当对Rt中的任意一个节点vi存在一个节点vj在其之后使得R或在其之前使得R，记为RtR。记路由RtR前加一个前缀节点v0构成的路由为Rtv0R。称在路由Rtv0R上路由RtR是节点v0的后缀路由。定理1 对于v1,v2,v|SS,SFXv1=SFXv2=SFXv|S