WEKO3
-
RootNode
アイテム
A New Data Structure for Lin-Kernighan Traveling Salesman Heuristic
http://hdl.handle.net/10458/282
http://hdl.handle.net/10458/282803542d5-ba2c-47c9-9b1c-0483154fa972
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
KJ00002426422.pdf (609.2 kB)
|
|
| Item type | 紀要論文 / Departmental Bulletin Paper(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2007-06-28 | |||||
| タイトル | ||||||
| タイトル | A New Data Structure for Lin-Kernighan Traveling Salesman Heuristic | |||||
| 言語 | en | |||||
| 言語 | ||||||
| 言語 | eng | |||||
| キーワード | ||||||
| 言語 | en | |||||
| 主題Scheme | Other | |||||
| 主題 | Traveling salesman problem, Combinatorial optimization, Lin-Kernighan heuristic, Data structure, Algorithm analysis, Three-level trees | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
| 資源タイプ | departmental bulletin paper | |||||
| その他（別言語等）のタイトル | ||||||
| その他のタイトル | A New Data Structure for Lin-Kernighan Traveling Salesman Heuristic | |||||
| 言語 | en | |||||
| 著者 |
Nguyen, Hung Dinh
× Nguyen, Hung Dinh× Yoshihara, Ikuo× 山森, 一人× Yasunaga, Moritoshi |
|||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | Abstract The Lin-Kernighan (LK) heuristic is one of the most effective and efficient algorithms for the Traveling Salesman Problem (TSP). However, the LK heuristic is quite complicated and has many choices for implementing it. Especially, the data structure for tour representation plays an important role in the LK's performance. Traditionally, binary trees (including splay trees) are asymptotically the best tour representation. Empirically, however, they are utilized only for solving problems with more than one million cities due to the large overhead. Arrays are suitable for solving problems having up to a thousand cities and two-level trees are used for the problems with a thousand to a million cities. This paper proposes three-level trees as a new data structure. Although this structure is asymptotically not better than the existing ones, it perform empirically better than the existing ones in the range being investigated in this study (from 10(3乗) to 10(6.5乗) cities). |
|||||
| 言語 | en | |||||
| 書誌情報 |
ja : 宮崎大学工学部紀要 en : Memoirs of Faculty of Engineering, University of Miyazaki 巻 32, p. 303-308, 発行日 2003-07 |
|||||
| 出版者 | ||||||
| 出版者 | 宮崎大学工学部 | |||||
| 言語 | ja | |||||
| 出版者 | ||||||
| 出版者 | Faculty of Engineering, University of Miyazaki | |||||
| 言語 | en | |||||
| ISSN | ||||||
| 収録物識別子タイプ | ISSN | |||||
| 収録物識別子 | 05404924 | |||||
| 書誌レコードID | ||||||
| 収録物識別子タイプ | NCID | |||||
| 収録物識別子 | AA00732558 | |||||
| 著者版フラグ | ||||||
| 出版タイプ | VoR | |||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||
Share
Cite as
Nguyen, Hung Dinh, Yoshihara, Ikuo, 山森, 一人, Yasunaga, Moritoshi, 2003, A New Data Structure for Lin-Kernighan Traveling Salesman Heuristic: 宮崎大学工学部, 303–308 p.
Loading...
