PHP实现迷宫最短路径查找（DFS）

布满荆棘的人生 2022-05-17 11:50 122阅读 0赞

条件：

a. 一个M\*N的二维的迷宫，用一个二维数组Matrix表示

b. 无法到达的地方标记为1，可以到达的地方标记为0

c. 从任何一个位置Matrix\[i\]\[j\]，每次只能移动到四个位置:Matrix\[i+1\]\[j\],Matrix\[i-1\]\[j\],Matrix\[i\]\[j+1\],Matrix\[i\]\[j-1\]

d. 起始位置为任意

要求：实现算法，找到从起点到出口的一条最短路径；

代码如下，可直接运行

<?php
    /**
     * Created by PhpStorm.
     * User: KeenSting
     * Date: 2018/8/10
     * Time: 下午6:19
     * File Description: DFS迷宫出路检测
     */
    class KeenSting{
    
        public function run()
        {
            $this->findWayOut(10,10);
        }
    
    
        private function findWayOut($w,$h)
        {
    //        list($map,$mark) = $this->generateMap($w,$h);
            $map = $mark = [
                [1,0,1,1,1,0,1,1,0,1],
                [1,0,1,1,1,0,0,1,0,1],
                [1,0,1,0,0,1,0,1,0,1],
                [0,0,0,1,0,0,0,1,0,1],
                [1,1,0,1,0,0,1,1,0,0],
                [1,1,0,0,0,0,0,0,0,1],
                [1,1,0,1,1,0,1,1,0,1],
                [1,0,0,1,1,0,0,1,0,1],
                [0,0,1,1,1,1,0,1,0,1],
                [1,1,1,1,1,0,0,1,0,1],
            ];
            $queue = [];
    //        $s_x = random_int(3,$w-3);
    //        $s_y = random_int(3,$h-3);
            $s_x = 5;
            $s_y = 7;
            while ($map[$s_x][$s_y]==1)
            {
                $s_y+=1;
                if($s_y >=$h)
                    exit('over flow');
            }
            echo 'star pos :（',$s_x,'，'.$s_y.')'.PHP_EOL;
            print_r($this->showMap($map));
    
            $mark[$s_x][$s_y] = 'x';//标记路线
            array_push($queue,[$s_x,$s_y]);//初始化处理队列
            //深度优先
    //        $this->DFS($w,$h,$map,$queue,$mark);
            $this->DFS1($w,$h,$map,$queue,$mark);
    //        $min = 9999;
    //        $this->DFS2($w,$h,$map,$queue,$mark,$min);
    //        echo 'min path : '.$min.PHP_EOL;
    
    
        }
    
        /**显示矩阵地图
         * @param $map
         * @return array
         */
        private function showMap($map)
        {
            $data =[];
            foreach ($map as $row)
            {
                $line = '';
                foreach ($row as $v)
                    $line .=$v.' ';
                array_push($data,$line);
            }
    
            return $data;
        }
    
        /**在地图中显示路径
         * @param $queue
         * @param $map
         * @return array
         */
        private function drawWay($queue,$map)
        {
            foreach ($queue as $p)
            {
                $map[$p[0]][$p[1]] = 'x';
            }
    
            return $this->showMap($map);
        }
    
    
        /**随机生成地图
         * @param $w
         * @param $h
         * @return array
         */
        private function generateMap($w,$h)
        {
            $map = [];
            for ($i=0;$i<$w;$i++)
            {
                $row = [];
                for ($j=0;$j<$h;$j++)
                {
                    $p = random_int(0,10);
                    $px = $p>5?1:0;
    
                    array_push($row,$px);
                }
                array_push($map,$row);
            }
            return [$map,$map];
        }
    
    
        /**
         * 深度优先 找出一条路径
         * @param $w
         * @param $h
         * @param $map
         * @param $queue
         * @param $marks
         */
        private function DFS($w,$h,&$map,&$queue,&$marks)
        {
    
            $size = count($queue);
            if($size==0) {
                echo 'no way out!'.PHP_EOL;
                return;
            }
            $x = $queue[$size-1][0];
            $y = $queue[$size-1][1];
            //上边 没溢出
            if($x-1>=0)
            {
                if(!$marks[$x-1][$y])
                    if($map[$x-1][$y]==0) {
                        array_push($queue, [$x - 1, $y]);
                        $marks[$x-1][$y] = 'x';
                        $this->DFS($w,$h,$map,$queue,$marks);
                    }
            }else//溢出 发现出路
            {
                print_r($this->showMap($marks));
                exit;
            }
    
            //右边 没溢出
            if($y+1 <= $h-1)
            {
                if(!$marks[$x][$y+1])
                    if($map[$x][$y+1]==0) {
                        array_push($queue, [$x, $y+1]);
                        $marks[$x][$y+1] = 'x';
                        $this->DFS($w,$h,$map,$queue,$marks);
                    }
            } else//溢出 发现出路
            {
                print_r($this->showMap($marks));
                exit;
            }
    
            //下边 没溢出
            if($x+1<=$w-1)
            {
                if(!$marks[$x+1][$y])
                    if($map[$x+1][$y]==0) {
                        array_push($queue, [$x + 1, $y]);
                        $marks[$x+1][$y] = 'x';
                        $this->DFS($w,$h,$map,$queue,$marks);
                    }
            }else//溢出 发现出路
            {
                print_r($this->showMap($marks));
                exit;
            }
            //左边 没溢出
            if($y-1 >= 0)
            {
                if(!$marks[$x][$y-1])
                    if($map[$x][$y-1]==0) {
                        array_push($queue, [$x, $y-1]);
                        $marks[$x][$y-1] = 'x';
                        $this->DFS($w,$h,$map,$queue,$marks);
                    }
            }
            else//溢出 发现出路
            {
                print_r($this->showMap($marks));
                exit;
            }
    
            array_pop($queue);
            return;
    
        }
    
        /**深度优先 显示所有的路径
         * @param $w
         * @param $h
         * @param $map
         * @param $queue
         * @param $marks
         */
        public function DFS1($w,$h,$map,&$queue,$marks)
        {
            $size = count($queue);
            if($size==0) {
                echo 'no way out!'.PHP_EOL;
                return;
            }
            $x = $queue[$size-1][0];
            $y = $queue[$size-1][1];
            //先检查是否是边缘点 相当于剪枝操作 避免冗余的递归运算
            if(in_array($x,[0,$w-1])) {
                print_r($this->drawWay($queue,$map));
                echo 'path deep :'.$size.PHP_EOL;
                array_pop($queue);
                return;
            }
            if(in_array($y,[0,$h-1])) {
                print_r($this->drawWay($queue,$map));
                $marks[$x][$y] = 0;
                echo 'path deep :'.$size.PHP_EOL;
                array_pop($queue);
                return;
            }
    
            //上
            if(!$marks[$x-1][$y])
            {
                if($map[$x-1][$y]==0)
                {
                    array_push($queue,[$x-1,$y]);
                    $marks[$x-1][$y] = 'x';
                    if(!$this->DFS1($w,$h,$map,$queue,$marks))//回溯后撤回标记
                        $marks[$x-1][$y] = 0;
    
                }
            }
    
            //下
            if(!$marks[$x+1][$y])
            {
                if($map[$x+1][$y]==0)
                {
                    array_push($queue,[$x+1,$y]);
                    $marks[$x+1][$y] = 'x';
                    if(!$this->DFS1($w,$h,$map,$queue,$marks))//回溯后撤回标记
                        $marks[$x+1][$y] = 0;
                }
            }
            //左
            if(!$marks[$x][$y-1])
            {
                if($map[$x][$y-1]==0)
                {
                    array_push($queue,[$x,$y-1]);
                    $marks[$x][$y-1] = 'x';
                    if(!$this->DFS1($w,$h,$map,$queue,$marks))//回溯后撤回标记
                        $marks[$x][$y - 1] = 0;
                }
            }
    
            //右
            if(!$marks[$x][$y+1])
            {
                if($map[$x][$y+1]==0)
                {
                    array_push($queue,[$x,$y+1]);
                    $marks[$x][$y+1] = 'x';
                    if(!$this->DFS1($w,$h,$map,$queue,$marks))//回溯后撤回标记
                        $marks[$x][$y + 1] = 0;
                }
            }
    
            array_pop($queue);
    
        }
    
        /**深度优先 兼职优化 最短路径
         * @param $w
         * @param $h
         * @param $map
         * @param $queue
         * @param $marks
         * @param int $min
         * @return bool
         */
        private function DFS2($w,$h,$map,&$queue,$marks,&$min=99999)
        {
            $size = count($queue);
    //        print_r($queue);
            if($size==0) {
                echo 'no way out!'.PHP_EOL;
                return true;
            }
            if($size > $min) {
                array_pop($queue);//剪枝操作，去除可能的冗余解以及对应的计算，向最优解逼近
                echo '剪枝'.PHP_EOL;
                return false;
    
            }
            $x = $queue[$size-1][0];
            $y = $queue[$size-1][1];
            //先检查是否是边缘点 相当于剪枝操作 避免冗余的递归运算
            if(in_array($x,[0,$w-1])) {
                print_r($this->drawWay($queue,$map));
                echo 'path deep :'.$size.PHP_EOL;
                array_pop($queue);
                if($size<$min) {
                    $min = $size;
                }
                return false;
            }
            if(in_array($y,[0,$h-1])) {
                print_r($this->drawWay($queue,$map));
                $marks[$x][$y] = 0;
                echo 'path deep :'.$size.PHP_EOL;
                array_pop($queue);
                if($size<$min)
                    $min = $size;
                return false;
            }
    
    
            //上
            if(!$marks[$x-1][$y])
            {
                if($map[$x-1][$y]==0)
                {
                    array_push($queue,[$x-1,$y]);
                    $marks[$x-1][$y] = 'x';
                    if(!$this->DFS2($w,$h,$map,$queue,$marks,$min))//回溯后撤回标记
                       $marks[$x-1][$y] = 0;
    
                }
            }
    
            //下
            if(!$marks[$x+1][$y])
            {
                if($map[$x+1][$y]==0)
                {
                    array_push($queue,[$x+1,$y]);
                    $marks[$x+1][$y] = 'x';
                    if(!$this->DFS2($w,$h,$map,$queue,$marks,$min))//回溯后撤回标记
                       $marks[$x+1][$y] = 0;
                }
            }
            //左
            if(!$marks[$x][$y-1])
            {
                if($map[$x][$y-1]==0)
                {
                    array_push($queue,[$x,$y-1]);
                    $marks[$x][$y-1] = 'x';
                    if(!$this->DFS2($w,$h,$map,$queue,$marks,$min))//回溯后撤回标记
                        $marks[$x][$y - 1] = 0;
                }
            }
    
            //右
            if(!$marks[$x][$y+1])
            {
                if($map[$x][$y+1]==0)
                {
                    array_push($queue,[$x,$y+1]);
                    $marks[$x][$y+1] = 'x';
                    if(!$this->DFS2($w,$h,$map,$queue,$marks,$min))//回溯后撤回标记
                        $marks[$x][$y + 1] = 0;
                }
            }
    
            array_pop($queue);
            echo '该节点四周无路可走---（'.$x.','.$y.'），回溯上个节点'.PHP_EOL;
            return false;
    
    
    
        }
    }
    
    $a = new KeenSting();
    $a->run();

