改進BFS算法在打包機電纜路徑計算中的設(shè)計與實現(xiàn)

董福鑫

關(guān)鍵詞：電纜最短路徑;改進BFS算法;Python

1概述

針對冶金生產(chǎn)電氣生產(chǎn)設(shè)計流程，電纜路徑設(shè)計的核心工作是保證滿足各相規(guī)范要求下使每根電纜的路徑長路最短，尤其是電纜價格昂貴，電纜敷設(shè)路徑是否優(yōu)化，直接對工程成本造成很大影響[1]。目前，各冷軋廠較為常用的電纜路徑設(shè)計方法是在打包機三維設(shè)計軟件Tribon或其他CAD軟件中根據(jù)設(shè)備定位，以起始設(shè)備為電纜的起始點，以終端設(shè)備為電纜的終點，再將電纜路徑的轉(zhuǎn)折點、分叉點、通艙件等位置設(shè)置為途徑節(jié)點或虛擬節(jié)點，之后設(shè)計人員手動按照電纜路徑走向依次拾取各節(jié)點，直到路徑終了，將其存儲在數(shù)據(jù)庫中。由于必須手動依次拾取節(jié)點，任何一個節(jié)點的錯漏都將影響結(jié)果。電纜長度越長，節(jié)點越多越容易選錯節(jié)點且隱秘不易被發(fā)現(xiàn)，若在敷設(shè)過程才發(fā)現(xiàn)已裁切的電纜長度不夠，返工重新訂貨、運輸、裁切、敷設(shè)將嚴(yán)重拖延施工工期。若整個路徑有任何節(jié)點錯漏，都需手動重頭依次修改，這對于大型打包機或特種工程打包機動則十?dāng)?shù)萬的電纜量而言，勢必耗費大量的人力和時間，影響出圖效率，進而壓縮后續(xù)施工工期，影響施工質(zhì)量[2]。

2改進BFS算法

經(jīng)典的最短路徑算法有Dijkstm算法、Floyd算法、A—Star算法、BFS算法、Bellm an—Ford算法[3～5]。

Diikstm算法的思想是從路徑的起始點，逐步向外層層擴展，直到找到終點為止。其缺點是遍歷計算的節(jié)點多、效率低，適合單源最短路徑在非負權(quán)圖中的問題。

Floyd算法可以一次計算出圖中任意兩頂點間的最短路徑，在稠密圖情形下，其效率要好于Dijkstm算法。但在本項目中，電纜通道的每個頂點只與鄰近頂點相連通，即圖是稀疏的。

A.Star算法與Diikstm算法類似，其引入了評價函數(shù)去評估下一步的最佳選擇，使得搜索具有趨近終點的方向性。其缺點是通過評價函數(shù)獲取的最佳路徑并不能保證是理論上的最佳。

BFS（breadth—first一search）算法是以寬度優(yōu)先進行的遍歷算法，即每一步先遍歷頂點的所有相鄰節(jié)點，然后再往相鄰節(jié)點的各相鄰節(jié)點進行延伸，直到找到結(jié)果為止。它先找到終點的路徑一定是遍歷層數(shù)最淺的，但距離卻不一定是最短的（各邊權(quán)值可能相差很大）。

Bellm an-Ford算法相較于Dijkstra算法更適合求解負權(quán)最短路問題，缺點是效率低，時間復(fù)雜度相對較大。

考慮到實際工程設(shè)計中，電纜路徑是根據(jù)電氣設(shè)備按需設(shè)計的，由設(shè)備位置決定電纜路徑的起始點和終點，并不需要找出所有節(jié)點尤其是中間節(jié)點間的最短路徑：隨著打包機生產(chǎn)運行的展開，根據(jù)現(xiàn)場實際和生產(chǎn)要求，可能經(jīng)常增刪節(jié)點和更改路徑。綜合考慮之下，本文選取BFS算法并加以改進，即在第一次找到完整路徑（從起點到終點的路徑）結(jié)果后，暫時保留其路徑和權(quán)值，繼續(xù)以未完路徑（以起點開始，中間節(jié)點為結(jié)尾的路徑）為基礎(chǔ)繼續(xù)尋徑，直到尋至該起點的最深層的所有鄰接點。

點A到點G的尋徑中：A—C—C是遍歷最淺的路徑，權(quán)值為10+3=13;A—C—F—I—G是遍歷較深的路徑，權(quán)值為3+3+2+4=12。

改進BFS算法：即整個尋徑過程中每一完整路徑皆被保存并比較，及時刪除較長路徑，只保留最小權(quán)值的完整路徑，上例中則自動保存A—C—F—I—C路徑，也是實際上最小權(quán)值的路徑：可以添加必過節(jié)點和避開節(jié)點，減少程序的遍歷深度和廣度，降低程序執(zhí)行的時間復(fù)雜度和空間復(fù)雜度，上例如添加必過節(jié)點H，避開節(jié)點C，則符合要求的最短路徑即A—B-E-H-I-G。

3Python編程仿真

