幅優先探索とは、近い所から調べること
幅優先探索とは、出発点に近い所から順に調べて、乗り換えや移動の回数が最少の道を見つける方法です。路線図の検索の、基本の考え方です。
地図は、グラフという形で表せます。グラフとキューを使うと、数行で最短の道が求まります。
このレッスンのゴール
メモ
キューと訪問済みを使って、幅優先探索で最少の移動回数を求められる。
重要な言葉
| ことば | いみ | れい |
|---|---|---|
| グラフ | 点と、点どうしをつなぐ線でできた図 | |
| 頂点 | グラフの点。駅にあたる | 新宿 |
| 辺 | 頂点と頂点をつなぐ線。駅と駅の路線にあたる | |
| キュー | 先に入れたものを、先に取り出す列 | |
| 訪問済み | すでにキューに入れた頂点の記録 | |
| 幅優先探索 | 近い頂点から順に調べる方法 |
学生が入力するセルは、このプレビューでは空白です。
路線図はグラフで表せる
駅を頂点、駅どうしを結ぶ路線を辺と考えると、路線図はグラフです。
Python では、駅の名前から、隣の駅のリストを引く辞書で表します。梅田の隣が新大阪と難波と京橋なら、梅田の値はその3つのリストです。
キューは先に入れたものを先に出す
幅優先探索は、キューを使います。出発点を入れ、先頭を取り出し、その隣をうしろに入れます。これを繰り返します。
先に入れたものが先に出るので、出発点に近い駅から順に調べられます。一度入れた駅は訪問済みに記録し、二度と入れません。
新大阪から天王寺までの追い方
| 取り出す駅 | 新しく入れる駅 | キューの中身 | 移動回数 |
|---|---|---|---|
| 新大阪 | 梅田 | 梅田 | 梅田は1 |
| 梅田 | 難波、京橋 | 難波、京橋 | 難波と京橋は2 |
| 難波 | 天王寺 | 京橋、天王寺 | 天王寺は3 |
| 京橋 | なし（天王寺は訪問済み） | 天王寺 | 変わらない |
| 天王寺 | なし | 空 | 終わり |
学生が入力するセルは、このプレビューでは空白です。
各駅までの回数を求める
# 幅優先探索: 新大阪から、各駅までの乗る駅の数を求めます。
lines = {
"新大阪": ["梅田"],
"梅田": ["新大阪", "難波", "京橋"],
"難波": ["梅田", "天王寺"],
"京橋": ["梅田", "天王寺"],
"天王寺": ["難波", "京橋"],
}
distance = {"新大阪": 0}
queue = ["新大阪"]
while len(queue) > 0:
now = queue.pop(0)
for next_station in lines[now]:
if next_station not in distance:
distance[next_station] = distance[now] + 1
queue.append(next_station)
for name in distance:
print(name, distance[name])
# distance と queue の「新大阪」を、どちらも「難波」に変えて実行しましょう。
最初に着いた道が最短になる
近い駅から順に取り出すので、ある駅に最初に着いた道が、動く回数の最少の道です。
すべての辺を、高々1回ずつ調べます。だから手数は、頂点の数と辺の数を足した程度で、グラフが大きくなっても線形に増えます。
よくある間違い
注意
幅優先探索の答えは、一番安い道だと思いがちです。数えているのは、動く回数だけです。運賃や距離が辺ごとに違うときは、合計が最少の道を求める別の方法を使います。
ラボの端末で辺のリストを数える
辺は、「A B」のように、2つの頂点を1行に書いたリストでも表せます。下の Run は、5本の辺の小さなグラフを端末に流します。
wc -l は辺の数、grep -c はある頂点を含む辺の数を数えます。最後の Run は、キューの先頭だけを取り出します。
辺の数を数える
printf 'A B\nA C\nB D\nC D\nD E\n' | wc -lここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
頂点 D につながる辺の数
printf 'A B\nA C\nB D\nC D\nD E\n' | grep -c Dここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
キューの先頭を取り出す
printf 'a\nb\nc\n' | head -n 1ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
さらに挑戦: 道順を答える
課題が通ったら、駅の回数でなく、道順の駅のリストを返すようにしましょう。
各駅について、どの駅から来たかを辞書に覚えます。着いたら、goal から start へ戻って並べ直します。新宿から東京までの道順を、1つ答えてください。