こんにちは
今回は迷路を使って深さ優先探索と幅優先探索について考える。
今回使用する迷路
入力
入力はn行行われる。
- 1行目は迷路のスタート地点とゴール地点
- 2行目は迷路の縦の長さと横の長さ
- 3~n行目は迷路の情報
n-2は迷路の縦の長さ、マスの無いところは#で与えられる。
ex.)
S G
3 5
# B E F G
S A C H #
# D # # #
出力
出力は3行行われる。
1行目はスタート地点とゴール地点の距離
2行目は探索の回数
3行目はスタート地点からゴール地点へのルート
ex.)
スタート地点とゴール地点の距離：5
探索回数：10
ルート：G <= F <= H <= C <= A <= S
深さ優先探索
コードの流れ
1.入力される情報を読み込む
2.スタートを各種リストに追加
3.スタックから取り出す
4.ゴール判定
5.隣接している地点をスタックに追加
6.チェック済リストに入れ3に戻る
実装
stack
# cording = utf-8
start, goal = input().split() # スタート地点とゴール地点
height, width = map(int, input().split()) # 迷路縦と横の長さ
maze, stack, checked, route = [], [], [], {}
num_of_t = 0 # 探索の回数
for i in range(height):
x = input().split()
maze.append(x) # 迷路
if start in maze[i]:
now_height, now_width = i, maze[i].index(start)
start_height, start_width = now_height, now_width # スタート地点の座標を保存
stack += start
checked += start
route[maze[now_height][now_width]] = "Start"
def search(h, w, x = maze, y = stack, z = checked):
if x[h][w] != "#" and x[h][w] not in z:
y += x[h][w]
z += x[h][w]
while stack[-1] != goal:
stack.pop()
if now_height < height-1:
search(now_height+1, now_width)
if now_width < width-1:
search(now_height, now_width+1)
if now_height > 0:
search(now_height-1, now_width)
if now_width > 0:
search(now_height, now_width-1)
num_of_t += 1
for j in range(height):
if stack[-1] in maze[j]:
route[stack[-1]] = maze[now_height][now_width]
now_height, now_width = j, maze[j].index(stack[-1])
print("スタート地点とゴール地点の距離：" + str(abs(now_height - start_height) + abs(now_width - start_width)))
print("探索回数：" + str(num_of_t))
print("ルート：", end = "")
while route[goal] != "Start":
print(goal + " <= ", end="")
goal = route[goal]
print(goal)
出力結果
スタート地点とゴール地点の距離：5
探索回数：5
ルート：G <= F <= E <= B <= A <= S
幅優先探索
コードの流れ
深さ優先探索のstackをqueueに変更
実装
queue
# cording = utf-8
start, goal = input().split() # スタート地点とゴール地点を入力
height, width = map(int, input().split()) # 迷路の縦と横の長さ
maze, queue, checked, route = [], [], [], {}
num_of_t = 0 # 探索の回数
for i in range(height):
x = input().split()
maze.append(x) # 迷路
if "A" in maze[i]:
now_height, now_width = i, maze[i].index(start)
start_height, start_width = now_height, now_width # スタート地点の座標を保存
queue += start
checked += start
route[maze[now_height][now_width]] = "Start"
def search(h, w, x = maze, y = queue, z = checked):
if x[h][w] != "#" and x[h][w] not in z:
y += x[h][w]
z += x[h][w]
while queue[0] != goal:
place = queue.pop(0)
tmp = len(queue)
if now_height < height-1:
search(now_height+1, now_width)
if now_width < width-1:
search(now_height, now_width+1)
if now_height > 0:
search(now_height-1, now_width)
if now_width > 0:
search(now_height, now_width-1)
num_of_t += 1
if tmp < len(queue):
for i in range(1, len(queue) - tmp+1):
route[queue[-i]] = place
for j in range(height):
if queue[0] in maze[j]:
now_height, now_width = j, maze[j].index(queue[0])
print("スタート地点とゴール地点の距離：" + str(abs(now_height - start_height) + abs(now_width - start_width)))
print("探索回数：" + str(num_of_t))
print("ルート：", end = "")
while route[goal] != "Start":
print(goal + " <= ", end="")
goal = route[goal]
print(goal)
出力結果
スタート地点とゴール地点の距離：5
探索回数：8
ルート：G <= F <= H <= C <= A <= S
考察
アルゴリズムに関する知識は十分に深められた。
もっと短く書ける人もいるだろうが、現状の自分ではこの様になった。