GAを用いた方形ピースジグソーパズルの組立て

摘要

本論文では，方形ピースのジグソーパズルを組み立てる手法を提案する．ピースの形状は方形とし，パズルの表面は白と黒からなる2値画像とする．パズルの組立ては，ピースの輪郭線上の画素値の情報のみを用いて行われる．この問題は，類似したピースが多数存在するため，二つのピース間の局所的なマッチングでは解くことはできず大域的な探索が必要となる．本研究では，遺伝的アルゴリズム（GA）を用いて最適なピースの配置を求める．GAを用いる際，交叉や突然変異によって同じピースを重複して使用してはならないというパズルの制約条件を崩すことなく最適解を効率的に探索できるような，染色体のコーデイング，交叉法を提案する．提案手法では9×9ピースのパズルの組立てに成功した．