买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网获悉西安理工大学申请的专利基于凝聚层次的最短路径分治搜索方法获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN117251642B 。

龙图腾网通过国家知识产权局官网在2026-02-24发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202311085242.0，技术领域涉及：G06F16/9536；该发明授权基于凝聚层次的最短路径分治搜索方法是由魏嵬;李林峰;郭梦星设计研发完成，并于2023-08-25向国家知识产权局提交的专利申请。

本基于凝聚层次的最短路径分治搜索方法在说明书摘要公布了：本发明公开了基于凝聚层次的最短路径分治搜索方法，通过引入网络分层、限定搜索层级、分治搜索等，提高算法的运行效率，其中，采用了网络分层将网络节点按照凝聚层次聚类方法进行划分，得到多个层次的子图，从而降低了搜索的复杂度，还通过限定搜索层级将搜索范围限制在一定的层次内，避免了搜索过程中的无效计算，同时，为了进一步提高搜索效率，采用分治搜索将整个搜索过程划分为多个子任务并同时进行，整个搜索方法可以精准且高效地在边缘计算网络中进行最短路径搜索。

本发明授权基于凝聚层次的最短路径分治搜索方法在权利要求书中公布了：1.基于凝聚层次的最短路径分治搜索方法，其特征在于，包括使用凝聚层次聚类法对边缘计算网络进行层级划分，将边缘计算网络以层级呈现并建立层间的有向联系，限制搜索层级，使每次路径搜索在规定层级中完成，同时采用分治搜索，将整个搜索过程划分为多个子任务并同时进行，完成最短路径搜索，具体按照以下步骤实施： 步骤1、对网络的节点数据和边关系数据进行数据预处理，节点连接到网络中的物联网设备，边关系为设备间数据流的传输方向，最终构建出完整的边缘计算网络，具有过程是： 步骤1.1、从原始数据中对网络节点数据及边关系数据内容进行解析，清洗冗余数据，统一节点与边关系的数据格式，为后续步骤提供可靠的输入，处理结果存放在CSV文件中； 步骤1.2、使用read_csv函数提取物联网设备名称，并给每个物联网设备建立唯一索引；在提取设备名称时获取到设备间数据流的传输方向信息，由此得到节点间有向边关系； 将提取到的节点索引值和边连接关系导入数据库中，创建复杂网络中的节点和有向边，为节点添加属性信息，包括设备名称、设备类型、设备运行时间信息，最终构建出完整的边缘计算网络； 步骤2、将边缘计算网络转化为度数矩阵形式，使用凝聚层次聚类方法划分网络层级，将层级信息加入到节点属性中，最后合并各层级之间的重复变关系并建立层级索引，具体过程是： 步骤2.1、将步骤1构建的边缘计算网络向量化表示； 步骤2.2、使用凝聚层次聚类方法划分网络层级； 步骤2.3、将层次信息写入节点属性； 步骤2.4、合并各层级之间的重复变关系并建立层级索引； 步骤3、向已经建立层级索引的边缘计算网络输入源节点即起始设备名称和目标节点即目标设备名称，进行节点存在性判断，若输入的源节点或目标节点名称有误或不存在，则提示重新输入或退出，若存在，则根据节点属性中的层级信息数据抽取层级关系，对抽取到的层级关系进行判断，最终返回层级关系类型和层级关系链条，具体过程是： 步骤3.1、节点存在性判断：输入源节点和目标节点，将在步骤1.2建立好的数据库中查询节点的唯一索引，若有任何一个节点的索引不存在，说明输入的节点名称有误或不存在，提示重新输入或退出； 步骤3.2、通过输入的节点名称，提取节点属性中的层级信息，若两节点的层级信息相同即两节点处于同一层中，层级关系链条归类为单层；若两节点间层级关系不处于同层，则使用路径搜索方法BiDFS获取层级关系链条； 步骤4、对层级关系类型和层级关系链条进行判断，若层级关系类型为单层，则使用Dijkstra单源最短路径算法进行单层搜索，直接将搜索结果输出； 若层级关系类型为多层，则限制搜索层级范围，具体范围是层级关系链条中涉及到的层级，对层级关系链条中各相邻层级同时使用SPFA算法进行路径搜索，若路径存在则拼接并输出，若层级关系不存在，则路径不存在，运行结束，具体过程是： 步骤4.1、使用igraph提供的子图提取函数对构建出的边缘计算网络限制搜索层级，具体使用subgraph函数提取完整网络中的子图并通过条件过滤方法筛选节点； 步骤4.2、对步骤3最终获得的层级关系链条类型进行识别，若类型为单层，则使用Dijkstra单源最短路径算法在单层网络中搜索最短路径； 若层级关系链条类型为多层，则使用分治法提取层级关系链条中的所有层级信息，使用步骤4.1中的方法筛选子图，即限制搜索区域为层级关系链条所涉及的层级，使用SPFA算法在各相邻层级中进行最短路径搜索，相邻层级的路径搜索同时进行。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人西安理工大学，其通讯地址为：710048 陕西省西安市碑林区金花南路5号；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。

以上内容由龙图腾AI智能生成。