単純パターンを用いた複雑パターン生成アルゴリズムとその計算複雑さ

点击翻译按钮获取中文摘要

本研究の目標は,単純パターンの集合を用いて複雑パターンを生成するプロセスを計算問題として形式的に定義し,アルゴリズム論及び計算量理論的な観点から議論を行い,本問題が本質的に有する計算時間限界の解明と品質・性能保証された近似アルゴリズムの開発を行うことである.多くの場合に感覚的に議論されていた図形描画を,数学的・情報学的に議論することにより作業効率を計る尺度を明確にし,効率の良いアルゴリズム開発を目指す.本年度の検討事項とその研究成果は以下である.1.線画図形における複雑パターンを単純パターンにより生成する問題は,与えられた単純パターンを1つの頂点として,隣接する単純パターン間の関係を辺として無向グラフで表し,どの順番で生成するかという関係を辺の方向付けで表すことにより,グラフ有向化の問題として形式化できる.本年度は,最大出次数を最小化するグラフ有向化最適化問題について,入力グラフがカクタスの場合Pであること,カクタスの最小スーパークラスである外部平面グラフの場合弱NP困難であること,別のカクタスの最小スーパークラスであるP_42部グラフの場合弱NP困難であること,ダイヤモンドフリーグラフ,ハウスフリーグラフ,直並列グラフ,2部グラフ,平面グラフの場合にはいずれもNP困難となることを示した.2.2次元n×nメッシュ上に複雑パターンとして水平・垂直の黒線分が与えられ,単純パターンとして1×1タイルの4辺の白・黒線分の組み合わせが与えられた時の単純パターンによる複雑パターンの線画描画問題について,任意の複雑パターンを実現するための単純パターン集合の必要十分条件を示した.また,線画描画を最適化問題として定式化し,O((logn)^<1/2>)の近似精度を持つ多項式時間アルゴリズムを示した.