1、矢量圖中繞過(guò)阻礙物的最短路徑算法研究綱要矢量圖中繞過(guò)阻礙物的最短路徑算法研究綱要6/6矢量圖中繞過(guò)阻礙物的最短路徑算法研究綱要自動(dòng)化技術(shù)與應(yīng)用2003年第22卷第1期計(jì)算機(jī)應(yīng)用矢量圖中繞過(guò)阻礙物的最短路徑算法研究AlgorithmsForTheShortestPathRoundingObstaclesInVectorGraphics華中科技大學(xué)陳傳波唐浩ChenChuanbo,TangHao綱要:經(jīng)過(guò)比較幾種常有的有阻礙物時(shí)求最短路徑的算法,徑的近似算法。重點(diǎn)詞:最短路徑探究線(xiàn)繞障偏移量Abstract:ThispapercomparesseveralpathontheLine-searchi

2、ngalgorithm,bringsforwardanim2provedalgorithmKewords:TheOffsetforobstaclerounding中圖分類(lèi)號(hào):TP11:A文章編號(hào):100327241(2003)0120034203前言運(yùn)輸管理以及工程設(shè)計(jì)的很多方面,如各樣工藝路線(xiàn)的安排,電網(wǎng)及管道線(xiàn)網(wǎng)的鋪設(shè),電子地圖的尋路等問(wèn)題,都與圖的最短路徑問(wèn)題親密有關(guān)。在某些工程應(yīng)用中,如設(shè)計(jì)電路圖或布線(xiàn)圖時(shí),經(jīng)常碰到這樣的狀況:電路元件和已布好的連結(jié)線(xiàn)成為了布線(xiàn)阻礙。為了防止新的連結(jié)線(xiàn)穿越元器件,就一定按必定的策略使得某些已作好的連結(jié)線(xiàn)作出躲避,同時(shí)求出阻礙群中兩點(diǎn)間的最短路徑,按這條

3、路徑為新作的連結(jié)線(xiàn)布線(xiàn)。降低算法的時(shí)間復(fù)雜度和空間復(fù)雜度。往常求最短路徑是在一個(gè)連通圖中進(jìn)行,各個(gè)節(jié)點(diǎn)由有向或無(wú)向的連線(xiàn)連結(jié),而阻礙物群中最短路徑指的是圖中兩點(diǎn)經(jīng)過(guò)一條折線(xiàn)或曲線(xiàn)相連,不與任一阻礙物發(fā)生碰撞,且這條折線(xiàn)或曲線(xiàn)的路徑長(zhǎng)度或許代價(jià)最小。幾種經(jīng)典算法現(xiàn)有的算法分為兩類(lèi):走迷宮(Maze-running)算法和線(xiàn)搜尋(Line-searching)算法。阻礙物群中最短路徑問(wèn)題的定義最短路徑問(wèn)題是VLSI設(shè)計(jì)和幾何信息系統(tǒng)中的基本問(wèn)題,是一種計(jì)算機(jī)圖形搜尋算法,即在出發(fā)點(diǎn)和目標(biāo)點(diǎn)之間找出總代價(jià)最低的路徑。路徑尋優(yōu)算法一方面要達(dá)成探究最低代價(jià)的路徑,另一方面要做到盡可能快,盡可能少占用內(nèi)存

4、,即盡可能34Lee算法為第一個(gè)走迷宮算法,它是廣度優(yōu)先搜尋法的一個(gè)應(yīng)用,迷宮算法鑒于單元格點(diǎn)搜尋,在時(shí)間和空間上是低效的,所以人們提出了線(xiàn)搜尋算法。線(xiàn)搜尋算法的基本思想是結(jié)構(gòu)一個(gè)代表阻礙和結(jié)點(diǎn)地點(diǎn)的圖,經(jīng)過(guò)在圖中找尋最短路徑獲得原格點(diǎn)中的最短路徑1。此|TechniquesofAutomation&Applications計(jì)算機(jī)應(yīng)用自動(dòng)化技術(shù)與應(yīng)用2003年第22卷第1期類(lèi)算法有以下特色:(1)結(jié)構(gòu)的圖比原單元格點(diǎn)圖稀少;(2)結(jié)構(gòu)的圖擁有代表性,圖中的路徑與原網(wǎng)格中的路徑是寸靈巧調(diào)整探究起點(diǎn)及探究方向。改良的線(xiàn)探究算法因?yàn)樽呙詫m法是鑒于網(wǎng)格的布線(xiàn)算法,采納這類(lèi)算法要對(duì)實(shí)質(zhì)布線(xiàn)圖作必定簡(jiǎn)化,

