文献

J-GLOBAL ID：201302290622868299   整理番号：13A1143748

Rectilinear Steiner arborescence問題の厳密解法における枝刈り規則について

著者 (2件)： 長瀬将行 (セイコーエプソン) ,  高橋俊彦 (新潟大)
資料名： 電子情報通信学会論文誌 A  (IEICE Transaction on Fundamentals of Electronics, Communications and Computer Sciences (Japan Edition))
巻： J96-A  号： 7  ページ： 432-439  発行年： 2013年07月01日 
JST資料番号： S0621A  ISSN： 0913-5707  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 平面上に原点を含むn個の点集合Sが与えられたとき,原点を根とし,原点から各点への経路が(L₁距離で)最短となるように水平線分,垂直線分で構成された根付木をRectilinear Steiner arborescence(RSA)と呼ぶ。また,総線分長が最小となるRSAを最小RSA(MRSA)と呼ぶ。Sが第一象限の点のみからなる場合に,MRSAを求める効率的な厳密解法RSA/DPがLeung and Congによって提案された。本論文では,最初にRSA/DPに二つの枝刈り規則を導入し高速化したアルゴリズムRSA/DP++を示す。計算機実験により,n=100程度の場合,RSA/DP++の生成する部分問題数がRSA/DPの約1/200以下になることを確認した。次に,RSA/DP++に更に二つの新しい枝刈り規則を加えたアルゴリズムRSA/DP+++を提案する。同様の計算機実験により,RSA/DP+++の生成部分問題数はRSA/DP++の約10分の1以下となること,及び2時間以内にn=400程度のMRSAを求めることが可能であることを確認した。(著者抄録)

シソーラス用語： *厳密解 ,  *分枝限定法 ,  木探索 ,  C言語 ,  アルゴリズム ,  動的計画法 ,  最短路問題
準シソーラス用語： 枝刈り【木探索】 ,  再帰アルゴリズム

分類 (1件)： その他のオペレーションズリサーチの手法  (KA03070E)

引用文献 (7件)：

• S. Ramnath, ”New approximations for the rectilinear steiner arborescence problem,” IEEE Trans. Comput.-Aided Des., Integr. Circuits Syst., vol.22, no.7, pp.859-869, 2003.
• L. Nastansky, S.M. Selkow, and N.F. Stewart, ”Cost minimum trees in directed acyclic graphs,” Mathematical Methods of Operations Research, vol.18, no.1, pp.59-67, 1974.
• J.M. Ho, M.T. Ko, T.H. Ma, and T.Y. Song, ”Algorithms for rectilinear optimal multicast problem,” Proc. Int. Symp. Algorithms Computation, pp.106-115, 1992.
• K.S. Leung and J. Cong, ”Fast optimal algorithms for the rectilinear steiner arborescence problem,” Comput. Sci. Dept., Univ. Calif., Los Angeles, Tech. Rep. CSD960037, 1996.
• S.K. Rao, P. Sadyappan, F.K. Hwang, and P.W. Shor, ”The rectilinear Steiner arborescence problem,” Algorithmica, vol.7, pp.277-288, 1992.

タイトルに関連する用語 (4件)： 問題 ,  厳密解法 ,  枝刈り ,  規則