試誤型史坦那樹演算法及電子設(shè)計自動化的應(yīng)用Obstacle-Avoiding課件

試誤型史坦那樹演算法及

電子設(shè)計自動化的應(yīng)用

Obstacle-AvoidingHeuristicsfor

SteinerTreeProbleminEDA

報告人：林琮徨指導(dǎo)教授：黃元欣博士詹景裕博士1

試誤型史坦那樹演算法及

電子設(shè)計自動化的應(yīng)用

ObstaOutlineIntroductionSteinerTreeProblem&XArchitectureHigherGeometryMazeRoutersAlgorithm(HGMRAlgorithm)Lou’sSteinerTreeAlgorithmLin’sSteinerTrees(ST)withoutObstaclesAlgorithmLin’sSteinerTreesexistLocalrefinementwithoutObstaclesAlgorithmLin’sSteinerTreeswithObstaclesAlgorithmLin’sSteinerTreesexistLocalrefinementwithObstaclesAlgorithmTheProposedAlgorithmExampleCompareTheProposedAlgorithmCompareTableConclusionsFutureStudies2OutlineIntroductionSteinerTr

IntroductionSteinerTreeProblemSteinervertexverticestobeinterconnectedInEuclideandomainGivenasetofnverticesontheplane,theSteinerMinimumTreeproblemistofindatreeintheplane,ofminimumtotalwirelength,whichconnectsthegivensetofvertices.3

IntroductionSteinerTreeProXArchitectureAnewinterconnectarchitectureisdifferentfrom“Manhattan”architecture.XArchitecturerotatestheprimarydirectionoftheinterconnectinthefourthandfifthmetallayersby45degrees.Theadvantagesarediscounting20%routingwiresand30%viainVLSIlayout.(Org:xinitiative)4XArchitectureAnewinterconneSteinerTreeProblemonXArchitectureAsimpleexampleofSteinerTreeon

Xarchitecture4GeometrySteinerMinimalTree,TotalLength=7.6565SteinerTreeProblemonXArchHigherGeometryMazeRoutersAlgorithmStep1.WavePropagationStep1.1Step1.2Step1.3Step2.BacktrackingStep2.1Step2.2Step2.36HigherGeometryMazeRoutersALou’sSteinerTreeAlgorithmStep1：利用HGMR演算法求出終端點(diǎn)之間的距離。Step2：利用Prime的MST演算法，算出連結(jié)所有終端點(diǎn)之MST樹長。Step3：對Map中每一點(diǎn)自由空間Ci,j，進(jìn)行下列所述：(1)：將此點(diǎn)當(dāng)作一個終端點(diǎn)，利用MST演算法，算出加入此點(diǎn)後的總樹長。(2)：將原本的樹長減去之後算出的樹長，紀(jì)錄在Ci,j中。Step4：Iteration*DefineT:Tree中的每個點(diǎn)的集合。(1)：建立ImprovementTable(IT)。(2)：找尋IT中最適合的Steinervertex，將其加入T後，執(zhí)行Step2~Step4.。(3)：若是IT中找不到合適的Steinervertex(IT值>0)

