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);

위 코드에서는 역추적 검색을 수행하는 데 backtrack 함수가 사용되었습니다. 선택한 요소의 수가 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);

위 코드에서는 역추적 검색을 수행하기 위해 backtrack 함수를 사용합니다. 선택한 요소의 수가 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);

위 코드에서는 역추적 검색을 수행하는 데 backtrack 함수가 사용되었습니다. 끝점에 도달하면 현재 경로 경로를 결과 배열 $res에 기록합니다. for 루프에서는 오른쪽, 아래, 왼쪽, 위의 네 방향으로 앞으로 이동하고 재귀 호출을 시도합니다. 재귀 호출 전에 현재 그리드가 통과 가능한 그리드인지 확인하고 반복 방문을 피하기 위해 액세스할 수 없는 그리드로 표시해야 합니다.

위 내용은 PHP에서 역추적 알고리즘 구현 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!