Detaillierte Erklärung von PHP mit der Backtracking-Methode zur Lösung des Labyrinthproblems

Dieser Artikel stellt hauptsächlich die PHP-Methode zur Lösung des Labyrinthproblems basierend auf der Backtracking-Methode vor. Er analysiert detailliert das Prinzip der Backtracking-Methode, die Implementierungsschritte und die damit verbundenen Bedienfähigkeiten zur Lösung des Labyrinthproblems in Form von Beispielen . Freunde in Not können sich darauf beziehen

Das Beispiel in diesem Artikel beschreibt, wie PHP die Methode zur Lösung von Labyrinthproblemen basierend auf der Backtracking-Methode implementiert. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Einführung

Ich habe kürzlich einige Algorithmusfragen zu Leetcode gelesen, und einige Einige davon sahen sehr einfach aus. Es gibt sehr häufig verwendete Dinge, aber ich kann nicht herausfinden, wie ich sie auf einmal lösen kann, wie zum Beispiel: die Funktion sqrt implementieren und die Anordnung des Arrays finden. Wenn Sie nicht gut in fortgeschrittener Mathematik sind, werden diese scheinbar einfachen Probleme beim ersten Mal schwer zu lösen sein. Natürlich werden wir heute über ein solches Problem sprechen, wie man alle Lösungen dafür löst Labyrinth. So lösen Sie dieses Problem: Wenn Sie die Idee des Zurückverfolgens nicht verstehen, werden viele etwas komplexere Probleme schwer zu lösen sein.

Problembeschreibung

Ich bin auf dieses Problem gestoßen, als ich gerade herumwanderte. Ich kann mich nicht genau erinnern, wo es ist.

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

Oben ist ein Labyrinth, die obere linke Ecke ist der Eingang , und die untere rechte Ecke ist Am Ausgang kommt Xiaomeng (ja, Sie haben es richtig gelesen, es ist Xiao Ming, der Gras angebaut hat) durch den Eingang herein und entkommt durch den Ausgang (wenn Sie eine Stunde lang nicht entkommen können, werden Sie es tun). (vom

Diese Frage scheint recht einfach zu sein, und Sie können die Antwort sofort sehen, aber ich weiß nicht, wo ich anfangen soll, wenn ich Gedanken in Code übertrage.

So lösen Sie

Eine Lösung für dieses Problem ist die Backtracking-Methode (Baidu-Enzyklopädie). ):

Die Backtracking-Methode (Explorations- und Backtracking-Methode) ist eine Optimierungssuchmethode, auch als heuristische Methode bekannt, die gemäß den Optimierungsbedingungen vorwärts sucht, um das Ziel zu erreichen. Aber wenn Sie einen bestimmten Schritt in der Erkundung erreichen und feststellen, dass die ursprüngliche Wahl nicht optimal ist oder das Ziel nicht erreichen kann, werden Sie einen Schritt zurücktreten und eine andere Wahl treffen. Diese Technik des Zurückgehens und erneuten Versuchens funktioniert nicht ist die Backtracking-Methode, und der Punkt in einem bestimmten Zustand, der die Backtracking-Bedingungen erfüllt, wird als „Backtracking-Punkt“ bezeichnet.

Meine Idee:

1. Koordinieren Sie das Labyrinth oben, die obere linke Ecke ist (0,0), die untere rechte Ecke ist (3,3), Andere Punkte sind im Koordinatensystem verstreut
2. Beginnen Sie mit dem angegebenen Koordinatenpunkt, suchen Sie zuerst nach rechts, wenn er 0 ist. Suchen Sie nach unten. Zeichnen Sie die aktuell gesuchten Koordinaten auf
4. Wenn die Koordinaten gleich (3,3) sind, wird zu diesem Zeitpunkt auch
5 zurückgegeben Überschreiten Sie die Grenze und wiederholen Sie den dritten Schritt

Sehen Sie sich meine PHP-Implementierung an:

<?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";
}

Ergebnisse ausgeben

Das obige ist der detaillierte Inhalt vonDetaillierte Erklärung von PHP mit der Backtracking-Methode zur Lösung des Labyrinthproblems. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!