미로 문제를 해결하기 위해 역추적 방법을 사용하는 PHP에 대한 자세한 설명

이 글에서는 역추적 방식을 기반으로 미로 문제를 해결하기 위한 PHP 방식을 주로 소개하고, 역추적 방식의 원리와 미로 문제 해결을 위한 구현 단계 및 관련 조작 기술을 사례 형식으로 분석합니다. 필요한 경우 이 기사의 예제를 참조하세요

PHP가 역추적 방법을 기반으로 미로 문제를 해결하는 방법을 구현하는 방법을 설명합니다. 참고하실 수 있도록 자세한 내용은 다음과 같습니다.

Introduction

최근에 leetcode에서 몇 가지 알고리즘 질문을 읽었는데 그 중 일부는 매우 간단하고 일반적으로 사용되는 것 같았습니다. 예를 들어, 한 번에 해결하는 방법: sqrt 함수를 구현하여 배열의 배열을 찾습니다. 고급 수학을 잘하지 못한다면 이러한 겉보기에 단순해 보이는 문제는 처음 접할 때 해결하기 어려울 것입니다. 미로. 이 문제를 해결하는 방법 역추적이라는 아이디어에 관해서, 이 아이디어를 이해하지 못하면 조금 더 복잡한 문제를 해결하기 어려울 것입니다.

문제 설명

이 문제는 정말 헤매다가 정확히 어디에 있는지 기억이 나지 않습니다.

1 1 1 1
0 1 0 1
0 1 0 1
0 1 1 1

위는 미로, 왼쪽 위가 입구, 오른쪽 아래가 출구, 샤오멍(예, 당신 읽어봐, 길다 (화를 낸 샤오밍)가 입구로 들어와서 출구로 탈출한다. (1시간 동안 탈출하지 못하면 에게 잡아먹히게 되고, 샤오멍이 탈출할 수 있는 경로를 모두 찾아라) .

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

해결 방법

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

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

내 생각:

1. 위의 미로를 좌표화하세요. 왼쪽 위 모서리는 (0,0), 오른쪽 아래 모서리는 (3,3)이고 다른 점은 좌표계에 흩어져 있습니다. (0,0)부터
3. 주어진 좌표점부터 오른쪽으로 먼저 검색하고, 0이면 검색한 좌표를 기록합니다.
4. 좌표가 (3,3)이 역추적 지점이고 이때
5로 돌아오면 경계를 넘지 않는 한 세 번째 단계를 반복하세요

내 PHP 구현을 보세요:

<?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

위 내용은 미로 문제를 해결하기 위해 역추적 방법을 사용하는 PHP에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!