一种有向赋权图最长链路的快速识别方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN109726856A(43)申请公布日2019.05.07(21)申请号201811548369.0(22)申请日2018.12.18(71)申请人太原理工大学地址030024山西省太原市迎泽西大街79号(72)发明人邢玉忠武旭东曹学军颜勍陈孟长郭长恒(74)专利代理机构太原晋科知识产权代理事务所(特殊普通合伙)14110代理人任林芳(51)Int.Cl.G06Q10/04(2012.01)G06Q50/06(2012.01)权利要求书1页说明书3页附图2页(54)发明名称一种有向赋权图最长链路的快速识别方法(57)摘要本发明涉及一种有向赋权图最长链路的快速识别方法，包括：根据识别目标构建有向赋权图，赋予有向赋权图的末节点第一标号，赋予末节点的上游节点第二标号；考察各标记第二标号的上游节点，若已标记第二标号的上游节点的数量等于从标记第二标号的上游节点出发的分支数，则将标记第二标号的上游节点的标号变换为第一标号，且第一标号的标号值为该上游节点已获各第二标号值中最大者；到始节点获得第一标号为止；使用逆向追踪法，由始节点开始，沿其下游之已标记第一标号值最大的节点前进，到达末节点，所经路线即为有向赋权图自始节点至末节点的最长路，始节点的第一标号值为最长路的权值。通过本发明，能够快速寻找有向赋权网络图中的最长链路。CN109726856ACN109726856A权利要求书1/1页1.一种有向赋权图最长链路的快速识别方法，其特征在于，包括：根据识别目标构建有向赋权图，赋予有向赋权图的末节点第一标号，赋予末节点的上游节点第二标号；其中，第二标号的标号值等于第一标号的标号值与末节点的上游节点对应分支权重之和；考察各标记第二标号的节点，若节点已标记第二标号的数量等于从该节点出发的分支数，则将标记第二标号的上游节点的标号变换为第一标号，且第一标号的标号值为该上游节点已获各第二标号值中最大者；重复上述步骤，直到始节点获得第一标号为止；使用逆向追踪法，由始节点开始，沿其下游的被标记的第一标号值最大的节点前进，到达末节点，所经路线即为有向赋权图自始节点至末节点的最长路，始节点的第一标号值为最长路的权值。2.根据权利要求1所述的有向赋权图最长链路的快速识别方法，其特征在于，所述识别目标为矿井通风最大阻力路、电网最大耗能线路、项目最耗时工序链中的一种。2CN109726856A说明书1/3页一种有向赋权图最长链路的快速识别方法技术领域[0001]本发明涉及图论范畴领域，具体涉及一种有向赋权图最长链路的快速识别方法。背景技术[0002]有向赋权图的应用极为广泛，而其中，寻找有向赋权图的最长路，在涉及有向网络的各个领域的应用尤为重要。在矿井通风领域，常用确定风网最大阻力路的方法，确定其它风路的增阻调节量，以达到按需供风的目的；在电网改造中，也需确定电网最大能耗路，以便找到电网改造的目标；在各类项目的工序衔接网络中，项目的完成工期是由最耗时工序链决定的，因此只有找到该工序链，并保证该工序链的完成日期，才能保障项目的按期完工；同时也为项目提前完工找到了突破口。[0003]现有工程有向赋权网络最长路的求解，主要有以下方法：1）循环深度优先遍历法；2）递归计算法；3）印刷电路板内阻检测法等。其计算过程复杂、计算量大、工作效率低，有些方法没有通用性。一种快速识别有向赋权网络最长路的算法可以避免上述传统计算方式的缺点，提高工作效率，具有重要的应用价值与广泛的应用前景。发明内容[0004]本发明的目的在于避免现有技术的不足之处而提供一种有向赋权图最长链路的快速识别方法。[0005]本发明的目的可以通过采用如下的技术措施来实现，设计一种有向赋权图最长链路的快速识别方法，包括：根据识别目标构建有向赋权图，赋予有向赋权图的末节点第一标号，赋予末节点的上游节点第二标号；其中，第二标号的标号值等于第一标号的标号值与末节点的上游节点对应分支权重之和；考察各标记第二标号的上游节点，若已标记第二标号的上游节点的数量等于从标记第二标号的上游节点出发的分支数，则将标记第二标号的上游节点的标号变换为第一标号，且第一标号的标号值为该上游节点已获各第二标号值中最大者；重复上述步骤，直到始节点获得第一标号为止；使用逆向追踪法，由始节点开始，沿其下游被标记第一标号值最大的节点前进，到达末节点，所经路线即为有向赋权图自始节点至末节点的最长路，始节点的第一标号值为最长路的权值。[0006]其中，识别目标为矿井通风最大阻力路、电网最大耗能线路、项目最耗时工序链中的一种。[0007]区别于现有技术，本发明的有向赋权图最长链路的快速识别方法，包括：根据识别目标构建有向赋权图，赋予有向赋权图的末节点第一标号，赋予末节点的上游节点第二标号；