等間隔の折り目を持つ紙の折り畳みの計算量について

概要

論文の詳細を見る
等間隔の折り目を持つ紙と折り目を折る向きが与えられたとき,可能な折り畳み方は数多く存在する.これらの折り状態の中で,crease width が最小となる折り畳み方を求める.ここで,crease width とは折り目に挟まれている紙の枚数のことである.この問題は,Stamp folding problem と呼ばれ,2 つのバリエーションが考えられている.crease width の最大値を最小化する問題と crease width の合計を最小化する問題である.この最小化問題は,数え上げ問題として定式化された.しかし,その計算量は知られていない.本研究では,始めに crease width の最大値を最小化する問題の強 NP 完全性を示す.次に crease width の合計を最小化する問題の解を求めるアルゴリズムを提案する.このアルゴリズムそのものは単純であるが,解析は自明ではない.そして,時間計算量が O(n2(n+kk))time であることを示す.ここで,n は折り目の数であり,k は目的とする crease width の合計である.つまり,k が定数のとき,このアルゴリズムの時間計算量は O(nk+2) である.したがって,小さい k に対しては効率よく解を求めることが出来る.
2011-05-09