2

配列を使用せずに最も長い共通部分列を見つけるにはどうすればよいですか? ocaml の折り畳みリストのみ

4

1 に答える 1

2

これは動的計画法の典型的な例です。実装する関数は再帰的に簡単に指定できますが、再帰呼び出しに対応するサブ問題には多くの重複があります。単純な再帰的実装は、これらのサブ問題を再計算することによって役に立たない作業を行い、指数関数的な実行時間につながりますが、メモ化または別のアプローチのいずれかが多項式アルゴリズムにつながります。

ウィキペディアで提供されている最長共通部分列（LCS）問題の定式化 は、次のとおりです（擬似コード）。

LCS(X,Y,0,0) = []
LCS(X,Y,i,j) =
  if X[i] = Y[j] then X[i]::LCS(X,Y,i-1,j-1)
  else longest(LCS(X,Y,i-1,j), LCS(X,Y,i,j-1))

配列やインデックスではなくリストをパラメーターとして受け取るように変換すると、次の定式化が行われます（まだ擬似コード）。

LCS([], []) = []
LCS([x],[]) = []
LCS([], [y]) = []
LCS(x::xs, y::ys) =
  if x = y then x::LCS(xs, ys)
  else longest(LCS(x::xs, ys), LCS(xs, y::ys))

これからOCamlの実装を簡単に引き出すことができるはずです（これは演習であり、自分で解決策を見つけることができると思います）が、これはO(2^N) 長さの入力で最悪の場合の実行時間を伴う指数アルゴリズムになりNます。

例で非効率がどこから来ているかを確認するために、入力がであり、が[x;y;z]と[x';y';z']はx異なると仮定しますx'。1つとlcs [x;y;z] [x';y';z']1つの2つの再帰呼び出しを行います。しかし、その後、これらの2つの呼び出しは、それぞれ2つの呼び出しを行い 、最初の呼び出しと2番目の呼び出しを行います。どちらも再帰呼び出しを行うため、2回計算されることに注意してください。十分に長い入力の場合、他のサブコールは任意の回数だけ再計算されます。lcs [y;z] [x';y';z']lcs [x;y;z] [y';z']lcs [z] [x';y';z']lcs [y;z] [y';z']lcs [y;z] [y';z']lcs [x;y;z] [z']lcs [y;z] [y';z']

この非効率性を回避するための解決策は、各結果を1回だけ計算するデータ構造を構築することです。これを行う従来の方法は、変更可能な2Dマトリックスを使用して結果を格納することですが、これを使用することは許可されていません。対応するリストのリストを計算することにより、機能的なデータ構造を使用して結果を格納できます。

[
  [lcs [x;y;z] [x';y';z']; lcs [x;y;z] [y';z']; lcs [x;y;z] [z']; lcs [x;y;z] [];]; 
  [lcs [y;z] [x';y';z'];   lcs [y;z] [y';z'];   lcs [y;z] [z'];   lcs [y;z] [];];
  [lcs [z] [x';y';z'];     lcs [z] [y';z'];     lcs [z] [z'];     lcs [z] [];];
  [lcs [] [x';y';z'];      lcs [] [y';z'];      lcs [] [z'];      lcs [] [];];
]

この結果のリストを計算するための単純な再帰的な方法を見つけることは、興味深い高度な演習のようです。たとえば、サイド3の右下のサブスクエアを計算し、それを（リストのリストとして）折りたたんで結果のスクエアの左側を計算し、次にフォールドすることで、サイド4のこの「正方形」を再帰的に計算できます。その行（リストのリストの先頭）は、結果の正方形の上面を計算します。lcs_results xs ysより一般的には、長さの2つのシーケンスを取りM、このように編成されたによって計算されるすべてのサブ結果に対応するリストのリストNを返す関数を定義できます。MxNlcs xs ys

ただし、あなたは単に素朴で指数関数的な定式化を探していると思います（ここでも、教育演習のように見えます）。

于 2013-02-15T09:23:25.707 に答える