二次元配列間の距離について
スポンサーリンク
概要
- 論文の詳細を見る
二次元配列の近似マッチング問題として従来提案されてきたものは縦方向と横方向の扱いが異なる不自然なものであった。本稿では、より自然な近似マッチングを行うために、縦方向と横方向が対等に考慮される二次元配列間の距離(誤差)を定義する。そして、MAX-2SAT問題を還元することにより、一般的にはこの距離を計算することはNP困難であることを示す。一方、特殊な、しかし、ある程度現実的な場合には最短経路問題に帰着させることにより多項式時間で計算できることも示す。
- 一般社団法人情報処理学会の論文
- 1995-03-17
著者
関連論文
- 最小キーおよび最適部分構造スクリーンの近似
- 二つの点集合の最大共通部分点集合を求めるランダマイズド・アルゴリズム
- 二次元配列間の距離について
- タンパク質立体構造の折れ線による近似とその構造マッチングへの応用
- 可変長ギャップ付き文字列に対する近似マッチング・アルゴリズム
- タンパク質立体構造に対する部分構造検索およびアラインメント・アルゴリズム
- 高次元点集合の合同性判定について
- Don't Care記号つき文字列に対する近似マッチング・アルゴリズム
- 複数の点集合の最大共通部分集合の近似可能性について