一種改進(jìn)的A*算法在電纜敷設(shè)設(shè)計(jì)中的應(yīng)用

楊亞偉，王　璐， 王　斐（.山東電力工程咨詢?cè)河邢薰?，山東濟(jì)南5003；.山東省質(zhì)量技術(shù)監(jiān)督教育培訓(xùn)中心，山東濟(jì)南5003）

一種改進(jìn)的A*算法在電纜敷設(shè)設(shè)計(jì)中的應(yīng)用

楊亞偉1，王璐2， 王斐1
（1.山東電力工程咨詢?cè)河邢薰?，山東濟(jì)南250013；2.山東省質(zhì)量技術(shù)監(jiān)督教育培訓(xùn)中心，山東濟(jì)南250013）

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

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

0　引 言

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

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

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

1　等長(zhǎng)路徑下電纜的彎曲次數(shù)問(wèn)題

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

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

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

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

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

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

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

2.1 A*算法的基本思想

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

式中：n為待擴(kuò)展的節(jié)點(diǎn)；f（n）為從起始節(jié)點(diǎn)到節(jié)點(diǎn)n的一條最佳路徑的實(shí)際代價(jià)加上從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的一條最佳路徑的代價(jià)之和；g（n）為從起始節(jié)點(diǎn)到節(jié)點(diǎn)n之間的最短路徑的實(shí)際代價(jià)；h（n）為從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的路徑估計(jì)代價(jià)。

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

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

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

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

圖2　A*算法流程圖

表2　A*算法搜索過(guò)程

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

3　改進(jìn)的A*算法

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

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

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

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

當(dāng)中間點(diǎn)M與終點(diǎn)T都確定的情況下，其之間路徑的最少?gòu)澢螖?shù)CMT為常數(shù)。此時(shí)，整個(gè)路徑的彎曲次數(shù)C的取值由CSM和CM這兩個(gè)參數(shù)決定。因此，當(dāng)CSM相同的情況下，整個(gè)路徑的彎曲次數(shù)并不一定相同，這取決于CM的取值。

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

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

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

圖3　改進(jìn)A*算法的流程圖

4　仿真結(jié)果

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

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

圖4　酒鋼鋁電一期工程汽機(jī)房零米層部分橋架簡(jiǎn)化模型

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

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

表3　仿真結(jié)果

5　實(shí)際應(yīng)用過(guò)程中需要注意的問(wèn)題

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

（1）路徑長(zhǎng)度的精度問(wèn)題

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

（2）纜流限制問(wèn)題

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

6　結(jié)束語(yǔ)

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

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

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

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

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

［5］ 王永慶.人工智能原理與方法［M］.西安：西安交通大學(xué)出版社，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-），男，碩士，工程師.

作者地址：山東濟(jì)南市華龍路1665號(hào)電力咨詢大廈1010室［250100］.