ID | 114970 |
著者 |
Imamiya, Akinori
Tokushima University
|
キーワード | Picture maze
Genetic algorithm
Edge assembly crossover
Longest path problem
Grid graph
|
資料タイプ |
学術雑誌論文
|
抄録 | A picture maze is a maze puzzle that reveals a hidden picture when the solution path is filled. The picture maze generation problem (PMGP) consists in generating a picture maze whose solution path draws the shape most similar to a given raster image. The PMGP can be formulated as the longest path problem (LPP) on grid graphs, and we propose a genetic algorithm (GA) for this problem. In our formulation, we optimize the start and exit positions simultaneously as well as the solution path. To construct an effective GA, we employ edge assembly crossover (EAX), which is known as a very effective crossover operator for the traveling salesman problem (TSP). However, because of the difference between the two problems, we adapt EAX to the PMGP in a novel manner. The proposed GA can generate satisfactory picture mazes in 17 s for complicated raster images with sizes up to 55 × 105.
|
掲載誌名 |
Computers & Operations Research
|
ISSN | 03050548
|
cat書誌ID | AA11527685
AA00613617
|
出版者 | Elsevier
|
巻 | 115
|
開始ページ | 104860
|
発行日 | 2019-12-09
|
権利情報 | © 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
|
EDB ID | |
出版社版DOI | |
出版社版URL | |
フルテキストファイル | |
言語 |
eng
|
著者版フラグ |
著者版
|
部局 |
理工学系
|