楊亞偉，王　璐， 王　斐（.山東電力工程咨詢院有限公司，山東濟南5003；.山東省質(zhì)量技術(shù)監(jiān)督教育培訓中心，山東濟南5003）

一種改進的A*算法在電纜敷設(shè)設(shè)計中的應用

楊亞偉1，王璐2， 王斐1
（1.山東電力工程咨詢院有限公司，山東濟南250013；2.山東省質(zhì)量技術(shù)監(jiān)督教育培訓中心，山東濟南250013）

針對常規(guī)A*算法僅以路徑最短作為限制條件而無法約束路徑彎曲次數(shù)的問題，提出一種改進的A*算法，該算法在保證路徑最短的前提下，同時考慮路徑的彎曲次數(shù)問題，最終得到一條彎曲次數(shù)最少的最短路徑。仿真結(jié)果顯示，在電纜敷設(shè)設(shè)計中應用該算法，可以有效降低電纜的總彎曲次數(shù)，從而降低電纜敷設(shè)的施工難度，提高電纜的可靠性。

A*算法；電纜敷設(shè)；電纜彎曲

0　引 言

電纜是發(fā)電廠中一個非常重要的組成部分，它就像整個發(fā)電廠的血管與神經(jīng)系統(tǒng)一樣，遍布廠區(qū)各個角落，其可靠性直接決定了整個發(fā)電廠的可靠性和安全性。造成電纜出現(xiàn)故障的原因有很多，其中電纜的彎曲半徑過小，是一個比較常見的原因［1］。

在電纜敷設(shè)施工時，如果對電纜過度彎曲，導致電纜的彎曲半徑過小，則有可能會對電纜的絕緣性能造成影響，從而在運行過程中引起短路、擊穿等故障［2］。雖然相關(guān)規(guī)程中對電纜的彎曲半徑都有明確的限制，但是由于在施工過程中執(zhí)行不嚴格，檢查不到位，電纜彎曲半徑過小的問題仍然普遍存在［3］。

近年來，隨著機組容量的不斷增加，發(fā)電廠中電纜的數(shù)量也變得越來越多，因此利用計算機輔助電纜敷設(shè)軟件來預先進行電纜敷設(shè)的設(shè)計工作，已經(jīng)成為近年來一種常見的設(shè)計手段［4］。由于發(fā)電廠中電纜橋架及電纜溝的布置較為復雜，某些電纜的起點與終點之間往往存在多條等長的電纜路徑。因此，在進行電纜敷設(shè)的設(shè)計時，在保證電纜路徑最短的前提下，如果能盡可能減少電纜的彎曲次數(shù)，不僅可以減少現(xiàn)場施工的工作量，同時也能夠降低電纜因為彎曲半徑過小而出現(xiàn)故障的概率。

1　等長路徑下電纜的彎曲次數(shù)問題

為了說明等長路徑下電纜的彎曲次數(shù)問題，我們給出一個簡化的電纜敷設(shè)模型如圖1所示。

圖1　電纜敷設(shè)模型

在圖1所示的電纜敷設(shè)模型中，假設(shè)電纜的起點為S，終點為T，通過觀察我們可以發(fā)現(xiàn)，在起點S和終點T之間，共有4種不同的敷設(shè)路徑，并且這4種敷設(shè)路徑是等長的，分別統(tǒng)計這四種敷設(shè)路徑的電纜彎曲次數(shù)，結(jié)果如表1所示。

表1　敷設(shè)結(jié)果

從表1可以發(fā)現(xiàn)，雖然四種敷設(shè)路徑具有相同的敷設(shè)長度，但是其電纜的彎曲次數(shù)卻相差很多。如果僅僅以路徑最短作為電纜敷設(shè)的唯一標準，那么表1中的四種敷設(shè)路徑均可以作為最優(yōu)結(jié)果。但如果從實際施工的角度來考慮，在保證路徑最短的前提下，應盡量選擇電纜彎曲次數(shù)最少的那條敷設(shè)路徑，以便降低現(xiàn)場施工難度，同時也有利于提高電纜的穩(wěn)定性和可靠性。

