PHP アルゴリズム分析: 動的計画アルゴリズムを使用して最長共通部分列問題を解決するにはどうすればよいですか?

PHP アルゴリズム分析: 動的計画アルゴリズムを使用して最長共通部分列問題を解決するにはどうすればよいですか?

動的計画法アルゴリズム (動的計画法) は、重複する部分問題と最適な部分構造特性を持つ問題を解決するために通常使用される数学的最適化手法です。その中で最も長い共通部分列問題は古典的な動的計画法問題であり、文字列処理、グラフ理論、バイオインフォマティクスなどの分野で幅広く応用されています。

最長共通部分列の問題は、次のように簡単に説明できます。2 つの文字列 s1 と s2 が与えられた場合、それらの最長共通部分列 (最長共通部分列、LCS と呼ばれます) を見つけます。文字列の部分列とは、元の文字列から他の文字の順序を変更せずに一部の文字を削除した文字列です。

たとえば、文字列 s1 = "ABCD" および s2 = "ACDF" の場合、それらの最長共通部分列は "ACD" です。

次に、PHP 言語を使用して動的プログラミング アルゴリズムを実装し、最長共通部分列問題を解決しましょう。

function longestCommonSubsequence($s1, $s2) {
    $m = strlen($s1);
    $n = strlen($s2);
    $dp = array();

    // 初始化边界条件
    for ($i = 0; $i <= $m; $i++) {
        $dp[$i][0] = 0;
    }
    for ($j = 0; $j <= $n; $j++) {
        $dp[0][$j] = 0;
    }

    // 动态规划计算最长公共子序列长度
    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            if ($s1[$i - 1] == $s2[$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 ($s1[$i - 1] == $s2[$j - 1]) {
            $lcs = $s1[$i - 1] . $lcs;
            $i--;
            $j--;
        } else {
            if ($dp[$i - 1][$j] > $dp[$i][$j - 1]) {
                $i--;
            } else {
                $j--;
            }
        }
    }

    return $lcs;
}

// 测试
$s1 = "ABCD";
$s2 = "ACDF";
echo "最长公共子序列：" . longestCommonSubsequence($s1, $s2);

上記のコードでは、longestCommonSubsequence 関数を定義します。この関数は、2 つの文字列 s1 と s2 を受け入れ、最後の長い共通サブシーケンスを返します。 。

2 次元配列 $dp を使用して、計算プロセス中の中間結果を記録します。まず、境界条件を初期化します。つまり、文字列が空の場合、最長共通部分列の長さは 0 になります。

次に、2 つのネストされたループを使用して、最長の共通部分シーケンスの長さを計算します。現在の文字が等しい場合は、最後の文字を削除した後の 2 つの文字列の最長の共通部分列の長さに 1 を加えた長さを選択し、現在の文字が等しくない場合は、1 文字を削除した後の 2 つの文字列の最長の共通部分列を選択します。シーケンスの長さのより大きな値。

最後に、中間結果の 2 次元配列 $dp を使用して、最長の共通部分列の文字列を構築します。具体的には、右下隅から開始し、現在の文字が等しい場合は、それらを最長の共通部分列文字列に追加し、ポインタを左上に移動します。現在の文字が等しくない場合、ポインタの移動方向は動的計画法の計算結果に基づいて決定されます。

最後に、サンプル文字列「ABCD」と「ACDF」をテストし、最長共通部分列「ACD」を出力します。

上記のコードを通じて、動的計画法アルゴリズムを使用して最長共通部分列問題を解決し、例を通じてアルゴリズムの正確さと実現可能性を検証しました。実際のアプリケーションでは、このアルゴリズムを使用してさまざまな文字列処理の問題を解決し、プログラムの効率と精度を向上させることができます。

以上がPHP アルゴリズム分析: 動的計画アルゴリズムを使用して最長共通部分列問題を解決するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。