WEKO3
アイテム
A genetic algorithm for the picture maze generation problem
https://tokushima-u.repo.nii.ac.jp/records/2007902
https://tokushima-u.repo.nii.ac.jp/records/2007902b0d6c539-e007-4e71-9b61-c037dd49f416
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
cor_115_104860.pdf (758 KB)
|
|
| Item type | 文献 / Documents(1) | |||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2020-07-16 | |||||||||||||||||||||||
| アクセス権 | ||||||||||||||||||||||||
| アクセス権 | open access | |||||||||||||||||||||||
| 資源タイプ | ||||||||||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||||||||||||
| 資源タイプ | journal article | |||||||||||||||||||||||
| 出版社版DOI | ||||||||||||||||||||||||
| 識別子タイプ | DOI | |||||||||||||||||||||||
| 関連識別子 | https://doi.org/10.1016/j.cor.2019.104860 | |||||||||||||||||||||||
| 言語 | ja | |||||||||||||||||||||||
| 関連名称 | 10.1016/j.cor.2019.104860 | |||||||||||||||||||||||
| 出版タイプ | ||||||||||||||||||||||||
| 出版タイプ | AM | |||||||||||||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||||||||||||
| タイトル | ||||||||||||||||||||||||
| タイトル | A genetic algorithm for the picture maze generation problem | |||||||||||||||||||||||
| 言語 | en | |||||||||||||||||||||||
| 著者 |
永田, 裕一
× 永田, 裕一
WEKO
695
× イマミヤ, アキノリ
× 小野, 典彦
WEKO
97
|
|||||||||||||||||||||||
| 抄録 | ||||||||||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||||||||||
| 内容記述 | 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. | |||||||||||||||||||||||
| 言語 | en | |||||||||||||||||||||||
| キーワード | ||||||||||||||||||||||||
| 言語 | en | |||||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||||||
| 主題 | Picture maze | |||||||||||||||||||||||
| キーワード | ||||||||||||||||||||||||
| 言語 | en | |||||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||||||
| 主題 | Genetic algorithm | |||||||||||||||||||||||
| キーワード | ||||||||||||||||||||||||
| 言語 | en | |||||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||||||
| 主題 | Edge assembly crossover | |||||||||||||||||||||||
| キーワード | ||||||||||||||||||||||||
| 言語 | en | |||||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||||||
| 主題 | Longest path problem | |||||||||||||||||||||||
| キーワード | ||||||||||||||||||||||||
| 言語 | en | |||||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||||||
| 主題 | Grid graph | |||||||||||||||||||||||
| 書誌情報 |
en : Computers & Operations Research 巻 115, p. 104860, 発行日 2019-12-09 |
|||||||||||||||||||||||
| 収録物ID | ||||||||||||||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||||||||||||||
| 収録物識別子 | 03050548 | |||||||||||||||||||||||
| 収録物ID | ||||||||||||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||||||||||||
| 収録物識別子 | AA11527685 | |||||||||||||||||||||||
| 収録物ID | ||||||||||||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||||||||||||
| 収録物識別子 | AA00613617 | |||||||||||||||||||||||
| 出版者 | ||||||||||||||||||||||||
| 出版者 | Elsevier | |||||||||||||||||||||||
| 言語 | en | |||||||||||||||||||||||
| 権利情報 | ||||||||||||||||||||||||
| 言語 | en | |||||||||||||||||||||||
| 権利情報 | © 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/ | |||||||||||||||||||||||
| EID | ||||||||||||||||||||||||
| 識別子 | 366715 | |||||||||||||||||||||||
| 識別子タイプ | URI | |||||||||||||||||||||||
| 言語 | ||||||||||||||||||||||||
| 言語 | eng | |||||||||||||||||||||||