5、以使得圖形坐標(biāo)數(shù)據(jù)位于網(wǎng)格上。且數(shù)據(jù)儲(chǔ)存空間和路徑搜尋時(shí)間隨線(xiàn)間距離的減少以平方關(guān)系而增添,當(dāng)布線(xiàn)圖比較復(fù)雜,元器件特別多時(shí),連結(jié)線(xiàn)寬度和線(xiàn)間距離愈來(lái)愈少,走迷宮算法就顯得有些力所不及了。本文主要對(duì)線(xiàn)探究算法進(jìn)行了改進(jìn),下邊詳盡表達(dá)。等價(jià)的;(3)對(duì)源結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn),結(jié)構(gòu)的圖中存在與原網(wǎng)格中的最短路徑對(duì)應(yīng)的路徑;(4)結(jié)構(gòu)圖的復(fù)雜度決定了算法的復(fù)雜度。李氏迷宮算法的基本思想李氏迷宮算法第一將布線(xiàn)地區(qū)分紅單位網(wǎng)格,而后沿著網(wǎng)格走線(xiàn),且每個(gè)網(wǎng)格在一個(gè)方向上只同意布一條線(xiàn),并在此基礎(chǔ)上搜尋路徑。使用矩陣網(wǎng)格后,布線(xiàn)其實(shí)是沿著曼哈坦路徑實(shí)現(xiàn)的。在布線(xiàn)算法中,因?yàn)橥Ｒ饬x上的兩點(diǎn)(x1,y1),(x2,

6、y2)之間的歐幾里德距離sqrt(x1-x2)3(x1-x2)+(y1-y2)3(y1-y2)計(jì)算波及大批的浮點(diǎn)運(yùn)算,411幾個(gè)基本觀(guān)點(diǎn)(1):,其某些區(qū)段是所():(x1,y1),(x2,y2dm=+x1-x2|+y1-Y2|,。是一條以目前點(diǎn)為起點(diǎn),有預(yù)約終點(diǎn)和必定寬度的水平、垂直或斜向射線(xiàn)。探究線(xiàn)的寬度即用來(lái)連結(jié)待連點(diǎn)對(duì)的連線(xiàn)寬度。探究過(guò)程實(shí)質(zhì)上是一個(gè)檢查計(jì)算過(guò)程,就是依據(jù)從起點(diǎn)至預(yù)約終點(diǎn)的方向,逐個(gè)檢查前面或雙側(cè)能否有元器件或已布連線(xiàn)等阻礙物阻擋探究線(xiàn)直通預(yù)約終點(diǎn)的過(guò)程2。(3)繞障偏移量:值得注意的是,采納這類(lèi)算法以后,兩點(diǎn)間的最短路徑將不獨(dú)一。李氏算法就是在上述網(wǎng)格中實(shí)現(xiàn)的,它的基

7、本思想能夠描繪為波的流傳過(guò)程的模擬。在一個(gè)存在阻礙的湖面上,若需找尋連結(jié)A,B兩點(diǎn)的最小道徑,能夠在A(yíng)點(diǎn)投下一枚石子,而后察看所惹起的水波流傳狀況。假設(shè)“水波”流傳時(shí)能量無(wú)損失,當(dāng)碰到阻礙時(shí),波產(chǎn)生反射,最初抵達(dá)的目標(biāo)點(diǎn)波前所經(jīng)過(guò)的路徑必然是一條最短距離。并且只需兩點(diǎn)間有通路存在,則自A點(diǎn)擴(kuò)散出去的波必定能流傳到B點(diǎn)。為了繞過(guò)阻礙,最短路徑不該與圖元訂交,因?yàn)榕R界最短路徑可能經(jīng)過(guò)了阻礙物的界限,所以一定加上必定的偏移量,稱(chēng)為繞障偏離量。相對(duì)每一阻礙,可有正負(fù)兩個(gè)繞障偏移量。此中,負(fù)偏移量小于0,正偏移量大于0。(4)登岸點(diǎn)線(xiàn)探究布線(xiàn)算法線(xiàn)探究布線(xiàn)算法實(shí)質(zhì)上是一種無(wú)網(wǎng)格布線(xiàn)算法,在線(xiàn)探究法中,不

8、用儲(chǔ)存各網(wǎng)點(diǎn)信息,只須儲(chǔ)存外形尺寸,儲(chǔ)存各連結(jié)線(xiàn)寬度及端點(diǎn)坐標(biāo)。但在詳細(xì)實(shí)現(xiàn)上,為了提升搜尋效率,常常外形尺寸一致、連線(xiàn)寬度一致,并將連線(xiàn)端點(diǎn)坐標(biāo)網(wǎng)格化,線(xiàn)探究能否依靠于網(wǎng)格,重點(diǎn)在于坐標(biāo)能否網(wǎng)格化。在鑒于網(wǎng)格的線(xiàn)探究中,探究線(xiàn)端點(diǎn)及回溯辦理時(shí)的步長(zhǎng)都以網(wǎng)格為單位計(jì)算。在無(wú)網(wǎng)格線(xiàn)探究方案中,坐標(biāo)以最小設(shè)計(jì)精度為單位,探究線(xiàn)端點(diǎn)則依據(jù)阻礙的幾何尺寸及探究線(xiàn)與阻礙之間的同意最小空隙而計(jì)算,回溯辦理以線(xiàn)間最小距離為步長(zhǎng),并聯(lián)合阻礙的幾何尺目前點(diǎn)可見(jiàn)的阻礙物上近來(lái)的極點(diǎn)。(5)分別點(diǎn)繞過(guò)阻礙物時(shí)探究線(xiàn)的起點(diǎn)。圖1表示圖如下圖,當(dāng)運(yùn)動(dòng)物體M沿探究線(xiàn)a行進(jìn),假如碰到阻礙TechniquesofAutoma

