* Graph: VertexとEdgeの組み合わせ
* 探索の起点(Source): 起点となるVertex
を与えられた時に、
Sourceから他のすべてのVertexへの
* 最短距離と
* その経路
を求めることのようです。
まずGraph, Vertex, Edgeってなんぞやって話ですが、
Vertexはいわゆるノード(下の図で言うと"東京", "大阪", "仙台", "札幌")で、
Edgeは"東京-大阪", "東京-仙台", "札幌-大阪"間を結ぶ線のことです。
でGraphは下の図全体って感じです。
サンプルプログラム
def init(graph):
import sys
for vertex in graph.vertices:
vertex.color = Vertex.WHITE
vertex.distance = sys.maxint
vertex.parent = None
def bfs(graph, source):
init(graph)
source.color = Vertex.GRAY
source.distance = 0
source.parent = None
queue = [source]
while len(queue) > 0:
origin = queue.pop(0)
for target in graph.adjacency_of(origin):
if target.color == Vertex.WHITE:
target.color = Vertex.GRAY
target.distance = origin.distance + 1
target.parent = origin
queue.append(target)
origin.color = Vertex.BLACK
もちろんエントリーポイントはbfs(graph, source)です。
こいつに、graphと探索の起点となるsourceを渡しています。
ざっと眺めてなんじゃこれと思うのは、 Vertex.WHITEやVertex.GRAY、Vertex.BLACKじゃないでしょうか？
それぞれ、
* WHITE: まだ探索されていないVertex
* GRAY: 探索はされたが近隣のVertexの少なくとも一つはWHITE
* BLACK: 近隣のVertexがすべてGRAYもしくはBLACKになった。
を意味します。
アルゴリズムの全体の流れは、
1. graph内のすべてのvertexを初期化(init関数)する。
(色をWHITE, 距離をinfinity, 親をNoneにする)
2. 起点(source)を探索済み、距離0、親Noneに設定する。
3. 起点をキューにいれ、起点の近隣Vertexが未探索であれば探索済みにして、キューに入れる
て感じです。
この各Vertexで計算されたdistanceが最短距離となり、
各Vertexのparentをたどることで最短距離経路がわかることとなります。
例えば、↑のGraphサンプル図で"東京"を起点として探索して見ると、
1. 東京を探索済みにする。（距離0、親 なし）
2. 東京の近隣の大阪、仙台を探索済みにする。（距離1、親 東京）
3. 大阪の近隣の東京、札幌を探索するが、
東京は探索済みなので札幌のみ探索。（距離2、 親 大阪）
4. 仙台の近隣の探索をするが、東京は探索済みなので何もしない。
なんで最短経路になるの？
証明の流れは、
その1. δ(s, v) ≤ δ(s, u) + 1
起点をs、graph内の任意のVertexをu, vとして、δ(s, u)をs=>uまでの最短距離とした時、
u => vへのEdge(u, v)があれば、↑が成り立つことを証明。
その2. v.d ≥ δ(s, v)
BFSで計算した距離は最短距離以上であることを証明
その3. Queue(v1.d, v2.d, ...., vn.d), v1.d ≤ v2.d ≤ ... ≤ vn.d ≤ v1.d + 1
キューの中にv1, v2, ..., vnが入っていた場合
常にv1.d ≤ v2.d ≤ ... ≤ vn.d ≤ v1.d + 1
が成り立つことを証明。
そして最終的にv.d > δ(s, v)となると仮定し、
その矛盾を解くことv.d = δ(s, v)であることを証明する。
その1の証明
帰納法を使うのですが、ざっくりというと、
uまでの最短距離δ(s, u)が成り立っている時、
vが未探索の場合はδ(s, v) = δ(s, u)+1となる。（サンプルコードの20行目）
すでに探索済みの場合は、δ(s, v) ≤ δ(s, u)となる。
（探索済みということはdistanceは単調増加なのでuよりdistanceが短いはずですからね）
その2の証明
これまた帰納法を使うようですが、
vの一個手前のVertex uまではu.d ≥ δ(s, u)が成り立つとすると、
v.d = u.d + 1 ≥ δ(s, u) + 1 ≥ δ(s, v)
が成り立つ。
その3の証明
これまた帰納法で証明します。
v1.d ≤ v2.d ≤ ... ≤ vn.d ≤ v1.d + 1が成り立っている時、
1. v1をQueueから削除した時、v2.d ≤ ... ≤ vn.d ≤ v2.d + 1が成り立つことを証明する
v1.d ≤ v2.d から v1.d + 1 ≤ v2.d + 1 が成り立つ。
そこから↑が成り立つことが言える。
2. 次にv(n+1)を入れた時にv2.d ≤ ... ≤ vn.d ≤ v(n+1).d ≤ v2.d + 1が成り立つことを証明する
v(n+1).d = v1.d + 1 ≤ v2.d + 1なので、成り立つといえる。
・・・ということで、
あるvにおいてv.d > δ(s, v)となってしまったとします。
その直前のVertex uではu.d = δ(s, u)が成り立っているとすると、
v.d > δ(s, v) = δ(s, u) + 1 = u.d + 1
が成り立つ。
vがWHITEの時、v.d = u.d + 1より↑の式と矛盾する。
vがBLACKの時、その３の証明よりv.d ≤ u.dから↑の式と矛盾する。
vがGRAYの時、すでにQueueに入っているので、v.d = w.d + 1となるwが必ず存在する。
wはuより前にdequeueされているのでv.d = w.d + 1 ≤ u.d + 1よってこの場合も矛盾する。
ということでv.d >δ(s, v)となるvは存在しないので、すべてのVertex vにおいて、
v.d = δ(s, v)といえます。
その1. δ(s, v) ≤ δ(s, u) + 1
起点をs、graph内の任意のVertexをu, vとして、δ(s, u)をs=>uまでの最短距離とした時、
u => vへのEdge(u, v)があれば、↑が成り立つことを証明。
その2. v.d ≥ δ(s, v)
BFSで計算した距離は最短距離以上であることを証明
その3. Queue(v1.d, v2.d, ...., vn.d), v1.d ≤ v2.d ≤ ... ≤ vn.d ≤ v1.d + 1
キューの中にv1, v2, ..., vnが入っていた場合
常にv1.d ≤ v2.d ≤ ... ≤ vn.d ≤ v1.d + 1
が成り立つことを証明。
そして最終的にv.d > δ(s, v)となると仮定し、
その矛盾を解くことv.d = δ(s, v)であることを証明する。
その1の証明
帰納法を使うのですが、ざっくりというと、
uまでの最短距離δ(s, u)が成り立っている時、
vが未探索の場合はδ(s, v) = δ(s, u)+1となる。（サンプルコードの20行目）
すでに探索済みの場合は、δ(s, v) ≤ δ(s, u)となる。
（探索済みということはdistanceは単調増加なのでuよりdistanceが短いはずですからね）
その2の証明
これまた帰納法を使うようですが、
vの一個手前のVertex uまではu.d ≥ δ(s, u)が成り立つとすると、
v.d = u.d + 1 ≥ δ(s, u) + 1 ≥ δ(s, v)
が成り立つ。
その3の証明
これまた帰納法で証明します。
v1.d ≤ v2.d ≤ ... ≤ vn.d ≤ v1.d + 1が成り立っている時、
1. v1をQueueから削除した時、v2.d ≤ ... ≤ vn.d ≤ v2.d + 1が成り立つことを証明する
v1.d ≤ v2.d から v1.d + 1 ≤ v2.d + 1 が成り立つ。
そこから↑が成り立つことが言える。
2. 次にv(n+1)を入れた時にv2.d ≤ ... ≤ vn.d ≤ v(n+1).d ≤ v2.d + 1が成り立つことを証明する
v(n+1).d = v1.d + 1 ≤ v2.d + 1なので、成り立つといえる。
・・・ということで、
あるvにおいてv.d > δ(s, v)となってしまったとします。
その直前のVertex uではu.d = δ(s, u)が成り立っているとすると、
v.d > δ(s, v) = δ(s, u) + 1 = u.d + 1
が成り立つ。
vがWHITEの時、v.d = u.d + 1より↑の式と矛盾する。
vがBLACKの時、その３の証明よりv.d ≤ u.dから↑の式と矛盾する。
vがGRAYの時、すでにQueueに入っているので、v.d = w.d + 1となるwが必ず存在する。
wはuより前にdequeueされているのでv.d = w.d + 1 ≤ u.d + 1よってこの場合も矛盾する。
ということでv.d >δ(s, v)となるvは存在しないので、すべてのVertex vにおいて、
v.d = δ(s, v)といえます。
全然関係ないですが・・・
なんか"探索"って割りには目的物がはっきりしないので
ほんとに"探索"なのか？と思いましたが、
どうも探索で合ってるらしい（当たり前か・・・ずっと探索と呼ばれてますしね）。
ざっくりとですが、
検索=目的のものを探すこと
探索=興味あるモノの解析すること
ということらしいですね。
だから探索なんですね。
はいすんません。
ほんとに"探索"なのか？と思いましたが、
どうも探索で合ってるらしい（当たり前か・・・ずっと探索と呼ばれてますしね）。
ざっくりとですが、
検索=目的のものを探すこと
探索=興味あるモノの解析すること
ということらしいですね。
だから探索なんですね。
はいすんません。