写了三个渐进的DFS

1 DFS

$this->DFS($w,$h,$map,$queue,$mark);

注释掉其他方法，DFS（）输出一个到达出口的路径，在数组中用‘X’标识出

start pos :（5，7)
    Array
    (
        [0] => 1 0 1 1 1 0 1 1 0 1 
        [1] => 1 0 1 1 1 0 0 1 0 1 
        [2] => 1 0 1 0 0 1 0 1 0 1 
        [3] => 0 0 0 1 0 0 0 1 0 1 
        [4] => 1 1 0 1 0 0 1 1 0 0 
        [5] => 1 1 0 0 0 0 0 0 0 1 
        [6] => 1 1 0 1 1 0 1 1 0 1 
        [7] => 1 0 0 1 1 0 0 1 0 1 
        [8] => 0 0 1 1 1 1 0 1 0 1 
        [9] => 1 1 1 1 1 0 0 1 0 1 
    )
    Array
    (
        [0] => 1 0 1 1 1 0 1 1 x 1 
        [1] => 1 0 1 1 1 0 0 1 x 1 
        [2] => 1 0 1 0 0 1 0 1 x 1 
        [3] => 0 0 0 1 0 0 0 1 x 1 
        [4] => 1 1 0 1 0 0 1 1 x 0 
        [5] => 1 1 0 0 0 0 0 x x 1 
        [6] => 1 1 0 1 1 0 1 1 0 1 
        [7] => 1 0 0 1 1 0 0 1 0 1 
        [8] => 0 0 1 1 1 1 0 1 0 1 
        [9] => 1 1 1 1 1 0 0 1 0 1 
    )