2　常規(guī)A*算法及其不足之處

計算機輔助電纜敷設(shè)軟件的主要工作是為每一根電纜尋找一條最優(yōu)的敷設(shè)路徑，因此路徑搜索算法便成為計算機輔助電纜敷設(shè)軟件的核心算法。目前較為成熟的路徑搜索算法主要有解析算法和啟發(fā)式算法兩種，分別以Dijastra算法和A*算法為典型代表，其中A*算法由于在計算速度和規(guī)模上具有一定優(yōu)勢［5］，因此在電纜敷設(shè)軟件中得到了廣泛的應用。

2.1 A*算法的基本思想

A*算法是一種典型的啟發(fā)式路徑搜索算法，其核心思想是估價函數(shù)的設(shè)計［6］。在選擇當前節(jié)點的下一個搜索節(jié)點時，引入了估價函數(shù)f（n）

式中：n為待擴展的節(jié)點；f（n）為從起始節(jié)點到節(jié)點n的一條最佳路徑的實際代價加上從節(jié)點n到目標節(jié)點的一條最佳路徑的代價之和；g（n）為從起始節(jié)點到節(jié)點n之間的最短路徑的實際代價；h（n）為從節(jié)點n到目標節(jié)點的路徑估計代價。

A*算法就是在每次選取節(jié)點時，從所有候選節(jié)點中選擇f（n）值最小的那個節(jié)點進行擴展。A*算法的流程圖如圖2所示。

2.2 常規(guī)A*算法的不足之處

常規(guī)A*算法以路徑最短作為衡量結(jié)果優(yōu)劣的唯一標準，當起點與終點間存在多條等長的最短路徑時，常規(guī)A*算法會隨機選取其中一條路徑作為最終結(jié)果，而舍棄其它等長的結(jié)果。在僅考慮路徑長度這一個因素時，這種處理方式?jīng)]有任何問題，但是如果想要在路徑最短的前提下，盡可能降低電纜的彎曲次數(shù)，那么常規(guī)A*算法此時已經(jīng)不能滿足我們的要求。

在對A*算法進行改進之前，首先來分析一下造成上述不足之處的原因。我們以圖1所示的電纜敷設(shè)模型為例，根據(jù)圖2所示的流程圖，得到常規(guī)A*算法的路徑搜索過程如表2所示。

圖2　A*算法流程圖

表2　A*算法搜索過程

將表2的搜索結(jié)果與表1中的數(shù)據(jù)進行對比后發(fā)現(xiàn)，常規(guī)A*算法并沒有得到一條彎曲次數(shù)最少的結(jié)果。與彎曲次數(shù)最少的路徑S-b-c-d-T相比，上述結(jié)果在S-a-c與S-b-c這兩條等長路徑中錯誤地選擇了前者，造成最終彎曲次數(shù)的增加。通過觀察表2中的具體搜索過程發(fā)現(xiàn)，在搜索過程的第2步，算法發(fā)現(xiàn)了由起點S到節(jié)點c的路徑S-a-c，而在搜索過程的第3步，算法發(fā)現(xiàn)了另一條由起點S到節(jié)點c的路徑S-b-c，由圖2所示的算法流程圖得知，當在起點與某個節(jié)點間存在多條可達路徑時，如果后發(fā)現(xiàn)的路徑長度不小于之前發(fā)現(xiàn)的路徑長度，則后發(fā)現(xiàn)的路徑將被舍棄。在上面的搜索過程中，由于從起點S至節(jié)點c之間的路徑S-a-c先被發(fā)現(xiàn)，而后發(fā)現(xiàn)的路徑S-b-c其長度并不比S-a-c小，因此路徑S-a-c被舍棄。

3　改進的A*算法

