経路探索の補足

プログラムのしくみ

link(地点1, 地点2). は、地点1と2が繋がっていることを示す。

path(地点1, 地点2). は、地点1と地点2の間で行き来が出来ることを示す。

pathFind(現在地, 目的地, 通行済み経路, これから通る経路） は、

現在地が既に通行済みでないなら、

現在地を通行済み経路に加え、

一つ先に進み、

残りの経路を探索する

というように定義されている。

田んぼの田の字を経路探索

「田」の字の 角 から 角 へ渡る経路のパターンは意外に多く、１２パターンある。

経路探索の様子

現在位置 a

ゴール g

通過地点 []

ゴールまでの経路 []

a→b 通路発見

現在位置 b

ゴール g

通過地点 [a]

ゴールまでの経路 [a]

b→a 通路発見 → a 通過済み → 別経路探索

b→d 通路発見

現在位置 d

ゴール g

通過地点 [b a]

ゴールまでの経路 [a b]

d→b 通路発見 → b 通過済み → 別経路探索

d→f 通路発見

現在位置 f

ゴール g

通過地点 [d b a]

ゴールまでの経路 [a b d]

f→d 通路発見 → d 通過済み → 別経路探索

f→g 通路発見

現在位置 g

ゴール g

通過地点 [f d b a]

ゴールまでの経路 [a b d f]

現在位置 と ゴール が一致 → ゴールまでの経路 [a b d f g]

f→h 通路発見

現在位置 h

ゴール g

通過地点 [f d b a]

ゴールまでの経路 [a b d f]

h→f 通路発見 → f 通過済み → 別経路探索

h→g 通路発見

現在位置 g

ゴール g

通過地点 [h f d b a]

ゴールまでの経路 [a b d f h]

現在位置 と ゴール が一致 → ゴールまでの経路 [a b d f h g]

a→c 通路発見

現在位置 c

ゴール g

通過地点 [a]

ゴールまでの経路 [a]

c→a 通路発見 → a 通過済み → 別経路探索

c→e 通路発見

現在位置 e

ゴール g

通過地点 [c a]

ゴールまでの経路 [a c]

e→c 通路発見 → c 通過済み → 別経路探索

全経路探索終了