PHPにおけるバックトラッキングアルゴリズムの実装方法

PHP でのバックトラッキング アルゴリズムの実装方法

バックトラッキング アルゴリズムは、問題を解決するために一般的に使用される方法です。その中心的な考え方は、考えられるすべての解決策を再帰的に試行し、問題の要件に従って続行することです。条件を満たす最適解を見つけます。

PHP では、バックトラッキング アルゴリズムを使用して、組み合わせ問題、順列問題、迷路などの一連の問題を解決できます。以下では、PHP でバックトラッキング アルゴリズムを実装する方法とコード例を紹介します。

1. 組み合わせ問題のバックトラッキング アルゴリズム実装

組み合わせ問題とは、選択された要素が特定の条件を満たすように、指定されたセットからいくつかの要素を選択することを指します。組み合わせ C(n, k) を例にとります。ここで、n は指定されたセットのサイズを表し、k は選択される要素の数を表します。以下は、組み合わせ問題を解決するための PHP でのバックトラック アルゴリズム実装の例です。

function backtrack($nums, $k, $start, $track, &$res) {
    if (count($track) == $k) {
        $res[] = $track;
        return;
    }
    
    for ($i = $start; $i < count($nums); $i++) {
        $track[] = $nums[$i];
        backtrack($nums, $k, $i + 1, $track, $res);
        array_pop($track);
    }
}

function combine($n, $k) {
    $nums = [];
    for ($i = 1; $i <= $n; $i++) {
        $nums[] = $i;
    }
    
    $res = [];
    backtrack($nums, $k, 0, [], $res);
    return $res;
}

$n = 4;
$k = 2;
$result = combine($n, $k);
print_r($result);

上記のコードでは、バックトラック関数を使用してバックトラック検索を実行します。選択された要素の数が k に等しい場合、現在のトラックを結果配列 $res に記録します。次に、for ループで再帰呼び出しを行います。渡されるパラメーターは、指定されたセット $nums、選択される要素の数 $k、現在選択されている開始位置 $start、現在選択されている要素配列 $track、および Result 配列です。 $res。

2. 順列問題のバックトラッキング アルゴリズム実装

順列問題とは、選択された要素が満たされた順序で配置されるように、指定されたセットから対応する数の要素を選択することを指します。特定の条件。配置 P(n, k) を例にとります。ここで、n は指定されたセットのサイズを表し、k は選択される要素の数を表します。以下は、順列問題を解決するための PHP でのバックトラック アルゴリズムの実装の例です。

function backtrack($nums, $k, &$visited, $track, &$res) {
    if (count($track) == $k) {
        $res[] = $track;
        return;
    }
    
    for ($i = 0; $i < count($nums); $i++) {
        if (!$visited[$i]) {
            $visited[$i] = true;
            $track[] = $nums[$i];
            backtrack($nums, $k, $visited, $track, $res);
            array_pop($track);
            $visited[$i] = false;
        }
    }
}

function permute($nums, $k) {
    $res = [];
    $visited = array_fill(0, count($nums), false);
    backtrack($nums, $k, $visited, [], $res);
    return $res;
}

$nums = [1, 2, 3];
$k = 2;
$result = permute($nums, $k);
print_r($result);

上記のコードでは、バックトラック関数を使用してバックトラック検索を実行します。選択された要素の数が k に等しい場合、現在のトラックを結果配列 $res に記録します。 for ループでは、毎回未訪問の要素を選択し、トラックに追加します。次に、再帰呼び出しを行います。渡されるパラメータは、指定されたセット $nums、選択される要素の数 $k、現在の要素が訪問されたかどうかを記録する配列 $visited、現在選択されている要素配列 $track、および結果の配列。

3. 迷路問題のバックトラッキング アルゴリズム実装

迷路問題とは、特定の迷路内で開始点から終点までの経路を見つけることを指します。迷路は 2 次元配列で表すことができます。0 は通過可能なグリッドを表し、1 は障害物を表します。以下は、PHP で迷路問題を解決するためのバックトラック アルゴリズムの実装の例です。

function backtrack($maze, $i, $j, $path, &$res) {
    if ($i == count($maze) - 1 && $j == count($maze[0]) - 1) {
        $res[] = $path;
        return;
    }
    
    $maze[$i][$j] = -1;
    
    $dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    $dirNames = ['right', 'down', 'left', 'up'];
    
    for ($k = 0; $k < 4; $k++) {
        $ni = $i + $dirs[$k][0];
        $nj = $j + $dirs[$k][1];
        
        if ($ni >= 0 && $ni < count($maze) && $nj >= 0 && $nj < count($maze[0]) && $maze[$ni][$nj] == 0) {
            backtrack($maze, $ni, $nj, $path . ' -> ' . $dirNames[$k], $res);
        }
    }
    
    $maze[$i][$j] = 0;
}

function solveMaze($maze) {
    $res = [];
    backtrack($maze, 0, 0, '(0, 0)', $res);
    return $res;
}

$maze = [
    [0, 1, 0, 0],
    [0, 0, 0, 1],
    [1, 1, 0, 0],
    [0, 0, 0, 0]
];

$result = solveMaze($maze);
print_r($result);

上記のコードでは、バックトラック関数を使用してバックトラック検索を実行します。終点に到達したら、現在のパス path を結果配列 $res に記録します。 for ループでは、右、下、左、上の 4 つの方向に前進しようとし、再帰呼び出しを行います。再帰呼び出しの前に、現在のグリッドが通行可能なグリッドであるかどうかを判断し、繰り返しのアクセスを避けるためにアクセス不可としてマークする必要があります。

以上がPHPにおけるバックトラッキングアルゴリズムの実装方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。