探索、推論

探索、推論

迷路(探索木)

上のような迷路があった時、分岐点にラベル付けをする。
〇:分岐 □:行き止まり

Sを起点にした、次のような図をツリー構造と言います。

幅優先探索:あるノードから繋がっている隣のノードのすべて探索(赤数字)
深さ優先探索:あるノードから行き止まりまでいき、一つ前にもどって探索。メモリが少なくて済むというメリットがある。(緑数字)