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

• 梅里 卓矢

• 斎藤 寿樹

• 上原 隆平

• 伊藤 大雄

書誌事項

タイトル別名

• Complexity of the stamp folding problem

抄録

等間隔の折り目を持つ紙と折り目を折る向きが与えられたとき，可能な折り畳み方は数多く存在する．これらの折り状態の中で，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 に対しては効率よく解を求めることが出来る．For a given mountain-valley pattern of equidistant creases on a long paper strip, there are many folded states consistent with the pattern. Among these folded states, we like to fold a paper so that the number of the paper layers between each pair of hinged paper segments, which is called the crease width at the crease point, is minimized. This problem is called the stamp folding problem and there are two variants of this problem; minimization of the maximum crease width, and minimization of the total crease width. This optimization problem is recently introduced and investigated from the viewpoint of the counting problem. However, its computational complexity is not known. In this paper, we first show that the minimization problem of the maximum crease width is strongly NP-complete. Hence we cannot solve the problem in polynomial time unless P=NP. We next propose an algorithm that solves the minimization problem. The algorithm itself is a straightforward one, but its analysis is not trivial. We show that this algorithm runs in O(n2(n+kk))time where n is the number of creases and k is the total crease width. That is, the algorithm runs in O(nk+2) time for a constant k. Hence we can solve the problem efficiently for a small constant k.

収録刊行物

• 研究報告アルゴリズム（AL）

  研究報告アルゴリズム（AL） 2011 (9), 1-7, 2011-05-09

詳細情報

• CRID: 1572543026893377792
• NII論文ID: 110008583107
• NII書誌ID: AN1009593X
• 本文言語コード: en
• データソース種別:
  • CiNii Articles