文献

J-GLOBAL ID：201202261317223680   整理番号：12A1166368

Rogo,TSPベースのペーパーパズル:最適化法

Rogo, a TSP-based Paper Puzzle: Optimization Approaches

著者 (2件)： DYE Shane (Univ. of Canterbury) ,  PETTY Nicola Ward (Univ. of Canterbury)
資料名： Journal of Information Processing (Web)  (Journal of Information Processing (Web))
巻： 20  号： 3  ページ： 672-679 (J-STAGE)  発行年： 2012年 
JST資料番号： U0109A  ISSN： 1882-6652  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： Rogoは,2009年に創作された新しいタイプの数学パズルである。Rogoはグリッド上で報酬を集める部分集合選択TSPである。グリッドの正方形は空白,禁止,又は報酬値になっている。目的は,グリッドを回るループの中で与えられた数のステップを用いて最大のスコアを蓄積することである。本論文では,Rogoを離散的最適化問題として紹介した。部分ツアー除去制約の2つの代替集合を用いて,この問題にIP定式化を与えた。解の性質とRogoのインスタンスに基づく列挙ベースのアルゴリズムを提案した。幾つかのコンピュータによる実験結果を報告した。(翻訳著者抄録)

シソーラス用語： *ゲーム ,  *巡回セールスマン問題 ,  最適化問題 ,  数え上げ理論
準シソーラス用語： *パズル

分類 (2件)： 数理計画法  (KA03030M) ,  その他の情報処理  (JE15050M)

引用文献 (7件)：

• [1] Garey, M.R. and Johnson, D.S.: Computers and Intractability, W.H. Freeman (1979).
• [2] Kant, G.: Drawing planar graphs using the canonical ordering, Algorithmica, Vol.16, pp.4-32 (1996).
• [3] Khellerstrand, H.: Rogo grid puzzle in Answer Set Programming (Clingo) and MiniZinc, My Constraint Programming Blog, available from <http://www.hakank.org/constraint_programming_blog/2011/01/rogo_grid_puzzle_in_answer_set_programming_clingo_and_minizinc_1.html> (accessed 2011-02-03).
• [4] Laporte, G.: A concise guide to the Traveling Salesman Problem, Journal of the Operational Research Society, Vol.61, pp.35-40 (2010).
• [5] Laporte, G. and Matrello, S.: The selective travelling salesman problem, Discrete Applied Mathematics, Vol.26, pp.193-207 (1990).

タイトルに関連する用語 (3件)： ペーパー ,  パズル ,  最適化