PHP アルゴリズム設計のアイデア: 最大共通部分列問題に対する効率的な解決策を達成するには?

PHP アルゴリズム設計のアイデア: 最大共通部分列問題に対する効率的な解決策を達成するにはどうすればよいですか?

最長共通部分列 (LCS) は、2 つの文字列内の最長の同一部分列を見つける問題です。実際のアプリケーションでは、LCS はテキストの類似性比較、バージョン管理、DNA 配列比較などの分野で広く使用されています。この記事では、この問題を解決するための効率的な解決策を紹介し、具体的なコード例を示します。

アルゴリズムのアイデア:

ダイナミック プログラミングは、LCS 問題を解決する一般的な方法です。 LCS 問題には最適な部分構造特性があります。つまり、2 つのシーケンスの最長共通部分列は、部分問題の最長共通部分列によって構築できます。この特性に従って、動的計画法を使用して LCS 問題を解決できます。

具体的なアルゴリズムの手順は次のとおりです。

1. 2 次元配列 dpm 1 を作成します。ここで、m と n はそれぞれ 2 つの入力文字列の長さです。

   • dpi は、最初の文字列の最初の i 文字と 2 番目の文字列の最初の j 文字の間の LCS の長さを表します。
2. dp 配列の最初の行と列を 0、つまり dpi=dp0=0 に初期化します。

3. 最初の文字列の i 番目の文字と 2 番目の文字列の j 番目の文字について、2 つの文字列の各文字をトラバースします。

   • If the two文字が等しい (つまり、最初の文字列の i 番目の文字と 2 番目の文字列の j 番目の文字が等しい) 場合、 dpi = dpi-1 1.
   • 2 つの文字が等しくない場合は、dpi = max(dpi-1, dpi)、つまり、前の文字と次の文字の LCS の大きい方の値が採用されます。
4. 2 つの文字列を走査した後、取得された dpm は、最長の共通部分シーケンスの長さになります。
5. dp配列の結果から、遡って最長の共通部分列を求めることができます。 dpm から開始して、左上隅に移動します。dpi が dpi-1 1 に等しい場合、現在の文字が LCS に属していることを意味します。文字を結果シーケンスに追加し、左上隅に移動します。

コード例:

functionlongestCommonSubsequence($str1, $str2){

$m = strlen($str1);
$n = strlen($str2);
$dp = array();

for($i=0; $i<=$m; $i++){
    $dp[$i] = array_fill(0, $n+1, 0);
}

for($i=1; $i<=$m; $i++){
    for($j=1; $j<=$n; $j++){
        if($str1[$i-1] == $str2[$j-1]){
            $dp[$i][$j] = $dp[$i-1][$j-1] + 1;
        }
        else{
            $dp[$i][$j] = max($dp[$i-1][$j], $dp[$i][$j-1]);
        }
    }
}

$lcs = "";
$i = $m;
$j = $n;

while($i>0 && $j>0){
    if($str1[$i-1] == $str2[$j-1]){
        $lcs = $str1[$i-1] . $lcs;
        $i--;
        $j--;
    }
    else if($dp[$i-1][$j] > $dp[$i][$j-1]){
        $i--;
    }
    else{
        $j--;
    }
}

return $lcs;

}

$ str1 = "ABCBDAB";
$str2 = "BDCAB";
$lcs =longestCommonSubsequence($str1, $str2);
echo "入力文字列: $str1 および $str2
" ;
echo "最長の共通部分シーケンスは次のとおりです: $lcs
";
?>

上記のコードは出力します:

入力文字列: ABCBDAB およびBDCAB
最長共通部分列は次のとおりです: BCBA

結論:

この記事では、動的プログラミング アルゴリズムを使用して最大共通部分列問題を解決するアイデアと、特定の PHP コード例を紹介します。動的計画法を使用すると、LCS 問題を効率的に解決できます。このアルゴリズムの時間計算量は O(m*n) です。ここで、m と n はそれぞれ 2 つの入力文字列の長さです。実際のアプリケーションでは、スペースの複雑さを軽減するためにローリング アレイなどの技術を使用するなど、ニーズに応じてアルゴリズムを最適化できます。

以上がPHP アルゴリズム設計のアイデア: 最大共通部分列問題に対する効率的な解決策を達成するには?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。