全幅探索アルゴリズム

お題はこれ

プログラマを育てる脳トレパズル 遊んでおぼえるPythonプログラミング&アルゴリズム

相変わらず問題だけ読んで、答えの処理を見ずに書いてみた系。

# 9=壁, 1=goal, 0=道
maze = [
    [0, 0, 0, 9, 9, 0, 9],
    [0, 9, 9, 0, 0, 0, 0],
    [0, 0, 0, 0, 9, 9, 9],
    [9, 0, 9, 0, 9, 0, 1],
    [0, 0, 9, 0, 0, 0, 9],
    [0, 9, 0, 0, 9, 0, 0]
]

で、自分が真っ先に考えたのが再起で全幅探索すること。
こんなのに、機械学習まで持って行っても仕方ないので（汗

現在の位置から、→↓←↑ の順番に見て、移動できるなら移動する。行き止まりに入ったら戻る…を繰り返します。

WALL = 9
ROAD = 0
GOAL = 1

# 9=壁, 1=goal, 0=道
maze = [
    [0, 0, 0, 9, 9, 0, 9],
    [0, 9, 9, 0, 0, 0, 0],
    [0, 0, 0, 0, 9, 9, 9],
    [9, 0, 9, 0, 9, 0, 1],
    [0, 0, 9, 0, 0, 0, 9],
    [0, 9, 0, 0, 9, 0, 0]
]

# 開始地点
startpos = (0, 0)

# ルートスタック
routeQueue = [ startpos ]

# 移動方向ベクトル
moveVectors = [(1, 0), (0, 1), (-1, 0), (0, -1)]


def print_test(x, y):
    copyMaze = [line[:] for line in maze]
    copyMaze[y][x] = 2
    print('----------------')
    for line in copyMaze:
        print(line)


def can_move(x, y, routeQueue):
    if x < 0 or x >= 7:
        return False
    if y < 0 or y >= 6:
        return False
    if (x, y) in routeQueue:
        return False
    return maze[y][x] != WALL


def next(routeQueue):
    (x, y) = routeQueue[-1]
    if maze[y][x] == GOAL:
        print(f'is finished!')
        print(routeQueue)
        return True
    for (mx, my) in moveVectors:
        (nx, ny) = (x + mx, y + my)
        if can_move(nx, ny, routeQueue):
            print_test(nx, ny)
            routeQueue.append((x + mx, y + my))
            if next(routeQueue):
                return True
            routeQueue.pop(-1)
    return False

next(routeQueue)

デバッグがてら print_test 関数作ってますね。
答えも全幅探索を真っ先に言及しているので、多分このへんは誰書いてもそんなに答えが変わらないのかもしれない。

尚、再起するときに routeQueue の中身を書き換えたくない（副作用したくない）という理由で、キューの積上があったデータを作ったら、案の定スタック食いつぶした…。
やっぱそういう原理主義は駄目ですかそうですか…。

最短経路問題となると、蟻コロニー最適化 がまっさきに浮かぶあたり業が深い…