2 DFS1

$this->DFS1($w,$h,$map,$queue,$mark);

该方法将所有的可能路径都遍历一遍并显示出来，输出结果太长了，不贴上来了。对边缘的点做了剪枝处理，减少了冗余检索

3 DFS2

$min = 9999;
    $this->DFS2($w,$h,$map,$queue,$mark,$min);
    echo 'min path : '.$min.PHP_EOL;

该方法进行大面积剪枝，逐步逼近最短路径

start pos :（5，7)
    Array
    (
        [0] => 1 0 1 1 1 0 1 1 0 1 
        [1] => 1 0 1 1 1 0 0 1 0 1 
        [2] => 1 0 1 0 0 1 0 1 0 1 
        [3] => 0 0 0 1 0 0 0 1 0 1 
        [4] => 1 1 0 1 0 0 1 1 0 0 
        [5] => 1 1 0 0 0 0 0 0 0 1 
        [6] => 1 1 0 1 1 0 1 1 0 1 
        [7] => 1 0 0 1 1 0 0 1 0 1 
        [8] => 0 0 1 1 1 1 0 1 0 1 
        [9] => 1 1 1 1 1 0 0 1 0 1 
    )
    该节点四周无路可走---（2,3），回溯上个节点
    该节点四周无路可走---（2,4），回溯上个节点
    Array
    (
        [0] => 1 x 1 1 1 0 1 1 0 1 
        [1] => 1 x 1 1 1 0 0 1 0 1 
        [2] => 1 x 1 0 0 1 0 1 0 1 
        [3] => 0 x x 1 x x 0 1 0 1 
        [4] => 1 1 x 1 x x 1 1 0 0 
        [5] => 1 1 x x x x x x 0 1 
        [6] => 1 1 0 1 1 0 1 1 0 1 
        [7] => 1 0 0 1 1 0 0 1 0 1 
        [8] => 0 0 1 1 1 1 0 1 0 1 
        [9] => 1 1 1 1 1 0 0 1 0 1 
    )
    path deep :16
    该节点四周无路可走---（1,1），回溯上个节点
    该节点四周无路可走---（2,1），回溯上个节点
    Array
    (
        [0] => 1 0 1 1 1 0 1 1 0 1 
        [1] => 1 0 1 1 1 0 0 1 0 1 
        [2] => 1 0 1 0 0 1 0 1 0 1 
        [3] => x x x 1 x x 0 1 0 1 
        [4] => 1 1 x 1 x x 1 1 0 0 
        [5] => 1 1 x x x x x x 0 1 
        [6] => 1 1 0 1 1 0 1 1 0 1 
        [7] => 1 0 0 1 1 0 0 1 0 1 
        [8] => 0 0 1 1 1 1 0 1 0 1 
        [9] => 1 1 1 1 1 0 0 1 0 1 
    )
    path deep :14
    该节点四周无路可走---（3,1），回溯上个节点
    该节点四周无路可走---（3,2），回溯上个节点
    该节点四周无路可走---（4,2），回溯上个节点
    剪枝
    该节点四周无路可走---（8,1），回溯上个节点
    该节点四周无路可走---（7,1），回溯上个节点
    该节点四周无路可走---（7,2），回溯上个节点
    该节点四周无路可走---（6,2），回溯上个节点
    该节点四周无路可走---（5,2），回溯上个节点
    该节点四周无路可走---（5,3），回溯上个节点
    该节点四周无路可走---（5,4），回溯上个节点
    该节点四周无路可走---（4,4），回溯上个节点
    该节点四周无路可走---（3,4），回溯上个节点
    Array
    (
        [0] => 1 0 1 1 1 x 1 1 0 1 
        [1] => 1 0 1 1 1 x x 1 0 1 
        [2] => 1 0 1 0 0 1 x 1 0 1 
        [3] => 0 0 0 1 0 x x 1 0 1 
        [4] => 1 1 0 1 0 x 1 1 0 0 
        [5] => 1 1 0 0 0 x x x 0 1 
        [6] => 1 1 0 1 1 0 1 1 0 1 
        [7] => 1 0 0 1 1 0 0 1 0 1 
        [8] => 0 0 1 1 1 1 0 1 0 1 
        [9] => 1 1 1 1 1 0 0 1 0 1 
    )
    path deep :10
    该节点四周无路可走---（1,5），回溯上个节点
    该节点四周无路可走---（1,6），回溯上个节点
    该节点四周无路可走---（2,6），回溯上个节点
    该节点四周无路可走---（3,6），回溯上个节点
    该节点四周无路可走---（3,5），回溯上个节点
    该节点四周无路可走---（2,3），回溯上个节点
    该节点四周无路可走---（2,4），回溯上个节点
    剪枝
    该节点四周无路可走---（1,6），回溯上个节点
    该节点四周无路可走---（2,6），回溯上个节点
    该节点四周无路可走---（3,6），回溯上个节点
    该节点四周无路可走---（3,5），回溯上个节点
    该节点四周无路可走---（3,4），回溯上个节点
    剪枝
    该节点四周无路可走---（3,2），回溯上个节点
    该节点四周无路可走---（4,2），回溯上个节点
    剪枝
    该节点四周无路可走---（7,2），回溯上个节点
    该节点四周无路可走---（6,2），回溯上个节点
    该节点四周无路可走---（5,2），回溯上个节点
    该节点四周无路可走---（5,3），回溯上个节点
    该节点四周无路可走---（5,4），回溯上个节点
    该节点四周无路可走---（4,4），回溯上个节点
    该节点四周无路可走---（4,5），回溯上个节点
    Array
    (
        [0] => 1 0 1 1 1 0 1 1 0 1 
        [1] => 1 0 1 1 1 0 0 1 0 1 
        [2] => 1 0 1 0 0 1 0 1 0 1 
        [3] => 0 0 0 1 0 0 0 1 0 1 
        [4] => 1 1 0 1 0 0 1 1 0 0 
        [5] => 1 1 0 0 0 x x x 0 1 
        [6] => 1 1 0 1 1 x 1 1 0 1 
        [7] => 1 0 0 1 1 x x 1 0 1 
        [8] => 0 0 1 1 1 1 x 1 0 1 
        [9] => 1 1 1 1 1 0 x 1 0 1 
    )
    path deep :8
    该节点四周无路可走---（8,6），回溯上个节点
    该节点四周无路可走---（7,6），回溯上个节点
    该节点四周无路可走---（7,5），回溯上个节点
    该节点四周无路可走---（6,5），回溯上个节点
    该节点四周无路可走---（2,3），回溯上个节点
    该节点四周无路可走---（2,4），回溯上个节点
    该节点四周无路可走---（4,5），回溯上个节点
    剪枝
    该节点四周无路可走---（3,6），回溯上个节点
    该节点四周无路可走---（3,5），回溯上个节点
    该节点四周无路可走---（3,4），回溯上个节点
    剪枝
    该节点四周无路可走---（3,4），回溯上个节点
    剪枝
    该节点四周无路可走---（3,6），回溯上个节点
    该节点四周无路可走---（3,5），回溯上个节点
    该节点四周无路可走---（4,5），回溯上个节点
    该节点四周无路可走---（4,4），回溯上个节点
    剪枝
    该节点四周无路可走---（3,2），回溯上个节点
    该节点四周无路可走---（4,2），回溯上个节点
    剪枝
    该节点四周无路可走---（7,2），回溯上个节点
    该节点四周无路可走---（6,2），回溯上个节点
    该节点四周无路可走---（5,2），回溯上个节点
    该节点四周无路可走---（5,3），回溯上个节点
    该节点四周无路可走---（5,4），回溯上个节点
    该节点四周无路可走---（5,5），回溯上个节点
    该节点四周无路可走---（5,6），回溯上个节点
    Array
    (
        [0] => 1 0 1 1 1 0 1 1 x 1 
        [1] => 1 0 1 1 1 0 0 1 x 1 
        [2] => 1 0 1 0 0 1 0 1 x 1 
        [3] => 0 0 0 1 0 0 0 1 x 1 
        [4] => 1 1 0 1 0 0 1 1 x 0 
        [5] => 1 1 0 0 0 0 0 x x 1 
        [6] => 1 1 0 1 1 0 1 1 0 1 
        [7] => 1 0 0 1 1 0 0 1 0 1 
        [8] => 0 0 1 1 1 1 0 1 0 1 
        [9] => 1 1 1 1 1 0 0 1 0 1 
    )
    path deep :7
    该节点四周无路可走---（1,8），回溯上个节点
    该节点四周无路可走---（2,8），回溯上个节点
    该节点四周无路可走---（3,8），回溯上个节点
    Array
    (
        [0] => 1 0 1 1 1 0 1 1 0 1 
        [1] => 1 0 1 1 1 0 0 1 0 1 
        [2] => 1 0 1 0 0 1 0 1 0 1 
        [3] => 0 0 0 1 0 0 0 1 0 1 
        [4] => 1 1 0 1 0 0 1 1 x x 
        [5] => 1 1 0 0 0 0 0 x x 1 
        [6] => 1 1 0 1 1 0 1 1 0 1 
        [7] => 1 0 0 1 1 0 0 1 0 1 
        [8] => 0 0 1 1 1 1 0 1 0 1 
        [9] => 1 1 1 1 1 0 0 1 0 1 
    )
    path deep :4
    该节点四周无路可走---（4,8），回溯上个节点
    剪枝
    该节点四周无路可走---（7,8），回溯上个节点
    该节点四周无路可走---（6,8），回溯上个节点
    该节点四周无路可走---（5,8），回溯上个节点
    该节点四周无路可走---（5,7），回溯上个节点
    min path : 4