|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 最 ： [さい] 1. (n,pref) the most 2. the extreme ・ 最長 ： [さいちょう] 【名詞】 1. the longest 2. the oldest ・ 長 ： [おさ] 【名詞】 1. chief 2. head ・ 共 ： [ども] 1. (suf) indicates plural - humble referring to oneself, disdainful referring to others ・ 共通 ： [きょうつう] 1. (adj-na,n,adj-no,vs) commonness 2. community ・ 通 ： [つう] 1. (adj-na,n) (1) connoisseur 2. authority 3. (2) counter for letters, notes, documents, etc. ・ 部分 ： [ぶぶん] 【名詞】 1. portion 2. section 3. part ・ 分 ： [ぶん, ふん] 1. (n,n-suf,pref) (1) part 2. segment 3. share 4. ration 5. (2) rate 6. (3) degree 7. one's lot 8. one's status 9. relation 10. duty 1 1. kind 12. lot 13. (4) in proportion to 14. just as much as 1 ・ 分列 ： [ぶんれつ] (n,vs) filing off (in a parade) ・ 列 ： [れつ] 【名詞】 1. queue 2. line 3. row ・ 問 ： [もん] 【名詞】 1. problem 2. question ・ 問題 ： [もんだい] 【名詞】 1. problem 2. question ・ 題 ： [だい] 1. (n,vs) title 2. subject 3. theme 4. topic
最長共通部分列問題（さいちょうきょうつうぶぶんれつもんだい、）とは、与えられた列の集合（多くの場合、2つの列からなる集合）の最長共通部分列を見つけ出す問題である。（ここで部分列(subsequence)は、部分文字列(substring)とは異なることに注意する。前者は元の列の連続した項からなる必要はない。）これは計算機科学における古典的問題であり、diff などのファイル比較プログラムの基礎をなし、バイオインフォマティクスにも応用されている。 == 計算量 == 汎用的な入力列の数が任意のときには、この問題はNP困難である。入力列の数が一定のときには、この問題は動的計画法によって多項式時間で解く事ができる（後の項参照）。長さが の 列が与えられたとする。素朴な探索では、最初の列の 個の部分列が残りの列の部分列であるかを確かめる。残りの配列もまた同様にテストを行う。それぞれの配列は、残りの配列長の線形時間で評価される。そして、このアルゴリズムの計算時間は、下記の通りである。 : 2つの配列 n と m エレメントの場合、動的計画法アプローチによるランニングタイムは、O(''n'' × ''m'')である。任意の入力配列数の場合、動的計画法アプローチによる解法では、下記のようになる。 : それらは、さほど複雑ではない計算方法が存在〔 〕し、それはしばしば、最長共通部分列の配列長か、アルファベットのサイズ、もしくはその両方に依存する。 注意：最長共通部分列は、必ずしも一意ではない。例として ”ABC” と ”ACB” の最長共通部分列は ”AB” と ”AC” の両方である。実際に最長共通部分列は、しばしば見つかったすべての最大長の共通部分列によって定義される。 この問題は本質的に高い複雑性を有しており、そのような部分列数は最悪の場合、指数関数的であり、2つの配列の場合も同様である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「最長共通部分列問題」の詳細全文を読む スポンサード リンク
|