文献

J-GLOBAL ID：202002272670082043   整理番号：20A0750310

カオス探索によるグラフにおけるシュタイナー木問題の解法

Solving the Steiner tree problem in graphs by chaotic search

著者 (4件)： Fujita Misa (Department of Management Science, Graduate School of Engineering, Tokyo University of Science) ,  Kimura Takayuki (Department of Electrical, Electronics, and Communication Engineering, Faculty of Fundamental Engineering, Nippon Institute of Technology) ,  Ikeguchi Tohru (Department of Management Science, Graduate School of Engineering, Tokyo University of Science) ,  Ikeguchi Tohru (Department of Information and Computer Technology, Faculty of Engineering, Tokyo University of Science)
資料名： Nonlinear Theory and Its Applications, IEICE (Web)  (Nonlinear Theory and Its Applications, IEICE (Web))
巻： 11  号： 1  ページ： 90-108(J-STAGE)  発行年： 2020年 
JST資料番号： U0219A  ISSN： 2185-4106  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： グラフにおけるシュタイナー木問題はNP困難組合せ最適化問題である。NP困難組合せ最適化問題,例えば巡回セールスマン問題,二次割当問題,および車両経路選定問題を解決するために,カオス動力学による解法を探索するためのアルゴリズム,またはカオス探索は良い性能を示した。この観点から,本論文は,カオス動力学を有するグラフにおけるシュタイナー木問題を解決するためのアルゴリズムを提案した。カオス探索の性能をタブー探索の性能と比較し,カオス探索の探索特性を解析した。数値実験の結果から,カオス探索のパラメータが適切な値に設定されると,カオス探索は良好な性能を示し,カオス探索は探索プロセスの間のタブー探索よりも頻繁に最適解を出力することが分かり,このことは,カオス探索がメタ発見法としてタブー探索よりも高い能力を持つことを意味する。(翻訳著者抄録)

シソーラス用語： 解析 ,  *アルゴリズム ,  *NP困難 ,  最適化問題 ,  巡回セールスマン問題 ,  割当問題 ,  経路選定 ,  タブー探索 ,  実験 ,  解
準シソーラス用語： カオス解析 ,  *グラフアルゴリズム ,  *シュタイナー木 ,  二次割当問題 ,  数値実験 ,  最適解

著者キーワード (5件)： グラフにおけるSteiner木問題 ,  組合せ最適化 ,  メタヒューリスティックス ,  カオス探索 ,  ニューラルネットワーク

分類 (1件)： 計算理論  (JB02000A)

引用文献 (33件)：

• [1] V.P. Kompella, J.C. Pasquale, and G.C. Polyzos, “Multicast routing for multimedia communication,” IEEE/ACM Transactions on Networking, vol. 1, no. 3, pp. 286-292, 1993.
• [2] A.B. Kahng and G. Robins, “On optimal interconnections for VLSI,” in <i>The Springer International Series in Engineering and Computer Science</i>, Springer Science & Business Media, 1994.
• [3] A. Jean, A. Stéphane, B. Jean, D.W. Daniel, M. Guy, M.O.S. Mohamed, and S. Antoine. “Design and dimensioning of hydrogen transmission pipeline networks,” European Journal of Operational Research, vol. 229, pp. 239-251, 2013.
• [4] E.W. Dijkstra, “A note on two problems in connexion with graphs,” Numersche mathematik, vol. 1, no. 1, pp. 269-271, 1959.
• [5] R.L. Graham and P. Hell, “On the History of the Minimum Spanning Tree Problem,” Annals of the History of Computing, vol. 7, no. 1, pp. 43-57, 1985.

タイトルに関連する用語 (6件)： カオス ,  探索 ,  グラフ ,  木 ,  問題 ,  解法