講演抄録/キーワード |
講演名 |
2013-03-18 14:35
だまし絵迷路生成に関する複数のハミルトン閉路構成法の比較評価 ○柳谷不比等・上嶋章宏(阪電通大) COMP2012-58 |
抄録 |
(和) |
本稿では,白黒2 値画像の黒地部分が解となる絵画的迷路を発展させ,2 つの2 値画像(ダミー画像と解画像) に対し求解前はダミー画像が浮き出て見え,解画像と対応する解を持つ迷路(だまし絵迷路と呼ぶ) の生成を試みる.絵画的迷路生成に用いられる全域木に基づくハミルトン閉路構成法やSAT ソルバによるハミルトン閉路構成法などを組み合わせただまし絵迷路生成法を設計し,構成法ごとの計算時間や生成される迷路の品質評価および構成法の組み合わせにより生成された複数のだまし絵迷路の品質評価を行う. |
(英) |
This report proposes a new type of maze generation as a generalization of the {\it picturesque maze generation problem}, which outputs a maze in which the solution path fills up black pixels of an input black-and-white raster image.The picturesque mazes generation problem with illusory images has two input binary images, which are called a {\it solution image} and a {\it dummy image}, and outputs a picturesque maze, which has a solution corresponding to the solution image but looks like the dummy image before solving.
In this report, we propose a method generating picturesque mazes with illusory images by combining two constructions of Hamiltonian circuits, of which one is a method based on spanning trees and the other is a SAT encoding method. And, the proposed method is evaluated by using the formula based on feature quantity of mazes. |
キーワード |
(和) |
迷路生成 / 絵画的迷路 / ハミルトン閉路 / SAT ソルバ / / / / |
(英) |
Automatic generation of maze / Picturesque maze / Hamiltonian cycles / SAT solver / / / / |
文献情報 |
信学技報, vol. 112, no. 498, COMP2012-58, pp. 39-46, 2013年3月. |
資料番号 |
COMP2012-58 |
発行日 |
2013-03-11 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2012-58 |