9、tion&Applications|35自動(dòng)化技術(shù)與應(yīng)用2003年第22卷第1期計(jì)算機(jī)應(yīng)用物O,則O的極點(diǎn)必然散布在a的雙側(cè),且部分邊是M可見(jiàn)的(圖中的實(shí)線(xiàn)邊),部分是不行見(jiàn)的(虛線(xiàn)邊),把M可見(jiàn)的阻礙得來(lái)臨界最短路徑S-v1-v2-v3-E2(圖中紅線(xiàn)),該路徑的某些區(qū)段是元器件的界限。物的極點(diǎn)分紅兩組,矢量a左邊的極點(diǎn)納入L組,右邊的納入R組。另設(shè)VL和VR分別是L和R組中離a最遠(yuǎn)的兩個(gè)極點(diǎn)。假如VL比VR離a更遠(yuǎn),則令C=R,不然令C=L。VC就是登岸點(diǎn)。M繞過(guò)阻礙物時(shí)第一向登岸點(diǎn)湊近。找到登岸點(diǎn)后,接著就是怎樣繞過(guò)阻礙物O。先把S與登岸點(diǎn)VC連結(jié),再把VC與E連結(jié)起來(lái)。視VC為目前點(diǎn),

10、記做P,假如PE不與阻礙物訂交,表示已繞過(guò)了阻礙物,稱(chēng)此P點(diǎn)為M繞過(guò)阻礙物O的分別點(diǎn)。不然把目前點(diǎn)從P出發(fā)順著(當(dāng)P在SE的左邊)或逆著(當(dāng)P在SE的右邊)O的界限移到下一個(gè)頂圖2兩點(diǎn)間的最短路徑下一步,S-v2-v-)。點(diǎn)上。繞過(guò)一個(gè)阻礙物后,假如后邊還有阻礙物,就把目前點(diǎn)作為新的起點(diǎn)重復(fù)上述過(guò)程,直到繞過(guò)全部阻礙物抵達(dá)終點(diǎn)E412基本思想(1),5結(jié)論筆者將本算法的思想應(yīng)用到電路布線(xiàn)圖的繪制和GIS道路搜尋應(yīng)用中,都獲得了較好的成效。因?yàn)楸舅惴ǖ奶骄烤€(xiàn)是從起點(diǎn)指向終點(diǎn)的射線(xiàn),且求出的最短路徑是在臨界最短路徑的基礎(chǔ)上加上繞障偏移量獲得的結(jié)果,繞障偏移量的計(jì)算也存在必定偏差,所以最后獲得的兩點(diǎn)

11、間繞過(guò)阻礙物的最短路徑是近似最短路徑3。最短路徑。(2)以第一步求出的臨界最短路徑為基準(zhǔn),考慮線(xiàn)寬等因素,加上繞阻礙偏移量,得出最后的最短路徑,該路徑不與阻礙物訂交。算法步驟第一將給定的開(kāi)端點(diǎn)和中斷點(diǎn)連起來(lái),獲得線(xiàn)段SE,從S指向E的射線(xiàn)SE為探究線(xiàn),沿探究線(xiàn)探究前面能否有阻礙物。找出與SE訂交的第一個(gè)阻礙物會(huì)合O,假如O不存在,則SE即為所求的解,不然在O上找到登岸點(diǎn),繞過(guò)O。假如O的分別點(diǎn)D不可以直抵中斷點(diǎn)E,中間存在阻礙物O,則求出以D為出發(fā)參照文件周智,等1用O(tlogt)的連結(jié)圖求有阻礙時(shí)的最短路徑J1計(jì)算機(jī)學(xué)報(bào),1999,5點(diǎn),E為目標(biāo)點(diǎn)時(shí)O上的登岸點(diǎn)VC。而后用與上述相同的方法求出D到VC的通路和VC到E的通路。如下圖,a,b,c,d表示阻礙物。S與E1之間沒(méi)有阻礙物,最短路徑為SE1;S與E2間存在阻礙物,第一沿探究線(xiàn)SE2探究,發(fā)現(xiàn)前面有阻礙物b,則繞過(guò)阻礙物b,分別點(diǎn)為v1,而后以v1為新的起點(diǎn),連結(jié)v1,E2,得探究線(xiàn)v1