Explication détaillée de PHP utilisant la méthode de retour en arrière pour résoudre le problème du labyrinthe

Cet article présente principalement la méthode PHP pour résoudre le problème du labyrinthe basée sur la méthode du backtracking. Il analyse en détail le principe de la méthode du backtracking, les étapes de mise en œuvre et les compétences opérationnelles associées pour résoudre le problème du labyrinthe sous forme d'exemples. . Les amis dans le besoin peuvent s'y référer

L'exemple de cet article décrit comment PHP implémente la méthode de résolution des problèmes de labyrinthe basée sur la méthode du backtracking. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Introduction

J'ai récemment lu quelques questions d'algorithme sur leetcode, et certaines certains d'entre eux semblaient très simples. Il y a des choses très couramment utilisées, mais je n'arrive pas à comprendre comment les résoudre à la fois, comme : implémenter la fonction sqrt et trouver la disposition du tableau. Si vous n'êtes pas doué en mathématiques avancées, ces problèmes apparemment simples seront difficiles à résoudre la première fois que vous les rencontrerez. Bien sûr, ce dont nous allons parler aujourd'hui est un tel problème, comment résoudre toutes les solutions du problème. labyrinthe.Comment résoudre ce problème Lorsqu'il s'agit de l'idée du retour en arrière, si vous ne comprenez pas cette idée, de nombreux problèmes légèrement plus compliqués seront difficiles à résoudre.

Description du problème

J'ai rencontré ce problème alors que je me promenais, je ne me souviens pas exactement où il se trouve.

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

Le sommet est un labyrinthe, le coin supérieur gauche est l'entrée , et le coin inférieur droit est A la sortie, Xiaomeng (oui, vous avez bien lu, c'est Xiao Ming qui a fait pousser de l'herbe) entre par l'entrée et s'échappe par la sortie (si vous ne pouvez pas vous échapper pendant une heure, vous le ferez être mangé par le monstre X), où 1 signifie qu'il est praticable et 0 signifie qu'il n'y a aucun moyen de passer, vous ne pouvez donc aller que dans deux directions : à droite et en bas. Trouvez toutes les voies d'évacuation possibles pour Xiaomeng.

Cette question semble assez simple, et vous pouvez voir la réponse immédiatement, mais je ne sais pas par où commencer pour traduire des pensées en code.

Comment résoudre

Une solution à ce problème est la méthode de backtracking. Examinons d'abord la définition de la méthode de backtracking (Baidu Encyclopedia). ):

La méthode de backtracking (méthode d'exploration et de backtracking) est une méthode de recherche d'optimisation, également connue sous le nom de méthode heuristique, qui recherche en avant en fonction des conditions d'optimisation pour atteindre l'objectif. Mais lorsque vous atteignez une certaine étape de l'exploration et constatez que le choix initial n'est pas optimal ou ne peut pas atteindre l'objectif, vous prendrez du recul et ferez un autre choix. Cette technique consistant à revenir en arrière et à réessayer quand cela ne fonctionne pas. est la méthode de retour en arrière, et le point dans un certain état qui satisfait aux conditions de retour en arrière est appelé « point de retour en arrière ».

Mon idée :

1 Coordonnez le labyrinthe ci-dessus, le coin supérieur gauche est (0,0), le coin inférieur droit est (3,3), D'autres points sont dispersés dans le système de coordonnées
2. Commencez à partir de (0,0)
3. En partant du point de coordonnées donné, recherchez d'abord vers la droite. Si c'est 1, continuez, si c'est 0, recherche vers le bas. Recherche Enregistrez les coordonnées actuellement recherchées
4 Lorsque les coordonnées sont égales à (3,3), c'est un point de retour en arrière,
5 est également renvoyé tant que ce n'est pas le cas. franchissez la frontière, répétez la troisième étape

Regardez mon implémentation 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";
}

Résultats de sortie

(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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!