通過上面的分析過程我們發(fā)現(xiàn)，如果想要得到一條彎曲次數(shù)最少的最短路徑，關(guān)鍵在于當在搜索過程中遇到兩條長度相同的路徑時，并不能簡單地隨機選取其中一條路徑，而是應該對比這兩條路徑的電纜彎曲次數(shù)，選擇彎曲次數(shù)較少的那條路徑。

需要注意的是，當在搜索過程中，遇到兩條長度相同且彎曲次數(shù)也相同的路徑時，我們并不能簡單地認為這兩條路徑是完全等同的而去隨機選取其中一條作為最終結(jié)果，原因如下：

假設(shè)在起點S與終點T之間，存在一點M，在S與M之間存在多條等長路徑，且這些路徑具有相同的彎曲次數(shù)CSM，則起點S與終點T之間經(jīng)過點M的路徑彎曲次數(shù)可以表示為

式中：C為整條路徑的彎曲次數(shù)；CSM為起點S與中間點M之間路徑的彎曲次數(shù)；CM為該路徑在點M處的彎曲次數(shù)（取值為0或1）；CMT為中間點M與終點T之間路徑的最少彎曲次數(shù)。

當中間點M與終點T都確定的情況下，其之間路徑的最少彎曲次數(shù)CMT為常數(shù)。此時，整個路徑的彎曲次數(shù)C的取值由CSM和CM這兩個參數(shù)決定。因此，當CSM相同的情況下，整個路徑的彎曲次數(shù)并不一定相同，這取決于CM的取值。

通過觀察圖1中的電纜敷設(shè)模型我們也很容易理解這個問題，在圖1所示的模型中，在起點S與中間點c之間存在2條等長路徑S-a-c與S-b-c，并且其彎曲次數(shù)都是1，在中間點c與終點T之間，路徑的最少彎曲次數(shù)為1（路徑c-d-T），但是當分別選取路徑S-a-c與S-b-c作為最終結(jié)果時，其總的彎曲次數(shù)并不相同，原因就在于當選取路徑S-a-c時，該路徑在c點的彎曲次數(shù)為1，而選取路徑S-b-c時，該路徑在c點的彎曲次數(shù)為0。

通過上述分析我們知道，當在路徑搜索過程中發(fā)現(xiàn)兩條彎曲次數(shù)相同的等長路徑時，我們并不能馬上在兩條路徑之間做出取舍，而是應該將兩條路徑全部保留，在全部路徑搜索完成后，對兩條路徑的總彎曲次數(shù)進行計算，選擇彎曲次數(shù)較少的那一條路徑作為最終結(jié)果。

下面給出整個改進A*算法的完整流程圖，其中不同于常規(guī)A*算法的部分用虛線表示，如圖3所示。

圖3　改進A*算法的流程圖

4　仿真結(jié)果

為了驗證本文所給出的改進A*算法的實際效果，我們以酒鋼集團鋁電一期工程汽機房零米層中的部分電纜為例，在AutoCAD VBA開發(fā)環(huán)境下，對該算法進行了編程實現(xiàn)，并進行了仿真計算。酒鋼集團鋁電一期工程汽機房零米層的部分橋架模型如圖4所示。

我們在該工程中隨機選取了243根儀表控制電纜，分別利用常規(guī)A*算法和改進A*算法對這些電纜的敷設(shè)路徑進行了仿真計算，通過觀察仿真結(jié)果發(fā)現(xiàn)，對于某些電纜，在運用常規(guī)A*算法和改進A*算法進行路徑搜索時，得到的敷設(shè)結(jié)果并不相同，結(jié)果如圖5所示。

圖4　酒鋼鋁電一期工程汽機房零米層部分橋架簡化模型

圖5　傳統(tǒng)A*算法與改進A*算法仿真結(jié)果對比

通過圖5中兩種算法仿真結(jié)果的對比可以發(fā)現(xiàn)，對于同一根電纜，在保證路徑最優(yōu)的前提下，改進A*算法所得結(jié)果與傳統(tǒng)A*算法相比，電纜的彎曲次數(shù)減少了2次。對全部243根電纜的仿真結(jié)果進行統(tǒng)計匯總，其結(jié)果如表3所示。從表3可以看出，改進A*算法在保持電纜敷設(shè)總長度不變的前提下，其電纜的彎曲總次數(shù)相比于常規(guī)A*算法減少了約6%。

