改进BFS算法在打包机电缆路径计算中的设计与实现

董福鑫

关键词：电缆最短路径;改进BFS算法;Python

1概述

针对冶金生产电气生产设计流程，电缆路径设计的核心工作是保证满足各相规范要求下使每根电缆的路径长路最短，尤其是电缆价格昂贵，电缆敷设路径是否优化，直接对工程成本造成很大影响[1]。目前，各冷轧厂较为常用的电缆路径设计方法是在打包機三维设计软件Tribon或其他CAD软件中根据设备定位，以起始设备为电缆的起始点，以终端设备为电缆的终点，再将电缆路径的转折点、分叉点、通舱件等位置设置为途径节点或虚拟节点，之后设计人员手动按照电缆路径走向依次拾取各节点，直到路径终了，将其存储在数据库中。由于必须手动依次拾取节点，任何一个节点的错漏都将影响结果。电缆长度越长，节点越多越容易选错节点且隐秘不易被发现，若在敷设过程才发现已裁切的电缆长度不够，返工重新订货、运输、裁切、敷设将严重拖延施工工期。若整个路径有任何节点错漏，都需手动重头依次修改，这对于大型打包机或特种工程打包机动则十数万的电缆量而言，势必耗费大量的人力和时间，影响出图效率，进而压缩后续施工工期，影响施工质量[2]。

2改进BFS算法

经典的最短路径算法有Dijkstm算法、Floyd算法、A—Star算法、BFS算法、Bellm an—Ford算法[3～5]。

Diikstm算法的思想是从路径的起始点，逐步向外层层扩展，直到找到终点为止。其缺点是遍历计算的节点多、效率低，适合单源最短路径在非负权图中的问题。

Floyd算法可以一次计算出图中任意两顶点间的最短路径，在稠密图情形下，其效率要好于Dijkstm算法。但在本项目中，电缆通道的每个顶点只与邻近顶点相连通，即图是稀疏的。

A.Star算法与Diikstm算法类似，其引入了评价函数去评估下一步的最佳选择，使得搜索具有趋近终点的方向性。其缺点是通过评价函数获取的最佳路径并不能保证是理论上的最佳。

BFS（breadth—first一search）算法是以宽度优先进行的遍历算法，即每一步先遍历顶点的所有相邻节点，然后再往相邻节点的各相邻节点进行延伸，直到找到结果为止。它先找到终点的路径一定是遍历层数最浅的，但距离却不一定是最短的（各边权值可能相差很大）。

Bellm an-Ford算法相较于Dijkstra算法更适合求解负权最短路问题，缺点是效率低，时间复杂度相对较大。

考虑到实际工程设计中，电缆路径是根据电气设备按需设计的，由设备位置决定电缆路径的起始点和终点，并不需要找出所有节点尤其是中间节点间的最短路径：随着打包机生产运行的展开，根据现场实际和生产要求，可能经常增删节点和更改路径。综合考虑之下，本文选取BFS算法并加以改进，即在第一次找到完整路径（从起点到终点的路径）结果后，暂时保留其路径和权值，继续以未完路径（以起点开始，中间节点为结尾的路径）为基础继续寻径，直到寻至该起点的最深层的所有邻接点。

点A到点G的寻径中：A—C—C是遍历最浅的路径，权值为10+3=13;A—C—F—I—G是遍历较深的路径，权值为3+3+2+4=12。

改进BFS算法：即整个寻径过程中每一完整路径皆被保存并比较，及时删除较长路径，只保留最小权值的完整路径，上例中则自动保存A—C—F—I—C路径，也是实际上最小权值的路径：可以添加必过节点和避开节点，减少程序的遍历深度和广度，降低程序执行的时间复杂度和空间复杂度，上例如添加必过节点H，避开节点C，则符合要求的最短路径即A—B-E-H-I-G。

3Python编程仿真

