미로 문제를 해결하기 위한 역추적 방법

소개

최근에 leetcode에서 몇 가지 알고리즘 질문을 읽었습니다. 그 중 일부는 매우 간단하고 일반적으로 사용되는 것처럼 보였지만 어떻게 해결할 수 있는지 알 수 없었습니다. 예: 实现sqrt函数,求数组的排列 . 고급 수학을 잘하지 못한다면 이러한 겉보기에 단순해 보이는 문제는 처음 접할 때 해결하기 어려울 것입니다. 미로. 이 문제를 해결하는 방법 역추적이라는 아이디어에 관해서, 이 아이디어를 이해하지 못하면 조금 더 복잡한 문제를 해결하기 어려울 것입니다.

문제 설명

방황하다가 정확히 어디에 있는지 기억이 나지 않는 문제가 발생했습니다.

<code>1   1   1   1

0   1   0   1

0   1   0   1

0   1   1   1</code>

상단이 미로입니다. 왼쪽 상단이 입구이고 오른쪽 하단이 출구입니다. (맞습니다. 풀이 있는 Xiao Ming입니다.) 입구 및 출구에서 탈출합니다(1시간 이내에 탈출하지 못하면 X 몬스터에게 먹히게 됩니다). 여기서 1은 통과 가능함을 의미하고, 0은 오른쪽과 두 방향으로만 통과할 수 없음을 의미합니다. 작고 귀여운 아이들이 탈출할 수 있는 경로를 모두 찾아보세요.

이 질문은 꽤 간단한 것 같고, 단번에 답이 보이는데, 생각을 코드로 옮기려면 어디서부터 시작해야 할지 모르겠습니다.

해결 방법

이 문제에 대한 한 가지 해결책은 역추적 방법(바이두 백과사전)의 정의를 살펴보겠습니다.

역추적 방법(탐색 및 역추적 방법)은 목표를 달성하기 위해 최적화 조건에 따라 앞으로 검색하는 휴리스틱 방법이라고도 하는 최적화 검색 방법입니다. 그러나 탐색의 특정 단계에 도달하여 원래 선택이 최적이 아니거나 목표를 달성할 수 없다는 것을 알게 되면 한 걸음 물러서서 다른 선택을 하게 됩니다. 이것이 작동하지 않을 때 다시 시도하는 것입니다. 역추적 방법이며, 역추적 조건을 만족하는 특정 상태의 지점을 "룩백 포인트"라고 합니다.

내 생각:

• 위의 미로를 조정하세요. 왼쪽 위 모서리는 (0,0), 오른쪽 아래 모서리는 (3,3), 기타 점 좌표계에 흩어져 있는
  
• (0,0)부터 시작
  
• 주어진 좌표점에서 시작하여 오른쪽으로 먼저 검색하고 1이면 계속 , 0 입니다. 아래쪽으로 검색하면 검색 전 검색한 좌표를 기록해 둡니다
  
• . 좌표가 (3,3)과 같을 때 역추적 지점입니다.
  
선을 넘지 않는 한 세 번째 단계를 반복하세요.

내 PHP 구현을 보세요:

<code><?php
$nums = [
    [1,1,1,1,1,1],
    [0,1,0,1,0,1],
    [0,1,0,1,0,1],
    [0,1,1,1,1,1]
];
function getRet($data, $x, $y, &$result=[], $record)
{
    $snapshort = [];
    $xL = count($data) - 1;
    $yL = count($data[0]) - 1;

    if($x > $xL || $y > $yL) {
        //跑到迷宫不存在的空间了，这种事情绝对不能发生
        return;
    }

    if($data[$x][$y] == "0") {
        //是0的话停止继续前进，退回上一状态
        return;
    } elseif($data[$x][$y] == "1") {
        //是1的话，记录最新的坐标到当前已找到的路径中，继续向前搜索
        //如果到达出口，记录答案并回溯
        $snapshort = array_merge($record, [[$x, $y]]);
        if($x == $xL && $y == $yL) {
            $result[] = array_merge($record, [[$x, $y]]);
            return;
        }
    } else {
        return;
    }       

    //向有搜索
    //这里的$snapshort保存当前搜索位置的状态，等到下次回溯到这里的时候会用到
    getRet($data, $x, ++$y, $result, $snapshort);

    //向下搜索
    getRet($data, ++$x, --$y, $result, $snapshort);
}


//看个例子    
$result = [];
getRet($nums, 0, 0, $result, []);

foreach ($result as $pos) {
    foreach ($pos as $xy) {
        echo "({$xy[0]},{$xy[1]}) => ";
    }
    echo "end\n";
}

//输出结果
(0,0)=>(0,1)=>(0,2)=>(0,3)=>(0,4)=>(0,5)=>(1,5)=>(2,5)=>(3,5)=>end
(0,0)=>(0,1)=>(0,2)=>(0,3)=>(1,3)=>(2,3)=>(3,3)=>(3,4)=>(3,5)=>end
(0,0)=>(0,1)=>(1,1)=>(2,1)=>(3,1)=>(3,2)=>(3,3)=>(3,4)=>(3,5)=>end</code>

위 내용은 미로 문제를 해결하기 위한 역추적 방법을 관련 내용을 포함하여 소개하고 있으며, PHP 튜토리얼에 관심이 있는 친구들에게 도움이 되기를 바랍니다.