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

董福鑫

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

1概述

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

2改進(jìn)BFS算法

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

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

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

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

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

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

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

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

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

3Python編程仿真

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

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

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

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

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

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

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

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

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

4總結(jié)

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