ID | 114970 |
Author |
Nagata, Yuichi
Tokushima University
Tokushima University Educator and Researcher Directory
KAKEN Search Researchers
Imamiya, Akinori
Tokushima University
Ono, Norihiko
Tokushima University
Tokushima University Educator and Researcher Directory
KAKEN Search Researchers
|
Keywords | Picture maze
Genetic algorithm
Edge assembly crossover
Longest path problem
Grid graph
|
Content Type |
Journal Article
|
Description | 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.
|
Journal Title |
Computers & Operations Research
|
ISSN | 03050548
|
NCID | AA11527685
AA00613617
|
Publisher | Elsevier
|
Volume | 115
|
Start Page | 104860
|
Published Date | 2019-12-09
|
Rights | © 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 (Published Version) | |
URL ( Publisher's Version ) | |
FullText File | |
language |
eng
|
TextVersion |
Author
|
departments |
Science and Technology
|