Total for the last 12 months
number of access : ?
number of downloads : ?
ID 114970
Author
Imamiya, Akinori Tokushima University
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