表3　仿真結(jié)果

5　實際應用過程中需要注意的問題

在實際應用本文所給出的考慮電纜彎曲次數(shù)的改進A*算法時，需要注意幾個問題。

（1）路徑長度的精度問題

在實際的電纜敷設(shè)設(shè)計時，電纜路徑的長度往往都是由一定精度的小數(shù)來表示的。在實際操作過程中，由于電纜路徑繪制不精確，或者開發(fā)環(huán)境中小數(shù)的精度過高等原因，往往會造成相同長度的兩條電纜路徑，其精確長度會有細微的差別。如果不進行額外的設(shè)置，算法會優(yōu)先選擇精確長度略短的那條路徑，而這種路徑長度上的細微差別在實際中是毫無意義的。因此，在進行電纜路徑長度的比較時，不宜將精度設(shè)置得過高。

（2）纜流限制問題

利用改進A*算法進行電纜敷設(shè)的設(shè)計時，在某些情況下可能會造成部分電纜過分集中于某一條路徑的情況，使得電纜路徑的利用率不均衡。在這種情況下，可以通過對上述路徑設(shè)置一個合理的纜流量限制值，來避免這種情況的發(fā)生。

6　結(jié)束語

本文所給的考慮電纜彎曲次數(shù)的改進A*算法，能夠在保證路徑最短的前提下，得到一條彎曲次數(shù)最少的電纜敷設(shè)路徑。仿真結(jié)果顯示，該算法能有效降低實際工程中電纜的總彎曲次數(shù)，這對降低電纜敷設(shè)施工的工作量和工作難度、提高電纜的可靠性都有著十分重要的意義。

［1］ 薛福連.35 kV及以下電力電纜故障的原因及對策［J］.電線電纜，2003（6）：38-40.

［2］ 吳明祥，毛琳明.一起220 kV電纜終端擊穿故障原因分析［J］.浙江電力，2012（9）：10-20.

［3］ 劉永興.一起所用變低壓電纜起火燃燒事故原因分析及預防措施［J］.電氣應用，2009，28（13）：44-46.

［4］ 安慶敏，徐愛東，陳志強，等.火力發(fā)電廠熱控電纜敷設(shè)軟件的開發(fā)與應用［J］.工業(yè)儀表與自動化裝置，2011（6）：64-66.

［5］ 王永慶.人工智能原理與方法［M］.西安：西安交通大學出版社，2003.

［6］ Ni1sson N J.PrinciP1es of artificia1 inte11igence［M］.Pa1o A1to：Tioga Pub1ishing ComPany，1980：72-88.

APPlication of an Im Proved A*Algorithm in Cab le Laing Design

YANG Ya-wei1，WANG Lu2，WANG Fei1
（1.Shandong E1ectric Power Engineering Consu1ting Institute Co.，1td.，Jinan 250013，China；2.Shandong Education Training Center of Qua1ity and Technica1SuPervision，Jinan 250013，China）

In order to avoid the Prob1em that the resu1t of conventiona1 A*a1gorithm is on1y oPtim ization in Path 1ength and the Path curve quantity is not considered，an imProved A*a1gorithm is ProPosed in this PaPer，the resu1t of this a1gorithm is oPtimization in Path curve quantity on the Premise that the Path 1ength is shortest.The exPerimenta1data indicate that the curve quantity of cab1es is reduced after this a1gorithm is used in the cab1e 1aying design，which can reduce the difficu1t of cab1e 1aying construction and imProve the re1iabi1ity of the cab1es.

A*a1gorithm；cab1e 1aying；cab1e curve

TM202

A

1672-6901（2016）03-0032-04

2015-07-09

楊亞偉（1985-），男，碩士，工程師.

作者地址：山東濟南市華龍路1665號電力咨詢大廈1010室［250100］.