概要
- 勉強のため深さ優先探索をPythonで書いてみます。
- ごく簡単な迷路のようなもののルート算出を深さ優先探索で対応します。
- 元々デザイン方面の学校卒なので、コンピューターサイエンス方面で知識的に雑な点などはご容赦ください。
深さ優先探索とは？
深さ優先探索とは「とにかく行けるとこまで行ってそれ以上進めなくなったら一歩戻ってそこから探索する」という探索方法。
深さ優先探索と幅優先探索
たとえばグリッド上の迷路で考えてみます。上端のグリッドに迷路の入口があり、下端のグリッドに迷路の出口があるとします。
途中途中に通路の分岐や行き止まりもあるとします。
こういった際に進めるだけ先に進んで（深さ優先）、もし行き止まりで進めなくなったら直前の通路の分岐まで戻ってその分岐を進んで出口を目指すような探索方法です。
英語だとdepth-first search、略してDFSなどと表記されます。
解くべき問題のための迷路を作るスクリプトを書く
まずはグリッド上のランダムな迷路を生成するためのスクリプトを書いていきます。
セルの状態の定義
各グリッドの位置1つ分をセルとして、セルには「入口」「通路」「壁」「出口」という状態があるとします。また、探索で算出されたルートが分かるようにするための状態も保持するようにします。
これらの状態を定数として持っておきます。定数の値は半角の文字で持ち、グリッド表示の際にこの文字を表示するようにします。
# 入口用の定数値。
CELL_TYPE_START: str = 'S'
# 通路用の定数値。
CELL_TYPE_PASSAGE: str = ' '
# 壁の定数値。
CELL_TYPE_WALL: str = 'W'
# 出口の定数値。
CELL_TYPE_GOAL: str = 'G'
# 算出されたルートのパス用の定数値。
CELL_TYPE_PATH: str = '*'
入口と出口は、ENTRANCEやEXITとすると両方Eで分かりづらいのでSTARTとGOALとしてあります。
通路部分は空文字、通ったパスはアスタリスクの記号を設定するようにしてあります。
迷路のグリッドの位置情報を扱うクラスの定義
迷路のグリッドの位置情報単体を扱うためのクラスを定義しておきます。左上の位置で0からスタートする値で、右下にいくほど1増加する形で行と列の属性が設定されるようにします。
class Location:
def __init__(self, row: int, column: int) -> None:
"""
迷路のグリッドの位置情報単体を扱うクラス。
Parameters
----------
row : int
位置の行番号。0からスタートし、上から下に向かって1ずつ
加算される。
column : int
位置の列番号。0からスタートし、左から右に向かって1ずつ
加算される。
"""
self.row: int = row
self.column: int = column
ランダムな迷路を生成するクラスの定義
インスタンス化する度にランダムな迷路を生成するためのクラスを追加していきます。
from typing import List
import random
...
class Maze:
# 生成する迷路のグリッドの縦の件数。
_ROW_NUM: int = 7
# 生成する迷路のグリッドの横の件数。
_COLUMN_NUM: int = 15
# 生成する壁の比率。1.0に近いほど壁が多くなる。
_WALL_SPARSENESS: float = 0.3
def __init__(self) -> None:
"""
ランダムな迷路のグリッドの生成・制御などを扱うクラス。
Notes
-----
ランダムに各セルタイプが設定されるため、必ずしもスタートから
ゴールに到達できるものができるわけではない点には注意。
"""
self._set_start_and_goal_location()
self._grid: List[List[str]] = []
self._fill_grid_by_passage_cell()
self._set_wall_type_to_cells_randomly()
self._set_start_and_goal_type_to_cell()
def _set_start_and_goal_location(self) -> None:
"""
開始地点（入口）とゴール（出口）の座標の属性を設定する。
"""
self.start_loc: Location = Location(row=0, column=0)
self.goal_loc: Location = Location(
row=self._ROW_NUM - 1,
column=self._COLUMN_NUM - 1)
def _fill_grid_by_passage_cell(self) -> None:
"""
全てのセルに対してセルの追加を行い、通路のセルタイプを設定する。
"""
for row in range(self._ROW_NUM):
row_cells: List[str] = []
for column in range(self._COLUMN_NUM):
row_cells.append(CELL_TYPE_PASSAGE)
self._grid.append(row_cells)
def _set_wall_type_to_cells_randomly(self) -> None:
"""
グリッドの各セルへ、ランダムに壁のセルタイプを設定する。
"""
for row in range(self._ROW_NUM):
for column in range(self._COLUMN_NUM):
probability = random.uniform(0.0, 1.0)
if probability >= self._WALL_SPARSENESS:
continue
self._grid[row][column] = CELL_TYPE_WALL
def _set_start_and_goal_type_to_cell(self) -> None:
"""
開始（入口）とゴール（出口）の位置にそれぞれの
セルタイプを設定する。
"""
self._grid[self.start_loc.row][self.start_loc.column] = \
CELL_TYPE_START
self._grid[self.goal_loc.row][self.goal_loc.column] = \
CELL_TYPE_GOAL
def __str__(self) -> str:
"""
グリッドの各セルのタイプの文字列を取得する。
Returns
-------
grid_str : str
グリッドの各セルのタイプの文字列。
"""
grid_str: str = ''
for row_cells in self._grid:
grid_str += '-' * self._COLUMN_NUM * 2
grid_str += '\n'
for cell_type in row_cells:
grid_str += cell_type
grid_str += '|'
grid_str += '\n'
return grid_str
コンストラクタで順番にグリッドの行列のセル数の定数を定義したり、2次元のリストにセルタイプの文字列を格納する属性を追加したり、ランダムに壁のセルタイプを配置したり、入口と出口の位置をセルに設定したりしています。
__str__メソッドではprint関数などに渡された際に、見やすいように境界の線の文字などを追加するようにしています。
試しにインスタンス化してみて、print関数で出力してみると以下のようなものが出力されます。
if __name__ == '__main__':
maze = Maze()
print(maze)
左上に入口（スタート）のS、右下に出口（ゴール）のGが設定されます。
また、各セルにはランダムに壁（W）が配置されます。空のセルは通路です。
注意点として、単純にランダムに壁を生成しているだけなので、壁の生成具合によっては壁に阻まれてスタートからゴールまでのルートが存在しないケースも発生します（今回は何度か実行すれば問題ないと判断してこのまま進めます）。
ゴールに到達したかの判定用のメソッドの追加
Mazeクラスに、指定の位置がゴールの位置かどうかの判定を行うためのメソッドを追加しておきます。後で探索を実行した際に、ゴールに達しているのかの判定に使います。
def is_goal_loc(self, location: Location) -> bool:
"""
指定された位置がゴールの位置かどうかの真偽値を取得する。
Parameters
----------
location : Location
判定用の位置。
Returns
-------
result : bool
ゴールの位置であればTrueが設定される。
"""
if (location.row == self.goal_loc.row
and location.column == self.goal_loc.column):
return True
return False
移動可能な位置を取得するメソッドの追加
引き続きMazeクラスに、指定された位置を起点に移動可能な位置のリストを取得するメソッドを追加していきます。移動の処理はグリッド内で上下左右の1マスのみ、且つ壁のセルには移動できないようにします。
本当はパラメーターで奥方向を優先するなどの制御を色々入れたりといったところですが長くなりそうなので今回は割愛します（本当はそこが大切な気がしないでもないですが、参考にした本も読んだところでは割愛され気味だったので、別の記事などで機会があれば深堀りしようと思います）。
def get_movable_locations(self, location: Location) -> List[Location]:
"""
指定された位置から、移動が可能な位置のリストを取得する。
Parameters
----------
location : Location
基準となる位置のインスタンス。
Returns
-------
movable_locations : list of Location
移動可能な位置のインスタンスを格納したリスト。
"""
movable_locations: List[Location] = []
# 上に移動可能かどうかの判定処理。
if location.row + 1 < self._ROW_NUM:
is_wall: bool = self._grid[location.row + 1][location.column] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row + 1, column=location.column))
# 下に移動可能かどうかの判定処理。
if location.row - 1 >= 0:
is_wall = self._grid[location.row - 1][location.column] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row - 1, column=location.column))
# 右に移動可能かどうかの判定処理。
if location.column + 1 < self._COLUMN_NUM:
is_wall = self._grid[location.row][location.column + 1] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row, column=location.column + 1))
# 左に移動可能かどうかの判定処理。
if location.column - 1 >= 0:
is_wall = self._grid[location.row][location.column - 1] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row, column=location.column - 1))
return movable_locations
スタックの制御のためのクラスの定義
深さ優先探索では、スタックと呼ばれるデータ構造のものを使っていきます。スタックはLast-In-First-Out（LIFO・後入れ先出し）と呼ばれる挙動をします。つまり後に追加したデータの方が、取り出す際には先に対象になります。
積み上げられている新聞をイメージすると分かりやすいかもしれません。どんどん上に積み重ねて（スタックして）いきますが、それらを手に取る際には上から（後から積み上げた方から）手に取る形になります。
collectionsパッケージ内のPython標準モジュールを使えばスタックの制御を扱えますが、ここでは勉強目的なので自前でクラスを用意していきます。
class Stack:
def __init__(self) -> None:
"""
スタックの制御を扱うためのクラス。
"""
self._container: list = []
@property
def empty(self) -> bool:
"""
スタックの内容が空かどうかの真偽値を取得する。
"""
return not self._container
def push(self, item: Any) -> None:
"""
スタックへ要素を追加する。
Parameters
----------
item : *
追加する要素。
"""
self._container.append(item)
def pop(self) -> Any:
"""
スタック内から要素を取り出す。
Returns
-------
item : *
取り出された要素。最後に追加されたものが対象となる。
"""
item = self._container.pop()
return item
def __repr__(self) -> str:
"""
リスト内容を文字列で返却する。
Returns
-------
output : str
リスト内容を変換した文字列。
"""
return repr(self._container)
読んでいた書籍で出てきて思いましたが、今更ながら__repr__とかreprの制御ってなんのためにあるのだろう？__str__などとの使いわけはどうなのだろう？ということで調べてみました。どうやらreprなどの方はPythonのコードとして使える（コンストラクタを実行するような形）での文字列として出力されるそうです。
str()がJavaのクラスでオーバーライドするtoString()メソッド（C#のToString()メソッド）のイメージです。repr()は引数付きのコンストラクタ（または初期化子）を文字列で返してくれる関数と解釈できます。
Pythonのstr( )とrepr( )の使い分け
少しコードを動かして試してみます。__repr__部分の動作確認としてprint(stack)とインスタンス自体を出力しているのと、popさせた際にLIFOになっていることを確認します。
if __name__ == '__main__':
stack = Stack()
stack.push(100)
stack.push(200)
print(stack)
last_value = stack.pop()
print('last_value:', last_value)
[100, 200]
last_value: 200
移動の位置情報を保持するクラスの追加
移動してきた情報を格納するためのNodeクラスを追加します。該当の位置情報とどのグリッド位置から移動してきたのかをparentという属性名で保持します。
なお、クラスの引数自体にそのクラスの型のアノテーションをしたい場合には利用するPythonのバージョン次第（3.7や3.8では恐らく必要になります）でfrom __future__ import annotationsの記述が必要になります（そうしないとPylanceなどでエラーで引っかかります）。
詳細は少々まだ読めていませんが、PEP 563 -- Postponed Evaluation of Annotationsなどに書かれているそうです。
from __future__ import annotations
from typing import Optional
...
class Node:
def __init__(self, location: Location, parent: Optional[Node]):
"""
迷路の位置や推移の情報などを保持するためのノード単体のデータを
扱うクラス。
Parameters
----------
location : Location
対象の位置情報を扱うインスタンス。
parent : Node or None
移動前の位置情報を扱うノードのインスタンス。探索開始時
などにはNoneとなる。
"""
self.location: Location = location
self.parent: Optional[Node] = parent
スタックではこのNodeクラスのインスタンスを格納して扱っていきます。
深さ優先探索の関数の定義
実際に深さ優先探索のコードを書いていきます。DFSの略名から関数名もdfsとします。
from typing import Callable
from typing import Set
...
def dfs(
initial_loc: Location,
is_goal_loc_method: Callable[[Location], bool],
get_movable_locations_method: Callable[[Location], List[Location]]
) -> Optional[Node]:
"""
深さ優先探索（depth-first search）による、迷路のゴールの
探索を行う。
Parameters
----------
initial_loc : Location
探索の開始位置。
is_goal_loc_method : callable
対象の位置がゴールかどうかを判定するためのメソッド。
get_movable_locations_method : callable
対象の位置から移動可能な位置のリストを取得するための
メソッド。
Returns
-------
goal_node : Node or None
ゴールに達した場合にはその位置のNodeクラスのインスタンスが
設定され、迷路の構造的にもしゴールにたどり着けない場合には
Noneが設定される。
"""
frontier_loc_stack: Stack = Stack()
frontier_loc_stack.push(
item=Node(location=initial_loc, parent=None))
explored_set: Set[Location] = {initial_loc}
while not frontier_loc_stack.empty:
current_node: Node = frontier_loc_stack.pop()
current_location: Location = current_node.location
print('current_location', current_location.row, current_location.column)
if is_goal_loc_method(current_location):
return current_node
movable_locations = get_movable_locations_method(current_location)
for movable_location in movable_locations:
is_explored_loc = _is_explored_loc(
location=movable_location,
explored_set=explored_set)
if is_explored_loc:
continue
explored_set.add(movable_location)
frontier_loc_stack.push(
Node(location=movable_location, parent=current_node))
return None
def _is_explored_loc(
location: Location, explored_set: Set[Location]) -> bool:
"""
既に探索済みの位置かどうかの真偽値を返す。
Parameters
----------
location : Location
チェック対象の位置。
explored_set : set
探索済みの位置を格納したセット。
Returns
-------
result : bool
探索済みの位置であればTrueが設定される。
"""
for explored_location in explored_set:
if (location.row == explored_location.row
and location.column == explored_location.column):
return True
return False
まずは引数説明からですが、initial_locは基本的に入口の位置のインスタンスが指定されます。
is_goal_loc_methodとget_movable_locations_methodに関しては、対象の生成されたMazeクラスのインスタンスが持っている各メソッドが対象となります。
Callableで型アノテーションしておくと、Pylanceなどを使っているとちゃんとそのメソッド（や関数など）で実行箇所で引数の型の説明などが出るようで良いですね。
frontier_loc_stackは探索先となる位置を格納するスタックです。このスタックでLIFOの方式で最後に追加された位置に対して、ゴールかどうかの判定と移動可能な位置のスタックへの追加が実行されます。
explored_setに関しては同じ箇所を複数回探索しないようにするための制御に使われます。frontier_loc_stackのスタックに追加されたものはこちらのSetにも追加され、同じ探索を繰り返さないように制御しています。以下の部分で探索済みの箇所をスキップするようにしています。
is_explored_loc = _is_explored_loc(
location=movable_location,
explored_set=explored_set)
if is_explored_loc:
continue
出口（ゴール）のノードから入口 → 出口のパス情報を取得する処理の追加
dfs関数で出口の位置のノードが（算出できる条件であれば）算出できる形になりました。
ただし出口のノードのインスタンスだけではなく、入口から出口までどのような経路を辿るのかを算出しておきたい（後でセルタイプとしてアスタリスクの表示を反映したい）ので、入口から出口までのパスを取得する関数を追加しておきます。
Nodeクラスは移動元となるparent属性を持っているので、出口のノードさえ参照できればparent属性のノードを辿っていって、最後にそれらのノードのリストを逆順にすれば、入口のノードから出口のノードまでのノードを格納したリスト（探索で得られたパス）を取得することができます。
def get_path_from_goal_node(goal_node: Node) -> List[Location]:
"""
出口のノードから、探索で取得できた入口 → 出口までのパスを
取得する。
Parameters
----------
goal_node : Node
対象の出口（ゴール）のノードのインスタンス。
Returns
-------
path : list of Location
入口から出口までの各位置のインスタンスを格納したリスト。
"""
path: List[Location] = [goal_node.location]
node: Node = goal_node
while node.parent is not None:
node = node.parent
path.append(node.location)
path.reverse()
return path
最終的に入口のノードまで辿れたら、parent属性はNoneになるのでwhileのループを終了しています。
算出したパスを各セルへ反映するためのメソッドの追加
パスの取得処理を追加したので、今度はそのパスの各セルをアスタリスクの表示になるように設定していきます。
入口や壁などと同様にパスはセルタイプの定数としてCELL_TYPE_PATH: str = '*'と定義してあるのでそちらを反映し、迷路の可視化時にアスタリスクで表示されるようにします。
メソッドとしてMazeクラスに追加していきます。
def set_path_type_to_cells(self, path: List[Location]) -> None:
"""
入口と出口までの指定されたパス内に含まれるセルに対して、
パスのセルタイプを設定する。
Parameters
----------
path : list of Location
探索で得られた入口から出口までの各セルの位置情報を
格納したリスト。
"""
for location in path:
self._grid[location.row][location.column] = CELL_TYPE_PATH
# パス内に含まれている入口と出口の部分は、それぞれ元の
# セルタイプを反映する。
self._grid[self.start_loc.row][self.start_loc.column] = \
CELL_TYPE_START
self._grid[self.goal_loc.row][self.goal_loc.column] = \
CELL_TYPE_GOAL
実行してみる
これで準備ができたのでコードを実行してみます。
if __name__ == '__main__':
maze = Maze()
print('-' * 20)
print('生成された迷路 :')
print(maze)
print('-' * 20)
goal_node: Optional[Node] = dfs(
initial_loc=maze.start_loc,
is_goal_loc_method=maze.is_goal_loc,
get_movable_locations_method=maze.get_movable_locations)
if goal_node is None:
print('出口に到達できない迷路です。')
else:
path: List[Location] = get_path_from_goal_node(
goal_node=goal_node)
maze.set_path_type_to_cells(path=path)
print('算出されたパス :')
print(maze)
まずは最初に生成された迷路の内容を出力しています。
続いて深さ優先探索（dfs）を実行しています。
実行結果で返却されるノードは、出口に到達できない迷路の場合はNoneとなるのでNoneかどうかで分岐しています。
もしNone以外が返却されていれば、パスの取得（get_path_from_goal_node）とセルへの探索のパスの反映（set_path_type_to_cells）をしています。
迷路は毎回ランダムに生成されるので出力結果の一例として以下のようになります。
算出されたパス :
------------------------------
S|W| |W|W| | | |W| | |W| | |W|
------------------------------
*|*|W| | | |W|W| |W| |W| | |W|
------------------------------
|*|*|W| |W|W|W| | | | |W| | |
------------------------------
| |*|*|*|*|*|W| | | | | | | |
------------------------------
W| | |W|W|W|*|*|W|W| | |W|W| |
------------------------------
|W| | | | |W|*|*|*|*|*|*|*|W|
------------------------------
|W|W| | | |W|W| | |W| | |*|G|
入口（S）からアスタリスクのセルを辿っていくと出口（G）までちゃんと到達できていることが確認できます。
迷路はランダムなので、例えば以下のように壁（W）に阻まれて出口に到達できないケースも発生します。
生成された迷路 :
------------------------------
S| |W| |W|W| |W| | |W| |W| | |
------------------------------
|W|W| | | | | | |W| | |W| |W|
------------------------------
| | | | | | | |W|W| | | |W|W|
------------------------------
|W| | |W| | |W| | |W| |W|W| |
------------------------------
| |W|W|W|W|W| | | | | |W| |W|
------------------------------
|W|W|W| | | |W| | |W| | | | |
------------------------------
W| |W|W| |W|W| | | | | | |W|G|
--------------------
出口に到達できない迷路です。
コード全体
from __future__ import annotations
from typing import Optional
from typing import List
import random
from typing import Any
from typing import Callable
from typing import Set
# 入口用の定数値。
CELL_TYPE_START: str = 'S'
# 通路用の定数値。
CELL_TYPE_PASSAGE: str = ' '
# 壁の定数値。
CELL_TYPE_WALL: str = 'W'
# 出口の定数値。
CELL_TYPE_GOAL: str = 'G'
# 算出されたルートのパス用の定数値。
CELL_TYPE_PATH: str = '*'
class Location:
def __init__(self, row: int, column: int) -> None:
"""
迷路のグリッドの位置情報単体を扱うクラス。
Parameters
----------
row : int
位置の行番号。0からスタートし、上から下に向かって1ずつ
加算される。
column : int
位置の列番号。0からスタートし、左から右に向かって1ずつ
加算される。
"""
self.row: int = row
self.column: int = column
class Maze:
# 生成する迷路のグリッドの縦の件数。
_ROW_NUM: int = 7
# 生成する迷路のグリッドの横の件数。
_COLUMN_NUM: int = 15
# 生成する壁の比率。1.0に近いほど壁が多くなる。
_WALL_SPARSENESS: float = 0.3
def __init__(self) -> None:
"""
ランダムな迷路のグリッドの生成・制御などを扱うクラス。
Notes
-----
ランダムに各セルタイプが設定されるため、必ずしもスタートから
ゴールに到達できるものができるわけではない点には注意。
"""
self._set_start_and_goal_location()
self._grid: List[List[str]] = []
self._fill_grid_by_passage_cell()
self._set_wall_type_to_cells_randomly()
self._set_start_and_goal_type_to_cell()
def _set_start_and_goal_location(self) -> None:
"""
開始地点（入口）とゴール（出口）の座標の属性を設定する。
"""
self.start_loc: Location = Location(row=0, column=0)
self.goal_loc: Location = Location(
row=self._ROW_NUM - 1,
column=self._COLUMN_NUM - 1)
def _fill_grid_by_passage_cell(self) -> None:
"""
全てのセルに対してセルの追加を行い、通路のセルタイプを設定する。
"""
for row in range(self._ROW_NUM):
row_cells: List[str] = []
for column in range(self._COLUMN_NUM):
row_cells.append(CELL_TYPE_PASSAGE)
self._grid.append(row_cells)
def _set_wall_type_to_cells_randomly(self) -> None:
"""
グリッドの各セルへ、ランダムに壁のセルタイプを設定する。
"""
for row in range(self._ROW_NUM):
for column in range(self._COLUMN_NUM):
probability = random.uniform(0.0, 1.0)
if probability >= self._WALL_SPARSENESS:
continue
self._grid[row][column] = CELL_TYPE_WALL
def _set_start_and_goal_type_to_cell(self) -> None:
"""
開始（入口）とゴール（出口）の位置にそれぞれの
セルタイプを設定する。
"""
self._grid[self.start_loc.row][self.start_loc.column] = \
CELL_TYPE_START
self._grid[self.goal_loc.row][self.goal_loc.column] = \
CELL_TYPE_GOAL
def is_goal_loc(self, location: Location) -> bool:
"""
指定された位置がゴールの位置かどうかの真偽値を取得する。
Parameters
----------
location : Location
判定用の位置。
Returns
-------
result : bool
ゴールの位置であればTrueが設定される。
"""
if (location.row == self.goal_loc.row
and location.column == self.goal_loc.column):
return True
return False
def get_movable_locations(self, location: Location) -> List[Location]:
"""
指定された位置から、移動が可能な位置のリストを取得する。
Parameters
----------
location : Location
基準となる位置のインスタンス。
Returns
-------
movable_locations : list of Location
移動可能な位置のインスタンスを格納したリスト。
"""
movable_locations: List[Location] = []
# 上に移動可能かどうかの判定処理。
if location.row + 1 < self._ROW_NUM:
is_wall: bool = self._grid[location.row + 1][location.column] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row + 1, column=location.column))
# 下に移動可能かどうかの判定処理。
if location.row - 1 >= 0:
is_wall = self._grid[location.row - 1][location.column] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row - 1, column=location.column))
# 右に移動可能かどうかの判定処理。
if location.column + 1 < self._COLUMN_NUM:
is_wall = self._grid[location.row][location.column + 1] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row, column=location.column + 1))
# 左に移動可能かどうかの判定処理。
if location.column - 1 >= 0:
is_wall = self._grid[location.row][location.column - 1] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row, column=location.column - 1))
return movable_locations
def set_path_type_to_cells(self, path: List[Location]) -> None:
"""
入口と出口までの指定されたパス内に含まれるセルに対して、
パスのセルタイプを設定する。
Parameters
----------
path : list of Location
探索で得られた入口から出口までの各セルの位置情報を
格納したリスト。
"""
for location in path:
self._grid[location.row][location.column] = CELL_TYPE_PATH
# パス内に含まれている入口と出口の部分は、それぞれ元の
# セルタイプを反映する。
self._grid[self.start_loc.row][self.start_loc.column] = \
CELL_TYPE_START
self._grid[self.goal_loc.row][self.goal_loc.column] = \
CELL_TYPE_GOAL
def __str__(self) -> str:
"""
グリッドの各セルのタイプの文字列を取得する。
Returns
-------
grid_str : str
グリッドの各セルのタイプの文字列。
"""
grid_str: str = ''
for row_cells in self._grid:
grid_str += '-' * self._COLUMN_NUM * 2
grid_str += '\n'
for cell_type in row_cells:
grid_str += cell_type
grid_str += '|'
grid_str += '\n'
return grid_str
class Stack:
def __init__(self) -> None:
"""
スタックの制御を扱うためのクラス。
"""
self._container: list = []
@property
def empty(self) -> bool:
"""
スタックの内容が空かどうかの真偽値を取得する。
"""
return not self._container
def push(self, item: Any) -> None:
"""
スタックへ要素を追加する。
Parameters
----------
item : *
追加する要素。
"""
self._container.append(item)
def pop(self) -> Any:
"""
スタック内から要素を取り出す。
Returns
-------
item : *
取り出された要素。最後に追加されたものが対象となる。
"""
item = self._container.pop()
return item
def __repr__(self) -> str:
"""
リスト内容を文字列で返却する。
Returns
-------
output : str
リスト内容を変換した文字列。
"""
return repr(self._container)
class Node:
def __init__(self, location: Location, parent: Optional[Node]):
"""
迷路の位置や推移の情報などを保持するためのノード単体のデータを
扱うクラス。
Parameters
----------
location : Location
対象の位置情報を扱うインスタンス。
parent : Node or None
移動前の位置情報を扱うノードのインスタンス。探索開始時
などにはNoneとなる。
"""
self.location: Location = location
self.parent: Optional[Node] = parent
def dfs(
initial_loc: Location,
is_goal_loc_method: Callable[[Location], bool],
get_movable_locations_method: Callable[[Location], List[Location]]
) -> Optional[Node]:
"""
深さ優先探索（depth-first search）による、迷路のゴールの
探索を行う。
Parameters
----------
initial_loc : Location
探索の開始位置。
is_goal_loc_method : callable
対象の位置がゴールかどうかを判定するためのメソッド。
get_movable_locations_method : callable
対象の位置から移動可能な位置のリストを取得するための
メソッド。
Returns
-------
goal_node : Node or None
ゴールに達した場合にはその位置のNodeクラスのインスタンスが
設定され、迷路の構造的にもしゴールにたどり着けない場合には
Noneが設定される。
"""
frontier_loc_stack: Stack = Stack()
frontier_loc_stack.push(
item=Node(location=initial_loc, parent=None))
explored_set: Set[Location] = {initial_loc}
while not frontier_loc_stack.empty:
current_node: Node = frontier_loc_stack.pop()
current_location: Location = current_node.location
if is_goal_loc_method(current_location):
return current_node
movable_locations = get_movable_locations_method(current_location)
for movable_location in movable_locations:
is_explored_loc = _is_explored_loc(
location=movable_location,
explored_set=explored_set)
if is_explored_loc:
continue
explored_set.add(movable_location)
frontier_loc_stack.push(
Node(location=movable_location, parent=current_node))
return None
def _is_explored_loc(
location: Location, explored_set: Set[Location]) -> bool:
"""
既に探索済みの位置かどうかの真偽値を返す。
Parameters
----------
location : Location
チェック対象の位置。
explored_set : set
探索済みの位置を格納したセット。
Returns
-------
result : bool
探索済みの位置であればTrueが設定される。
"""
for explored_location in explored_set:
if (location.row == explored_location.row
and location.column == explored_location.column):
return True
return False
def get_path_from_goal_node(goal_node: Node) -> List[Location]:
"""
出口のノードから、探索で取得できた入口 → 出口までのパスを
取得する。
Parameters
----------
goal_node : Node
対象の出口（ゴール）のノードのインスタンス。
Returns
-------
path : list of Location
入口から出口までの各位置のインスタンスを格納したリスト。
"""
path: List[Location] = [goal_node.location]
node: Node = goal_node
while node.parent is not None:
node = node.parent
path.append(node.location)
path.reverse()
return path
if __name__ == '__main__':
maze = Maze()
print('-' * 20)
print('生成された迷路 :')
print(maze)
print('-' * 20)
goal_node: Optional[Node] = dfs(
initial_loc=maze.start_loc,
is_goal_loc_method=maze.is_goal_loc,
get_movable_locations_method=maze.get_movable_locations)
if goal_node is None:
print('出口に到達できない迷路です。')
else:
path: List[Location] = get_path_from_goal_node(
goal_node=goal_node)
maze.set_path_type_to_cells(path=path)
print('算出されたパス :')
print(maze)