，則演算結(jié)束。7Lou’sSteinerTreeAlgorithmSt介紹米字型延伸(A2)(A1)(A3)(A5)(A4)(A6)8介紹米字型延伸(A2)(A1)(A3)(A5)(A4)(A6多點(diǎn)同時進(jìn)行米字型延伸找出所有可能的Steinervertex(B2)點(diǎn)對點(diǎn)(B1)(點(diǎn)對點(diǎn))9多點(diǎn)同時進(jìn)行米字型延伸找出所有可能的SteinervertLin’sSteinerTreewithoutObstacles

Algorithm

Step1：設(shè)定所有終端節(jié)點(diǎn)的米字型延伸範(fàn)圍。

Step2：使用座標(biāo)軸求所有終端節(jié)點(diǎn)間最短距離與米字型延伸的重疊點(diǎn)找所有可能的Steinervertex

Step3：利用Prime的MST演算法，算出連結(jié)所有終端點(diǎn)之MST樹長。Step4：對Map中指定範(fàn)圍內(nèi)的米字延伸交叉點(diǎn)Ci,j，進(jìn)行下列所述：(1)：將此點(diǎn)當(dāng)作一個終端點(diǎn)，利用MST演算法，算出加入此點(diǎn)後的總樹長。(2)：將原本的MST樹長減去之後算出的MST樹長，紀(jì)錄在Ci,j中。Step5：Iteration

*DefineT:Tree中的每個點(diǎn)的集合。(1)：建立ImprovementTable(IT)。(2)：找尋IT中最適合的Steinervertex，將其加入T後，執(zhí)行Step4。(3)：若是IT中找不到合適的Steinervertex(IT值>0)，則演算結(jié)束。

10Lin’sSteinerTreewithoutObsLin’sSteinerTreewithoutObstacles

Algorithm建立ImprovementTable(IT)。11Lin’sSteinerTreewithoutObsLin’sSteinerTreewithoutObstacles

AlgorithmImprovementTable中，找不到合適的Steinervertex(IT值>0)

，則演算法結(jié)束。12Lin’sSteinerTreewithoutObsLin’sSTexistLocalRefinementwithoutObstacles

AlgorithmStep1：設(shè)定所有終端節(jié)點(diǎn)的米字型延伸範(fàn)圍。

Step2：使用座標(biāo)軸求所有終端節(jié)點(diǎn)間最短距離與米字型延伸的重疊點(diǎn)找所有可能的Steinervertex

Step3：利用Prime的MST演算法，算出連結(jié)所有終端點(diǎn)之MST樹長。Step4：對Map中指定範(fàn)圍內(nèi)的米字延伸交叉點(diǎn)Ci,j，進(jìn)行下列所述：(1)：將此節(jié)點(diǎn)當(dāng)作一個終端點(diǎn)，找出距離此點(diǎn)線段長最小的三個終端點(diǎn)，並將此三點(diǎn)相同值的所有節(jié)點(diǎn)，皆以最短路徑相連成tree。(2)：將此tree加入目前的MST，刪除迴圈中最長的邊長，儲存修改此MST。(3)：將原本的MST樹長減去之後算出的MST樹長，紀(jì)錄在Ci,j中。Step5：

*DefineT:Tree中的每個點(diǎn)的集合。(1)：建立ImprovementTable(IT)。Iteration(2)：找尋IT中數(shù)值最大SteinervertexCi,j(IT值>0)，暫將其加入T，用原本的樹長減去之後算出的樹長，結(jié)果大於0則修改T，刪除IT中的此Ci,j

。結(jié)果小於等於0，則放棄此點(diǎn)，並且從IT中刪除Ci,j，直到IT中為正的值都測試完為止。

(3)：若是IT中找不到合適的Steinervertex(IT值>0)，則演算結(jié)束。

13Lin’sSTexistLocalRefinemenLocalRefinement示意圖14LocalRefinement示意圖14Lin’sSteinerTreewithObstacles

AlgorithmStep1：利用HGMR演算法求出終端點(diǎn)之間的距離Step2：使用Prime的MST演算法，算出連結(jié)所有終端點(diǎn)之MST樹長。Step3：利用HGMR演算法洪氾求出每個自由節(jié)點(diǎn)避開障礙物到達(dá)地圖盡頭(東、南、西、北、東南、東北、西南、西北)的最短路徑。Step4：將每個終端點(diǎn)使用米字型延伸後的重疊點(diǎn)找出所有可能的Steinervertex，直到整個地圖做完為止。Step5：對Map中的米字延伸交叉點(diǎn)Ci,j，進(jìn)行下列所述：(1)：將此點(diǎn)當(dāng)作一個終端點(diǎn)，利用PrimeMST演算法，算出加入此點(diǎn)後的總樹長。(2)：將原本的MST樹長減去之後算出的MST樹長，紀(jì)錄在Ci,j中。Step6：Iteration

*DefineT:Tree中的每個點(diǎn)的集合。(1)：建立ImprovementTable(IT)。(2)：找尋IT中最適合的Steinervertex，將其加入T後，執(zhí)行演算法中的Step5。(3)：若是IT中找不到合適的Steinervertex(IT值>0)，則演算結(jié)束。

15Lin’sSteinerTreewithObstac針對地圖最北邊的列座標(biāo)[(0,0)~(6,0)]之中的所有節(jié)點(diǎn)，將上面的所有節(jié)點(diǎn)放入HGMR演算法中的進(jìn)行洪氾。wavepropagationfinishwavepropagation16針對地圖最北邊的列座標(biāo)[(0,0)~(6,0)]之中的所有節(jié)針對地圖最西邊的行座標(biāo)[(0,0)~(0,6)]與最北邊的列座標(biāo)[(0,0)~(6,0)]之中的所有節(jié)點(diǎn)，將上面的所有節(jié)點(diǎn)放入HGMR演算法中的進(jìn)行洪氾。wavepropagationfinishwavepropagation17針對地圖最西邊的行座標(biāo)[(0,0)~(0,6)]與waveLin’sSTexistLocalRefinementwithObstacles

AlgorithmStep1：利用HGMR演算法洪氾求出每個自由節(jié)點(diǎn)避開障礙物到達(dá)地圖盡頭(東、南、西、北、東南、東北、西南、西北)的最短路徑。Step2：將每個終端點(diǎn)使用米字型延伸後的重疊點(diǎn)找出所有可能的Steinervertex，直到整個地圖做完為止。Step3：利用Prime的MST演算法，算出連結(jié)所有終端點(diǎn)之MST樹長。Step4：對Map中的米字延伸交叉點(diǎn)Ci,j，進(jìn)行LocalRefinement：(1)：將此節(jié)點(diǎn)當(dāng)作一個終端點(diǎn)，找出距離此點(diǎn)線段長最小的三個終端點(diǎn)，並將此三點(diǎn)相同值的所有節(jié)點(diǎn)，皆以最短路徑相連成tree。(2)：將此tree加入目前的MST，刪除迴圈中最長的邊長，儲存修改此MST。(3)：將原本的MST樹長減去之後算出的MST樹長，紀(jì)錄在Ci,j中。Step5：

*DefineT:Tree中的每個點(diǎn)的集合。(1)：建立ImprovementTable(IT)。Iteration(2)：找尋IT中數(shù)值最大SteinervertexCi,j(IT值>0)，暫將其加入T，用原本的樹長減去之後算出的樹長，結(jié)果大於0則修改T，刪除IT中的此Ci,j

。結(jié)果小於等於0，則放棄此點(diǎn)，並且從IT中刪除Ci,j，直到IT中為正的值都測試完為止。

(3)：若是IT中找不到合適的Steinervertex(IT值>0)，則演算結(jié)束。

18Lin’sSTexistLocalRefinemenHGMR、Lou’s、Lin’sAlgorithmLength

ExampleCompareResultofLou’s

(Length=13.8)ResultofHGMR

(Length=14.6)ResultofLin’s

(Length=13.8)19HGMR、Lou’s、Lin’sAlgorithmLeResultofHGMR

(Length=35.384)ResultofLou’s

(Length=34.142)ResultofLin’s

(Length=34.142)HGMR、Lou’s、Lin’sAlgorithmLength

ExampleCompare20ResultofHGMR

(Length=35.38AlgorithmCompareTableLou’sSMTAlgorithmO(N2+p3N)O(N2)Jan’sSMTAlgorithmO(p2N)O(pN)Lin’sSMTwithoutObstaclesAlgorithmO(p4)AlgorithmsItemsTimeComplexitySpaceComplexityO(pN+N+p4)O(pN)O(pN)O(N+p2)O(p2)p:#ofterminalvertices,N:#offreespaceLin’sSMTwithoutObstaclesAlgorithmexistLocalrefinementLin’sSMTwithObstaclesAlgorithmLin’sSMTwithoutObstaclesAlgorithmexistLocalrefinementO(pN)O(pN)21AlgorithmCompareTableLou’sConclusionsLin的演算法之所以優(yōu)於Lou，主要是在於Lou的演算法在找尋Steinervertex上花費(fèi)過多的時間去測試自由空間上的每一個節(jié)點(diǎn)，Lin的演算法收尋SteinerPoint僅在特定縮小範(fàn)圍內(nèi)測試少許的米字延伸交叉點(diǎn)，花費(fèi)較少的時間，在無障礙物空間下只需要，有障礙物也只需要Lin的演算法存在Localrefinement之下，有效的降低次方的時間，使得演算法更迅速的建立史坦那樹，不需每次都使用Prim‘sMST去重建所要測試的Steinervertex與Z節(jié)點(diǎn)。O(p3N)O(p2)O(N+p2)O(p)22ConclusionsLin的演算法之所以優(yōu)於Lou，主要是FutureStudiesVerifyourresultsofalgorithmsToanalyze3D26-DirectionalSteinerTreeAlgorithmCombineSteinertreeandsinglelayerroutingAlgorithm.23FutureStudiesVerifyourresul

試誤型史坦那樹演算法及

電子設(shè)計自動化的應(yīng)用

Obstacle-AvoidingHeuristicsfor

SteinerTreeProbleminEDA

報告人：林琮徨指導(dǎo)教授：黃元欣博士詹景裕博士24

試誤型史坦那樹演算法及

電子設(shè)計自動化的應(yīng)用

ObstaOutlineIntroductionSteinerTreeProblem&XArchitectureHigherGeometryMazeRoutersAlgorithm(HGMRAlgorithm)Lou’sSteinerTreeAlgorithmLin’sSteinerTrees(ST)withoutObstaclesAlgorithmLin’sSteinerTreesexistLocalrefinementwithoutObstaclesAlgorithmLin’sSteinerTreeswithObstaclesAlgorithmLin’sSteinerTreesexistLocalrefinementwithObstaclesAlgorithmTheProposedAlgorithmExampleCompareTheProposedAlgorithmCompareTableConclusionsFutureStudies25OutlineIntroductionSteinerTr

IntroductionSteinerTreeProblemSteinervertexverticestobeinterconnectedInEuclideandomainGivenasetofnverticesontheplane,theSteinerMinimumTreeproblemistofindatreeintheplane,ofminimumtotalwirelength,whichconnectsthegivensetofvertices.26

IntroductionSteinerTreeProXArchitectureAnewinterconnectarchitectureisdifferentfrom“Manhattan”architecture.XArchitecturerotatestheprimarydirectionoftheinterconnectinthefourthandfifthmetallayersby45degrees.Theadvantagesarediscounting20%routingwiresand30%viainVLSIlayout.(Org:xinitiative)27XArchitectureAnewinterconneSteinerTreeProblemonXArchitectureAsimpleexampleofSteinerTreeon

Xarchitecture4GeometrySteinerMinimalTree,TotalLength=7.65628SteinerTreeProblemonXArchHigherGeometryMazeRoutersAlgorithmStep1.WavePropagationStep1.1Step1.2Step1.3Step2.BacktrackingStep2.1Step2.2Step2.329HigherGeometryMazeRoutersALou’sSteinerTreeAlgorithmStep1：利用HGMR演算法求出終端點(diǎn)之間的距離。Step2：利用Prime的MST演算法，算出連結(jié)所有終端點(diǎn)之MST樹長。Step3：對Map中每一點(diǎn)自由空間Ci,j，進(jìn)行下列所述：(1)：將此點(diǎn)當(dāng)作一個終端點(diǎn)，利用MST演算法，算出加入此點(diǎn)後的總樹長。(2)：將原本的樹長減去之後算出的樹長，紀(jì)錄在Ci,j中。Step4：Iteration*DefineT:Tree中的每個點(diǎn)的集合。(1)：建立ImprovementTable(IT)。(2)：找尋IT中最適合的Steinervertex，將其加入T後，執(zhí)行Step2~Step4.。(3)：若是IT中找不到合適的Steinervertex(IT值>0)

，則演算結(jié)束。30Lou’sSteinerTreeAlgorithmSt介紹米字型延伸(A2)(A1)(A3)(A5)(A4)(A6)31介紹米字型延伸(A2)(A1)(A3)(A5)(A4)(A6多點(diǎn)同時進(jìn)行米字型延伸找出所有可能的Steinervertex(B2)點(diǎn)對點(diǎn)(B1)(點(diǎn)對點(diǎn))32多點(diǎn)同時進(jìn)行米字型延伸找出所有可能的SteinervertLin’sSteinerTreewithoutObstacles

Algorithm

Step1：設(shè)定所有終端節(jié)點(diǎn)的米字型延伸範(fàn)圍。

Step2：使用座標(biāo)軸求所有終端節(jié)點(diǎn)間最短距離與米字型延伸的重疊點(diǎn)找所有可能的Steinervertex

Step3：利用Prime的MST演算法，算出連結(jié)所有終端點(diǎn)之MST樹長。Step4：對Map中指定範(fàn)圍內(nèi)的米字延伸交叉點(diǎn)Ci,j，進(jìn)行下列所述：(1)：將此點(diǎn)當(dāng)作一個終端點(diǎn)，利用MST演算法，算出加入此點(diǎn)後的總樹長。(2)：將原本的MST樹長減去之後算出的MST樹長，紀(jì)錄在Ci,j中。Step5：Iteration

*DefineT:Tree中的每個點(diǎn)的集合。(1)：建立ImprovementTable(IT)。(2)：找尋IT中最適合的Steinervertex，將其加入T後，執(zhí)行Step4。(3)：若是IT中找不到合適的Steinervertex(IT值>0)，則演算結(jié)束。

33Lin’sSteinerTreewithoutObsLin’sSteinerTreewithoutObstacles

Algorithm建立ImprovementTable(IT)。34Lin’sSteinerTreewithoutObsLin’sSteinerTreewithoutObstacles

AlgorithmImprovementTable中，找不到合適的Steinervertex(IT值>0)

，則演算法結(jié)束。35Lin’sSteinerTreewithoutObsLin’sSTexistLocalRefinementwithoutObstacles

AlgorithmStep1：設(shè)定所有終端節(jié)點(diǎn)的米字型延伸範(fàn)圍。

Step2：使用座標(biāo)軸求所有終端節(jié)點(diǎn)間最短距離與米字型延伸的重疊點(diǎn)找所有可能的Steinervertex

Step3：利用Prime的MST演算法，算出連結(jié)所有終端點(diǎn)之MST樹長。Step4：對Map中指定範(fàn)圍內(nèi)的米字延伸交叉點(diǎn)Ci,j，進(jìn)行下列所述：(1)：將此節(jié)點(diǎn)當(dāng)作一個終端點(diǎn)，找出距離此點(diǎn)線段長最小的三個終端點(diǎn)，並將此三點(diǎn)相同值的所有節(jié)點(diǎn)，皆以最短路徑相連成tree。(2)：將此tree加入目前的MST，刪除迴圈中最長的邊長，儲存修改此MST。(3)：將原本的MST樹長減去之後算出的MST樹長，紀(jì)錄在Ci,j中。Step5：

*DefineT:Tree中的每個點(diǎn)的集合。(1)：建立ImprovementTable(IT)。Iteration(2)：找尋IT中數(shù)值最大SteinervertexCi,j(IT值>0)，暫將其加入T，用原本的樹長減去之後算出的樹長，結(jié)果大於0則修改T，刪除IT中的此Ci,j

。結(jié)果小於等於0，則放棄此點(diǎn)，並且從IT中刪除Ci,j，直到IT中為正的值都測試完為止。

(3)：若是IT中找不到合適的Steinervertex(IT值>0)，則演算結(jié)束。

36Lin’sSTexistLocalRefinemenLocalRefinement示意圖37LocalRefinement示意圖14Lin’sSteinerTreewithObstacles

AlgorithmStep1：利用HGMR演算法求出終端點(diǎn)之間的距離Step2：使用Prime的MST演算法，算出連結(jié)所有終端點(diǎn)之MST樹長。Step3：利用HGMR演算法洪氾求出每個自由節(jié)點(diǎn)避開障礙物到達(dá)地圖盡頭(東、南、西、北、東南、東北、西南、西北)的最短路徑。Step4：將每個終端點(diǎn)使用米字型延伸後的重疊點(diǎn)找出所有可能的Steinervertex，直到整個地圖做完為止。Step5：對Map中的米字延伸交叉點(diǎn)Ci,j，進(jìn)行下列所述：(1)：將此點(diǎn)當(dāng)作一個終端點(diǎn)，利用PrimeMST演算法，算出加入此點(diǎn)後的總樹長。(2)：將原本的MST樹長減去之後算出的MST樹長，紀(jì)錄在Ci,j中。Step6：Iteration

*DefineT:Tree中的每個點(diǎn)的集合。(1)：建立ImprovementTable(IT)。(2)：找尋IT中最適合的Steinervertex，將其加入T後，執(zhí)行演算法中的Step5。(3)：若是IT中找不到合適的Steinervertex(IT值>0)，則演算結(jié)束。

38Lin’sSteinerTreewithObstac針對地圖最北邊的列座標(biāo)[(0,0)~(6,0)]之中的所有節(jié)點(diǎn)，將上面的所有節(jié)點(diǎn)放入HGMR演算法中的進(jìn)行洪氾。wavepropagationfinishwavepropagation39針對地圖最北邊的列座標(biāo)[(0,0)~(6,0)]之中的所有節(jié)針對地圖最西邊的行座標(biāo)[(0,0)~(0,6)]與最北邊的列座標(biāo)[(0,0)~(6,0)]之中的所有節(jié)點(diǎn)，將上面的所有節(jié)點(diǎn)放入HGMR演算法中的進(jìn)行洪氾。wavepropagationfinishwavepropagation40針對地圖最西邊的行座標(biāo)[(0,0)~(0,6)]與waveLin’sSTexistLocalRefinementwithObstacles

AlgorithmStep1：利用HGMR演算法洪氾求出每個自由節(jié)點(diǎn)避開障礙物到達(dá)地圖盡頭(東、南、西、北、東南、東北、西南、西北)的最短路徑。Step2：將每個終端點(diǎn)使用米字型延伸後的重疊點(diǎn)找出所有可能的Steinervertex，直到整個地圖做完為止。Step3：利用Prime的MST演算法，算出連結(jié)所有終端點(diǎn)之MST樹長。Step4：對Map中的米字延伸交叉點(diǎn)Ci,j，進(jìn)行LocalRefinement：(1)：將此節(jié)點(diǎn)當(dāng)作一個終端點(diǎn)，找出距離此點(diǎn)線段長最小的三個終端點(diǎn)，並將此三點(diǎn)相同值的所有節(jié)點(diǎn)，皆以最短路徑相連成tree。(2)：將此tree加入目前的MST，刪除迴圈中最長的邊長，儲存修改此MST。(3)：將原本的MST樹長減去之後算出的MST樹長，紀(jì)錄在Ci,j中。Step5：

*DefineT:Tree中的每個點(diǎn)的集合。(1)：建立ImprovementTable(IT)。Iteration(2)：找尋IT中數(shù)值最大SteinervertexCi,j(IT值>0)，暫將其加入T，用原本的樹長減去之後算出的樹長，結(jié)果大於0則修改T，刪除IT中的此Ci,j

。結(jié)果小於等於0，則放棄此點(diǎn)，並且從IT中刪除Ci,j，直到IT中為正的值都測試完為止。

(3)：若是IT中找不到合適的Steinervertex(IT值>0)，則演算結(jié)束。

41Lin’sSTexistLocalRefinemenHGMR、Lou’s、