Qiitaに載っているpythonで迷路を解くアルゴリズムについて

前提・実現したいこと

迷路探索プログラムを自作したい。
現在、独学でQiitaにあるpythonで迷路を解くアルゴリズム(リンク参照)および
アルゴリズムクイックリファレンスを用い勉強しています。
しかしながら、iswall,getWalls,getEdge関数の中身が何をしているのか理解できません。
特にgetwalls内にて配列を足しているところがわかりません。
全くの初心者ですので、可能であれば、詳しく教えていただきたいです。

https://qiita.com/sasanquaneuf/items/77bf6518b4bf97bcd15b

該当のソースコード

python
1# 迷路をグラフにする：本質的に深さ優先探索
2import itertools as it
3
4def isWall(s):
5    return 1 if s == '$' else 0
6
7def getWalls(arr, i, j):
8    return isWall(arr[i+1][j]) + isWall(arr[i-1][j]) + isWall(arr[i][j+1]) + isWall(arr[i][j-1])
9
10def getEdge(arr, i, j, edges, v, c):
11    for (a,b) in zip([1,-1,0,0], [0,0,1,-1]):
12        if isWall(arr[i+a][j+b]) == 0:
13            arr[i+a][j+b] = '$'
14            if arr[i+2*a][j+2*b] == 0:
15                vn = v
16                cn = c + 1
17            else:
18                vn = arr[i+2*a][j+2*b]
19                edges.append((v, vn, c))
20                cn = 1
21            getEdge(arr, i+2*a, j+2*b, edges, vn, cn)
22
23vs = 0
24edges = list()
25arr = list()
26for line in open('maze_input.txt', 'r'):
27    arr.append(list(line))
28height = len(arr)
29width = len(arr[height - 1])
30cellidi = range(1,width,2)
31cellidj = range(1,height,2)
32for i,j in it.product(cellidi, cellidj):
33    if getWalls(arr, i, j) == 2:
34        arr[i][j] = 0
35    elif arr[i][j] == ' ':
36        vs += 1
37        arr[i][j] = vs
38
39# 今回のデータ用の設定
40getEdge(arr, 3, 7, edges, 1, 1)

試したこと

アルゴリズムクイックリファレンスを読んだ

行動規範の内容に同意します

回答2件

ベストアンサー

isWall

引数sが壁($)かどうかを判定して、壁なら1、そうでなければ0を返しています。

getWalls

座標(i, j)の上下左右に壁が何ヵ所あるかを返しています。

getEdge

迷路の情報arrをスタート地点から順に調べていき、edgesにグラフ情報を保存しています。

また、関数化されていませんが、実は下部のfor文も結構大事な処理です。

python
1for i,j in it.product(cellidi, cellidj):
2    if getWalls(arr, i, j) == 2:
3        arr[i][j] = 0
4    elif arr[i][j] == ' ':
5        vs += 1
6        arr[i][j] = vs

ここでは、読み込んだ迷路情報から、通路の座標がノードになるかエッジになるかを判断しています。
つまりgetEdges関数では、各座標がエッジかノードかの情報が付与された迷路情報を受け取り、それらのつながりを追っていくことでグラフを作成しています。

投稿2018/07/03 09:49

shiron46

総合スコア111

isWallは引数の文字が$かどうか判定するだけです。

getWallsはi,jで表される現在の探索位置の右左下上にisWallを適用し、結果を合算しているので「いくつの壁に囲まれているか」を返します。

getEdgeはちょっとなかなか読み込めないので、とりあえずざっくりしたコメントだけ入れておきます。

python
1def getEdge(arr, i, j, edges, v, c):
2    """読み込めて無くていまいちよくわからないので、ざっくりしか説明できません
3    qiitaの説明の引用：「
4    getEdgeという関数が、本質的には深さ優先探索を行っていて、ひたすら自分と隣接するマスを再帰的に処理します。マスが既に処理されたかどうかは、盤面が入っているリストarrにそのまま書き込んでいきます。
5    また、この処理をするときに、ついでに「辺の長さ」＝「次の交差点や行き止まりに行きつくまでのマスの数」も計算することにしました。
6    」
7    """
8    for (a,b) in zip([1,-1,0,0], [0,0,1,-1]):  # ((1,0),(-1,0),(0,1),(0,-1))がzipの結果。けっきょく右、左、下、上を見てる
9        if isWall(arr[i+a][j+b]) == 0:  # 壁じゃなかったら探索を続ける
10            arr[i+a][j+b] = '$'  # もう見たマスには$を入れておく（簡略化のためにそうしているのでしょう）
11            if arr[i+2*a][j+2*b] == 0:  # 右に2歩とか上に2歩とかそんな感じ
12                vn = v
13                cn = c + 1
14            else:
15                vn = arr[i+2*a][j+2*b]  
16                edges.append((v, vn, c))
17                cn = 1
18            getEdge(arr, i+2*a, j+2*b, edges, vn, cn)  # 壁じゃなかったら探索を続ける