國立虎尾科技大學 |

Language: English

Back

新的分割近似演算法於RST問題之應用 = A New Partition...

國立虎尾科技大學

新的分割近似演算法於RST問題之應用 = A New Partitioning Algorithm for Solving The RST Problems

Record Type:	Language materials, printed : monographic
Paralel Title:	A New Partitioning Algorithm for Solving The RST Problems
Author:	吳杰峯,
Secondary Intellectual Responsibility:	黃俊平,
Secondary Intellectual Responsibility:	國立虎尾科技大學
Place of Publication:	雲林縣
Published:	國立虎尾科技大學;
Year of Publication:	民96[2007]
Edition:	初版
Description:	45面圖,表 : 30公分;
Subject:	分割
Subject:	Manhattan
Online resource:	http://140.130.12.251/ETD-db/ETD-search-c/view_etd?URN=etd-0724107-054922
Summary:	矩狀史丹納樹為一個由水平與垂直線所建構之無迴圈網路，此網路跨越所有已知點，矩狀的史丹納樹問題（rectilinear Steiner tree，RST）是一個NP-Complete問題，當RST問題尺度稍大時，計算時間極長，因此有許多學者嘗試推導近似法來求解，以便獲得不錯之行走路徑。L’RST演算法是由學者F.K.Hwang於1976年所提出，在1994年時，Ting-Hai Cha和Yu-Chin Hsu提出Local and Global演算方式來改善L’RST的總長度，然而在節點數過多時其計算時間也明顯變長許多，在本文中主要以Local and Global演算方式為基礎加以延伸提出一個新的演算方法，其方法為先確定節點數目在超過多少時會造成運算時間過長，再利用分割方法來減少個別運算時間且在合併時利用修正方法使得長度之修正，以便減少在節點數過多時所花費之時間。 Rectilinear Steiner tree is an acyclic network constructed by the horizontal and vertical line segment, that span over all the given nodes. RST is an NP-complete problem that consumes tremendous computation time. Due to its complexity on computation, many researchers tried to solve this problem approximately. L’RST algorithm was proposed by F.K.Hwang is 1976. Ting-Hai Cha and Yu-Chin Hsu proposed Local and Global algorithm to improve L’RST method. However, the computation time for Local and Global algorithm increases dramatically when the node number is large. A new algorithm is proposed in this study that divides the node set in to several smaller subsets to reduce the computational complexity , and these subsets will be reunified after the computation. This algorithm gives an efficient way to solve the RST problem with good approximation.

新的分割近似演算法於RST問題之應用 = A New Partitioning Algorithm for Solving The RST Problems
吳, 杰峯

新的分割近似演算法於RST問題之應用 = A New Partitioning Algorithm for Solving The RST Problems / 吳杰峯 - 初版. - 雲林縣 : 國立虎尾科技大學, 民96[2007]. - 45面 ; 圖,表 ; 30公分.
分割Manhattan

黃, 俊平

新的分割近似演算法於RST問題之應用 = A New Partitioning Algorithm for Solving The RST Problems
LDR:02756nam0 2200253 450 001 540274
010 0 $b 平裝
100 $a 20090417h akaa0chia50020302ba
101 0 $a chi
102 $a cw
105 $a ak am 000yy
200 1 $a 新的分割近似演算法於RST問題之應用 $d A New Partitioning Algorithm for Solving The RST Problems $f 吳杰峯
205 $a 初版
210 $a 雲林縣 $d 民96[2007] $c 國立虎尾科技大學
215 0 $a 45面 $c 圖,表 $d 30公分
314 $a 指導教授：黃俊平
328 $a 碩士論文--國立虎尾科技大學工業工程與管理究所
330 $a 矩狀史丹納樹為一個由水平與垂直線所建構之無迴圈網路，此網路跨越所有已知點，矩狀的史丹納樹問題（rectilinear Steiner tree，RST）是一個NP-Complete問題，當RST問題尺度稍大時，計算時間極長，因此有許多學者嘗試推導近似法來求解，以便獲得不錯之行走路徑。L’RST演算法是由學者F.K.Hwang於1976年所提出，在1994年時，Ting-Hai Cha和Yu-Chin Hsu提出Local and Global演算方式來改善L’RST的總長度，然而在節點數過多時其計算時間也明顯變長許多，在本文中主要以Local and Global演算方式為基礎加以延伸提出一個新的演算方法，其方法為先確定節點數目在超過多少時會造成運算時間過長，再利用分割方法來減少個別運算時間且在合併時利用修正方法使得長度之修正，以便減少在節點數過多時所花費之時間。 Rectilinear Steiner tree is an acyclic network constructed by the horizontal and vertical line segment, that span over all the given nodes. RST is an NP-complete problem that consumes tremendous computation time. Due to its complexity on computation, many researchers tried to solve this problem approximately. L’RST algorithm was proposed by F.K.Hwang is 1976. Ting-Hai Cha and Yu-Chin Hsu proposed Local and Global algorithm to improve L’RST method. However, the computation time for Local and Global algorithm increases dramatically when the node number is large. A new algorithm is proposed in this study that divides the node set in to several smaller subsets to reduce the computational complexity , and these subsets will be reunified after the computation. This algorithm gives an efficient way to solve the RST problem with good approximation.
510 1 $a A New Partitioning Algorithm for Solving The RST Problems
610 0 $a 分割 $a 曼哈頓 $a 矩狀的史丹納樹
610 1 $a Manhattan $a partitioning. $a rectilinear Steiner tree
681 $a 008.169M $b 2642
700 $a 吳 $b 杰峯 $3 523755
702 $a 黃 $b 俊平 $3 471353
712 $a 國立虎尾科技大學 $b 工業工程與管理究所 $3 523742
770 $a Chieh-Fung Wu $3 586698
772 $a J.P. Huang $3 586699
801 0 $a cw $b 虎尾科技大學 $c 20071207 $g CCR
801 2 $a cw $b 虎尾科技大學 $c 20090417 $g CCR
856 7 $u http://140.130.12.251/ETD-db/ETD-search-c/view_etd?URN=etd-0724107-054922