(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202110389163.3 (22)申请日 2021.04.12 (65)同一申请的已公布的文献号 申请公布号 CN 113268837 A (43)申请公布日 2021.08.17 (73)专利权人 中国电建集团华 东勘测设计 研究 院有限公司 地址 310014 浙江省杭州市潮王路2 2号 (72)发明人 徐展鹏　王运罡　陈福新　 (74)专利代理 机构 浙江杭州金通专利事务所有 限公司 3 3100 专利代理师 刘晓春 (51)Int.Cl. G06F 30/18(2020.01) G06F 30/27(2020.01) G06K 9/62(2022.01) G06Q 10/04(2012.01) G06Q 50/06(2012.01) G06F 113/04(2020.01)(56)对比文件 CN 103427371 A,2013.12.04 CN 105279574 A,2016.01.27 US 2009217248 A1,20 09.08.27 US 20210 58314 A1,2021.02.25 CN 110197305 A,2019.09.0 3 CN 112085280 A,2020.12.15 CN 109583 667 A,2019.04.0 5 CN 112330054 A,2021.02.0 5 US 2020252327 A1,2020.08.0 6 US 202102 9038 A1,2021.01.28 王运罡 等.天荒坪抽水蓄能电站控制系统 设计特点及技 术发展. 《水电与抽水蓄能》 .2019, 钱嘉楠等.基 于Intergraph Smart 3D的邮 轮电缆自动敷设功能优化 开发. 《船舶工程》 .2020,(第01期), 徐展鹏等.基 于神经网络算法的工缝机节能 电动机控制系统的设计. 《纺织学报》 .201 1,(第 12期), 审查员 王利双 (54)发明名称 一种采用C4.5决策树算法的电缆路径寻优 方法 (57)摘要 本发明提供了一种采用C4.5决策树算法的 电缆路径寻优方法， 包括以下步骤： S1： 将实际的 桥架布置图进行有向网络建模； S2： 采用最短路 径算法， 对任意两点间的最短路径和最短路径的 长度进行计算， 路径的表现形式为具有一个起点 和一个终点， 起点和终点之间具有多个顶点， 根 据这个路径， 起点到终点的边的长度和最短， 即 电缆敷设的长度最短； 本发明可将诸多实际因素 引入， 使算法更适合实际的运用场景， 提高单次 敷设成功率和自动化程度， 减少后期人工调整的 工作量。 权利要求书2页 说明书9页 附图6页 CN 113268837 B 2022.06.14 CN 113268837 B 1.一种采用C4.5决策树 算法的电缆路径寻优方法， 其特 征在于： 包括以下步骤： S1： 将实际的桥架 布置图进行有向网络建模； S2： 采用最短路径算法， 对任意两点间的最短路径和最短路径的长度进行计算， 路径的 表现形式为具有一个起点和一个终点， 起点和终点之间具有多个顶 点， 根据这个路径， 起点 到终点的边的长度和最短， 即电缆 敷设的长度最短； S3： 利用决策树理论， 采用C4.5决策树算法， 对S2中得到的最短路径， 引入影响路径选 择的多个因素， 对最短路径进行进一 步处理， 得到最优路径； 所述决策树 算法对最短路径进行进一 步处理的具体步骤如下： S3‑1： 选择决定电缆走向的多个因素， 并将这些需要考虑的因素编号为因素A， 因素B， 因素C， 因素D. ..， 因素N； S3‑2： 针对需考虑的n个因素的每种可 能情况建立不同的样本组合， 样本个数为X， 并在 建立的样本组合下， 对每一个当前所在顶点， 决定是否按步骤S2中确定的最短路径作为接 下来的电缆路径， 以符号M表示该选择， 作为目标变量， 其取值 为“是”和“否”； S3‑3： 在样本组合中， 设目标变量M的结果， 选 “是”的有X1组， 选“否”的有X2组， 则样本总 数为X＝X1+X2组， 则计算M的经验熵为： H(M)＝‑P1*log(P1)‑P2*log(P2) 其中： P1＝X1/X， P2＝X2/X S3‑4： 在样本组合中， 设因素A有j种不同的具体情况， 编号为A1， A2， A3， ...， Aj， 各情况出 现的个数为Y1， Y2， Y3， ...， Yj， Y1+Y2+Y3+...+Yj＝X； 假设在第j个情况 中， 步骤S3 ‑2中的目标 变量M选“是”的为Yj1组， 选“否”的为Yj2组， Yj1+Yj2＝Yj， 则计算M在因素A下的经验条件熵为： H(M/A)＝Y1/X*H(A1)+Y2/X*H(A2)+Y3/X*H(A3)+....+Yj/X*H(Aj) 上式中， 第j个情况中H(Aj)计算如下： H(Aj)＝‑Pj1*log(Pj1)‑Pj2*log(Pj2) 其中： Pj1＝Yj1/Yj， Pj2＝Yj2/Yj S3‑5： 将步骤S3 ‑3和S3‑4中得到的H(M)和H(M /A)， 计算因素A的信息增益g(M， A)： g(M， A)＝H(M) ‑H(M/A) 利用步骤S3 ‑3和S3‑4中的参数： Y1， Y2， Y3...Yj可得因素A的经验熵为： H(A)＝‑Y1/X*log(Y1/X)‑Y2/X*log(Y2/X)......‑Yj/X*log(Yj/X) S3‑6： 利用步骤S3 ‑5中的结果， 计算采用决策树C4.5算法下的因素A的信息增益 率为： gr(M， 因素A)＝g(M， A)/ H(A) 同理， 重复步骤S3 ‑3至S3‑6， 可得gr(M， 因素B)， gr(M， 因素C)， gr(M， 因素D)....gr(M， 因素N)； S3‑7： 比较gr(M， 因素A)、 gr(M， 因素B)、 gr(M， 因素C)、 gr(M， 因素D)....gr(M， 因素N)之 间的大小， 最大 的因素作为决策树根节点， 次小的作为下一个分枝节点， 依 次排序， 最小的 作为最末的分枝节点。 2.根据权利要求1所述的一种采用C4.5决策树算法的电缆路径寻优方法， 其特征在于： 所述有向网络 建模， 将桥架的三通及三通以上的连接端作为一个顶 点， 并按顺序编号， 作为 网络的顶点； 两点之间若有实际桥架连接， 则认为两点之间有边， 边的属性有两个： 权重和 方向； 边只指定了单个方向的， 电缆走向只能按指定方向； 边同时指定了正反向和反方向权　利　要　求　书 1/2 页 2 CN 113268837 B 2的， 则认为 边是无向的， 即电缆走向是双向的。 3.根据权利要求1所述的一种采用C4.5决策树算法的电缆路径寻优方法， 其特征在于： 所述最短路径算法的具体步骤如下： S2‑1： 将步骤S1中建立的有向网络进行命名， 为第一名称， 然后将该名称中所有的边的 方向取反， 并进行命名， 为第二名称； 设a、 b为网络中某相邻两点， 在第一名称网络中， 如果 ab边的方向为a →b， Lab为ab两点间的实际长度， 如果ab边的方向为b →a,则Lab为正无穷大； S2‑2： 根据每个顶点的编号i， 可以建立集合D(V1， V2， V3， .....， Vi)； 其中各元素初始值 为正无穷大； 以及集合P(U1， U2， U3， ......， Ui)， 其初始为 空集合， 若某一根电缆起点编号为 Start， 终点编号为End， 从终点往起点回溯， 此时将 集合D(V1， V2， V3， .....， Vi)中Vend值由正 无穷改为0； S2‑3： 找出集合D(V1， V2， V3， .....， Vi)中的最小值元素， 设为第n个元素， 其值为Vn， 将此 值记下， 然后在集合中删除该元素，  在第一次寻找中， 这个元素编号即为S2 ‑2中设定的 End； S2‑4： 遍历第二名称网络中所有以n为端 点的边， 并设m为边的另一端 点； 对于集合D(V1， V2， V3， .....， Vi)中的所有Vm， 若Vk+Lnm<Vm， 则令Vm＝Vk+Lnm； 因为n即为最短路径的途径点， 存 入集合P(U1， U2， U3， ......， Ui)中， 记录途径点； S2‑5： 重复步骤S2 ‑3和S2‑4， 直到到达起点， 最后可以得到第一名称网络中Start和End 两点间的最短长度和最短路径经 过的所有中间点。 4.根据权利要求1所述的一种采用C4.5决策树算法的电缆路径寻优方法， 其特征在于： 所述S3‑1中影响因素包括： 本路径中目前的电缆容积率、 路径中的弯头数量， 转弯半径以及 垂直路径中是电缆梯架或电缆竖井。权　利　要　求　书 2/2 页 3 CN 113268837 B 3