基于打包機生產(chǎn)設(shè)計軟件Tribon和改進BFS最短路徑算法，利用Python 3.8. 10編程仿真，設(shè)計并計算電纜的最短路徑及其長度。其優(yōu)點是無須手動依次拾取節(jié)點，只須設(shè)計人員根據(jù)具體打包機結(jié)構(gòu)、設(shè)計要求和工作經(jīng)驗，設(shè)置電纜路徑的起始點和終點，并根據(jù)需要靈活添加電纜路徑的必過節(jié)點和避開節(jié)點，程序自動算出符合要求的最短路徑。由于可以設(shè)置必過節(jié)點和避開節(jié)點[6]，對于特殊電纜的走向，如相關(guān)規(guī)范要求：至應(yīng)急消防泵的電纜，不應(yīng)穿過裝有主消防泵及其動力源和/或原動機的機器處所：與冷藏處所無關(guān)的電纜，不應(yīng)穿過冷藏處所敷設(shè)：當(dāng)電纜在金屬管子、管道、電纜槽內(nèi)敷設(shè)時穿管系數(shù)應(yīng)不大于0.4;對要求兩路供電的重要設(shè)備，應(yīng)盡最大可能在水平及垂直方向遠離敷設(shè)，設(shè)計人員可以根據(jù)相關(guān)規(guī)范要求和實際情況靈活分流，如此既可減少程序的無序遍歷，降低原有BFS算法的時間復(fù)雜度和空間復(fù)雜度，又提高了電纜路徑設(shè)計的靈活度。此外，考慮到實際工程中可能出現(xiàn)同一始點可有多個長度相同的路徑到達終點的情況，本算法在最短路徑的計算和選擇中不保留其唯一性，而是將相同長度的所有最短路徑羅列出來，以便設(shè)計人員根據(jù)設(shè)計要求、施工難度、是否可與其他類電纜同橋架敷設(shè)、所經(jīng)電纜筒剩余空間大小等其他影響權(quán)值但難以量化的因素選擇最優(yōu)解，使電纜路徑的設(shè)計更加方便靈活高效，減少錯漏的發(fā)生。

Python編程的過程：先用tribon提取目前生產(chǎn)運行中使用的西門子打包機的電子樣電纜節(jié)點名稱及其三維數(shù)據(jù)，按其數(shù)據(jù)結(jié)構(gòu)仿真設(shè)計一電纜路徑集合存儲在Python字典中。利用python將其計算并轉(zhuǎn)換為包括所有電纜節(jié)點的二維正權(quán)圖，如圖1所示。以起點為源頭，遍歷與其鄰接的節(jié)點，并判斷其鄰接節(jié)點是否有終點、避開點[7]。當(dāng)鄰接點為終點時，將該路徑存人完整路徑庫：當(dāng)鄰接點為避開點時，刪除該路徑;當(dāng)鄰接點為已遍歷節(jié)點（即回頭路，或鄰接點為只有一個節(jié)點與其相連的端點）時，刪除該路徑;當(dāng)臨接點既不是終點，也不是避開點時，存儲該路徑至未完路徑庫。同時，在下層尋徑開始前判斷是否有多余兩條的完整路徑存在，若存在，刪除權(quán)值較高的完整路徑，并以完整路徑庫內(nèi)的當(dāng)前最小權(quán)值完整路徑為判斷依據(jù)，刪除未完路徑庫內(nèi)權(quán)值不小于該最小權(quán)值的未完路徑，只保留可能存在權(quán)值更小的最小路徑。以降低程序的時間復(fù)雜度和空間復(fù)雜度。至此，該層尋徑結(jié)束。

在下層尋徑時，遍歷未完路徑庫內(nèi)未完路徑末尾點的鄰接點，重復(fù)上層判斷規(guī)則，更新完整路徑庫和未完路徑庫，直至將未完路徑庫清空，并保留若干相同權(quán)值的不同完整路徑于完整路徑庫，即為最終尋徑結(jié)果。其程序流程如圖2所示。

若有必過點，則相當(dāng)于將完整路徑分拆成起點——必過點和必過點——終點兩個最短路徑的問題，即程序執(zhí)行兩次，更有利于降低單次程序的遍歷深度。

以“ab003”為起點，“ac004”為終點尋徑為例，程序執(zhí)行結(jié)果如圖3所示，存在長度相同的四個不同路徑。

若單獨添加避開點“ac007”再次尋徑，程序執(zhí)行結(jié)果如圖4所示，圖4中含有避開點的兩個路徑已被刪除。

若添加避開點“ac007”，再添加必過點“ac005”，程序執(zhí)行結(jié)果如圖5所示，只有圖4中第二個路徑被保留。

若單獨添加必過點“ac005”，程序執(zhí)行結(jié)果如圖6所示。

如圖5和圖6所示，添加必過節(jié)點的尋徑，程序可自動將尋徑結(jié)果分為兩段，當(dāng)某段有多個尋徑結(jié)果時，設(shè)計人員可以根據(jù)實際情況進行選擇。根據(jù)程序執(zhí)行結(jié)果，該改進算法簡便有效，完全可以用于基于Tribon軟件的打包機電纜路徑的設(shè)計和計算，亦可對接其他可提取電纜節(jié)點三維參數(shù)的設(shè)計軟件，使電纜路徑的設(shè)計更加靈活、高效。

4總結(jié)

本文詳細地介紹了改進BFS最短路徑算法的核心思想，結(jié)合Windows 7系統(tǒng)平臺、Tribon軟件、Python編程技術(shù)等相關(guān)技術(shù)與標(biāo)準(zhǔn)，設(shè)計開發(fā)了打包機電纜最短路徑自動計算程序，并通過流程圖展示Python程序的處理過程。程序能與可提取電纜節(jié)點參數(shù)的三維設(shè)計軟件（如Tribon）對接，實現(xiàn)可添加避開點和必過點的最短路徑設(shè)計和長度計算，幫助設(shè)計人員在生產(chǎn)設(shè)計中合理且快速地選擇電纜路徑。