経路探索 深さ優先探索 : PHPで実装

Tweet

Pocket

深さ優先探索で迷路の探索をするプログラムです。
スタート(S)、ゴール(G)、通行可(0)、通行不可(1)の2次元配列あるときスタートからゴールへの経路の存在に使います。
深さ探索はスタックを使い実装します。また再帰で簡潔に実装することができます。

4 6
0,0,S,0,1,0
0,G,1,0,0,0
1,0,0,1,0,0
0,0,0,0,0,1

スタック版

<?php
/**
 * 深さ優先 経路探索 スタック版
 */
Class DFSRouteStack
{
    /** @var integer $n 行数 */
    private $n;
    /** @var integer $m 列数 */
    private $m;
    /** @var array $map nxm行列 0 移動可能、 1 移動不可、スタート S、ゴール G */
    private $map;
    /** @var integer[] $stack */
    private $stack;
    /** @var boolean[] $visited 訪問済フラグ */
    private $visited = [];

    /**
     * DFSRouteStack constructor.
     *
     * @param integer $n   行数
     * @param integer $m   列数
     * @param array   $map データ行列
     */
    public function __construct($n, $m, $map)
    {
        $this->n   = $n;
        $this->m   = $m;
        $this->map = $map;
    }

    /**
     * 訪問済みフラグ初期化
     */
    private function initVisited()
    {
        for ($i = 0; $i < $this->n; $i++) {
            for ($j = 0; $j < $this->m; $j++) {
                $this->visited[$i][$j] = false;
            }
        }
    }

    /**
     * 探索
     *
     * @return boolean
     */
    private function search()
    {
        while (!empty($this->stack)) {
            $current = end($this->stack);
            $c_i     = $current[0];
            $c_j     = $current[1];
            if ($this->map[$c_i][$c_j] === 'G') {
                return true;
            }
            $point = $this->next($current);
            if ($point === false) {
                array_pop($this->stack);
            } else {
                array_push($this->stack, $point);
                $i                     = $point[0];
                $j                     = $point[1];
                $this->visited[$i][$j] = true;
            }
        }

        return false;
    }

    /**
     * 移動先座標取得
     *
     * @param integer[] $current 現在探索位置
     * @return integer[]|boolean 次に移動する座標
     */
    private function next($current)
    {
        $i = $current[0];
        $j = $current[1];
        // up, right, down, left
        if (isset($this->map[$i + 1][$j]) && $this->map[$i + 1][$j] != 1 && $this->visited[$i + 1][$j] === false) {

            return [$i + 1, $j];
        }
        if (isset($this->map[$i][$j + 1]) && $this->map[$i][$j + 1] != 1 && $this->visited[$i][$j + 1] === false) {

            return [$i, $j + 1];
        }
        if (isset($this->map[$i - 1][$j]) && $this->map[$i - 1][$j] != 1 && $this->visited[$i - 1][$j] === false) {
            return [$i - 1, $j];
        }
        if (isset($this->map[$i][$j - 1]) && $this->map[$i][$j - 1] != 1 && $this->visited[$i][$j - 1] === false) {

            return [$i, $j - 1];
        }

        return false;
    }

    /**
     * 経路取得
     *
     * @param integer $i 行
     * @param integer $j 列
     * @return integer[]|boolean
     */
    public function getPath($i, $j)
    {
        $this->stack = [];
        $this->initVisited();
        $this->visited[$i][$j] = true;
        $this->stack[0]        = [$i, $j];
        $result                = $this->search();
        if ($result !== false) {
            return $this->stack;
        } else {
            return false;
        }
    }

    /**
     * 訪問済みフラグ配列取得
     *
     * @param integer $i
     * @param integer $j
     * @return boolean[]|boolean
     */
    public function getVisited($i, $j)
    {
        $this->stack = [];
        $this->initVisited();
        $this->visited[$i][$j] = true;
        $this->stack[0]        = [$i, $j];
        $result                = $this->search();

        if ($result !== false) {
            return $this->visited;
        } else {
            return false;
        }
    }
}

再帰版

<?php
/**
 * 深さ優先 経路探索 再帰版
 */
Class DFSRouteRecursion
{
    /** @var integer $n 行数 */
    private $n;
    /** @var integer $m 列数 */
    private $m;
    /** @var array $map nxm行列 0 移動可能、 1 移動不可、スタート S、ゴール G */
    private $map;
    /** @var boolean[] $visited 訪問済フラグ */
    private $visited = [];
    /** @var bool $finished 探索完了フラグ */
    private $finished = false;

    /**
     * DFSRouteRecursion constructor.
     *
     * @param integer $n   行数
     * @param integer $m   列数
     * @param array   $map データ行列
     */
    public function __construct($n, $m, $map)
    {
        $this->n   = $n;
        $this->m   = $m;
        $this->map = $map;
    }

    /**
     * 訪問済みフラグ初期化
     */
    private function initVisited()
    {
        for ($i = 0; $i < $this->n; $i++) {
            for ($j = 0; $j < $this->m; $j++) {
                $this->visited[$i][$j] = false;
            }
        }
    }

    /**
     * 探索
     *
     * @param integer $i
     * @param integer $j
     * @return boolean
     */
    private function search($i, $j)
    {
        if ($this->finished) {
            return;
        }
        if (!isset($this->map[$i][$j]) || $this->map[$i][$j] == 1 || $this->visited[$i][$j] === true) {
            return;
        }
        $this->visited[$i][$j] = true;

        if ($this->map[$i][$j] == 'G') {
            $this->finished = true;

            return;
        }

        // up, right, down, left
        $this->search($i + 1, $j);
        $this->search($i, $j + 1);
        $this->search($i - 1, $j);
        $this->search($i, $j - 1);

        if ($this->finished) {
            return true;
        } else {
            return false;
        }
    }

    /**
     * 訪問済みフラグ配列取得
     *
     * @param integer $i
     * @param integer $j
     * @return boolean[]|boolean
     */
    public function getVisited($i, $j)
    {
        $this->initVisited();
        $result = $this->search($i, $j);

        if ($result !== false) {
            return $this->visited;
        } else {
            return false;
        }
    }
}