07-求解迷宫问题

2.2　求解迷宫问题

寻找穿过迷宫的路径类似于计算机科学中的很多常见搜索问题，那么不妨直观地用查找迷宫路径来演示广度优先搜索、深度优先搜索和A*算法吧。

此处的迷宫将是由 Cell 组成的二维网格。 Cell 是一个包含 str 值的枚举，其中 " " 表示空白单元格， "X" 表示路障单元格。还有其他一些在打印输出迷宫时供演示用的单元格。具体代码如代码清单2-10所示。

代码清单2-10　maze.py

from enum import Enum
from typing import List, NamedTuple, Callable, Optional
import random
from math import sqrt
from generic_search import dfs, bfs, node_to_path, astar, Node
class Cell(str, Enum):
    EMPTY = " "
    BLOCKED = "X"
    START = "S"
    GOAL = "G"
    PATH = "*"

这里再次用到了很多导入操作。注意，最后一个导入（ from generic_search ）有几个还未定义的标识符，此处是为了方便才包含进来的，但在用到之前可以先把它们注释掉。

还需要有一种表示迷宫中各个位置的方法，只要用 NamedTuple 即可实现，其属性表示当前位置的行和列。具体代码如代码清单2-11所示。

代码清单2-11　maze.py（续）

class MazeLocation(NamedTuple):
    row: int
    column: int