翻訳と辞書 Words near each other ・ 最適者生存 ・ 最適葉面積指数 ・ 最適要因 ・ 最適農業経営規模 ・ 最適通貨圏 ・ 最適選択 ・ 最適遺伝子型 ・ 最重点 ・ 最長 ・ 最長不倒距離 ・ 最長共通部分列問題 ・ 最長片道切符 ・ 最長片道切符でゆく42日 ・ 最長片道切符で行く ・ 最長片道切符の旅 ・ 最長筋 ・ 最雲法親王 ・ 最頻値 ・ 最首公司 ・ 最首悟 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク 最長共通部分列問題 ： ウィキペディア日本語版 最長共通部分列問題[さいちょうきょうつうぶぶんれつもんだい] 最長共通部分列問題（さいちょうきょうつうぶぶんれつもんだい、）とは、与えられた列の集合（多くの場合、2つの列からなる集合）の最長共通部分列を見つけ出す問題である。（ここで部分列(subsequence)は、部分文字列(substring)とは異なることに注意する。前者は元の列の連続した項からなる必要はない。）これは計算機科学における古典的問題であり、diff などのファイル比較プログラムの基礎をなし、バイオインフォマティクスにも応用されている。 == 計算量 == 汎用的な入力列の数が任意のときには、この問題はNP困難である。入力列の数が一定のときには、この問題は動的計画法によって多項式時間で解く事ができる（後の項参照）。長さが $n\_1,\; ...,\; n\_N$ の$N$ 列が与えられたとする。素朴な探索では、最初の列の $2^$ 個の部分列が残りの列の部分列であるかを確かめる。残りの配列もまた同様にテストを行う。それぞれの配列は、残りの配列長の線形時間で評価される。そして、このアルゴリズムの計算時間は、下記の通りである。 :$O\backslash left(\; 2^\; \backslash sum\_\; n\_i\backslash right).$ 2つの配列 n と m エレメントの場合、動的計画法アプローチによるランニングタイムは、O(''n'' × ''m'')である。任意の入力配列数の場合、動的計画法アプローチによる解法では、下記のようになる。 :$O\backslash left(N\; \backslash prod\_^\; n\_i\backslash right).$ それらは、さほど複雑ではない計算方法が存在〔 〕し、それはしばしば、最長共通部分列の配列長か、アルファベットのサイズ、もしくはその両方に依存する。 注意：最長共通部分列は、必ずしも一意ではない。例として ”ABC” と ”ACB” の最長共通部分列は ”AB” と ”AC” の両方である。実際に最長共通部分列は、しばしば見つかったすべての最大長の共通部分列によって定義される。 この問題は本質的に高い複雑性を有しており、そのような部分列数は最悪の場合、指数関数的であり、2つの配列の場合も同様である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「最長共通部分列問題」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.