基于打包机生产设计软件Tribon和改进BFS最短路径算法，利用Python 3.8. 10编程仿真，设计并计算电缆的最短路径及其长度。其优点是无须手动依次拾取节点，只须设计人员根据具体打包机结构、设计要求和工作经验，设置电缆路径的起始点和终点，并根据需要灵活添加电缆路径的必过节点和避开节点，程序自动算出符合要求的最短路径。由于可以设置必过节点和避开节点[6]，对于特殊电缆的走向，如相关规范要求：至应急消防泵的电缆，不应穿过装有主消防泵及其动力源和/或原动机的机器处所：与冷藏处所无关的电缆，不应穿过冷藏处所敷设：当电缆在金属管子、管道、电缆槽内敷设时穿管系数应不大于0.4;对要求两路供电的重要设备，应尽最大可能在水平及垂直方向远离敷设，设计人员可以根据相关规范要求和实际情况灵活分流，如此既可减少程序的无序遍历，降低原有BFS算法的时间复杂度和空间复杂度，又提高了电缆路径设计的灵活度。此外，考虑到实际工程中可能出现同一始点可有多个长度相同的路径到达终点的情况，本算法在最短路径的计算和选择中不保留其唯一性，而是将相同长度的所有最短路径罗列出来，以便设计人员根据设计要求、施工难度、是否可与其他类电缆同桥架敷设、所经电缆筒剩余空间大小等其他影响权值但难以量化的因素选择最优解，使电缆路径的设计更加方便灵活高效，减少错漏的发生。

Python编程的过程：先用tribon提取目前生产运行中使用的西门子打包机的电子样电缆节点名称及其三维数据，按其数据结构仿真设计一电缆路径集合存储在Python字典中。利用python将其计算并转换为包括所有电缆节点的二维正权图，如图1所示。以起点为源头，遍历与其邻接的节点，并判断其邻接节点是否有终点、避开点[7]。当邻接点为终点时，将该路径存人完整路径库：当邻接点为避开点时，删除该路径;当邻接点为已遍历节点（即回头路，或邻接点为只有一个节点与其相连的端点）时，删除该路径;当临接点既不是终点，也不是避开点时，存储该路径至未完路径库。同时，在下层寻径开始前判断是否有多余两条的完整路径存在，若存在，删除权值较高的完整路径，并以完整路径库内的当前最小权值完整路径为判断依据，删除未完路径库内权值不小于该最小权值的未完路径，只保留可能存在权值更小的最小路径。以降低程序的时间复杂度和空间复杂度。至此，该层寻径结束。

在下层寻径时，遍历未完路径库内未完路径末尾点的邻接点，重复上层判断规则，更新完整路径库和未完路径库，直至将未完路径库清空，并保留若干相同权值的不同完整路径于完整路径库，即为最终寻径结果。其程序流程如图2所示。

若有必过点，则相当于将完整路径分拆成起点——必过点和必过点——终点两个最短路径的问题，即程序执行两次，更有利于降低单次程序的遍历深度。

以“ab003”为起点，“ac004”为终点寻径为例，程序执行结果如图3所示，存在长度相同的四个不同路径。

若单独添加避开点“ac007”再次寻径，程序执行结果如图4所示，图4中含有避开点的两个路径已被删除。

若添加避开点“ac007”，再添加必过点“ac005”，程序执行结果如图5所示，只有图4中第二个路径被保留。

若单独添加必过点“ac005”，程序执行结果如图6所示。

如图5和图6所示，添加必过节点的寻径，程序可自动将寻径结果分为两段，当某段有多个寻径结果时，设计人员可以根据实际情况进行选择。根据程序执行结果，该改进算法简便有效，完全可以用于基于Tribon软件的打包机电缆路径的设计和计算，亦可对接其他可提取电缆节点三维参数的设计软件，使电缆路径的设计更加灵活、高效。

4总结

本文详细地介绍了改进BFS最短路径算法的核心思想，结合Windows 7系统平台、Tribon软件、Python编程技术等相关技术与标准，设计开发了打包机电缆最短路径自动计算程序，并通过流程图展示Python程序的处理过程。程序能与可提取电缆节点参数的三维设计软件（如Tribon）对接，实现可添加避开点和必过点的最短路径设计和长度计算，帮助设计人员在生产设计中合理且快速地选择电缆路径。