近傍探索法の近似度推定法 ―巡回セールスマン問題を対象として―

• Item type: SIG Technical Reports(1)
• 公開日: 1990-07-16
• タイトル: 近傍探索法の近似度推定法 ―巡回セールスマン問題を対象として―
• タイトル / 言語: en
• タイトル: Estimation of Approximation for Neighborhood Search Method for Travelling Salesman Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪大学工学部
• 著者所属: 大阪大学工学部
• 著者所属: 大阪大学工学部
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Osaka University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Osaka University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Osaka University
• 著者名: 安田, 覚; 阪本, 清和; 中野, 秀男
• 著者名(英): Satoru, Yasuda; Kiyokazu, Sakamoto; Hideo, Nakano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 離散最適化問題に用いられる近傍探索法の良さの推定を、近似解を探索している途中で得られるデータから確率的に推定する方法について考察する。本報告では対象とする問題とその近傍探索法として、巡回セールスマン問題とλ最適法を取り上げる。50都市程度の問題例での計算結果から、あらかじめ最適値を予測した上での推定法が近似解の出現頻度推定に有効である事を確かめた。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We propose a method to estimate the accuracy of local optimal solution by many data obtained during the calculation of neighborhood search method in the combinatorial optimization problem. In this report, we consider λ-opt method for travelling salesman problem. From the computational experience of the problem instances with about 50 cities, we show that it is efficient for the estimation of the frequency distribution of local optimal values to use a method conjecturing an optimum value.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1990, 号 58(1990-AL-016), p. 15-21, 発行日 1990-07-16
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会