©2024 Thoth Children All rights reserved.

グラフ探索の種類

グラフ探索は、何を基準に探索をしていくかなどで幾らかの探索に種類を分類していくことができます.深さ優先探索や幅優先探索は次の探索する候補をどのように選択するかで決めたものです.
2018.7.22
  • 54
    Views
  • 0
    Watch
  • 3
    Knows

グラフ探索の種類の新規投稿

反復深化探索
反復深化探索(反復深化深さ優先探索, ID, Iterative deepening depth-first search)は深さを制限した深さ優先探索を最大深さ0から次第に大きくしながら目的のデータが見つかるまで繰り返す探索.深さ優先のメモリの効率性と幅優先探索の完全性、最適性を備え持っているため、深さ優先探索や幅優先探索よりも理論上優れていることが多い.
PV 1012
Fav 0
2018.07.22
幅優先探索
幅優先探索はグラフデータの中でスタートのデータから浅いデータから探索し、見つからなければ更に深いところで次の候補を探していく探索.今まで見てきたデータを保持するため空間計算量が大きく、頂点数VでO(V)、または深さdと平均分岐数bを用いてO(b^d)と記述できます
PV 127
Fav 0
2018.07.22
深さ優先探索
深さ優先探索はグラフデータの中でスタートのデータからとりあえずグラフの分岐がなくなるまで探索し、なくなったら少し戻って次の候補を探していく探索.データが深いところにありうる場合には幅優先探索でなくこちらを使用します.際限なく深くなりそうなときは最大深さを決めて途中で打ち切る場合もあります.通常幅優先探索より空間計算量ははるかに小さくなる.
PV 256
Fav 0
2018.07.22

グラフ探索の種類人気知識・質問

反復深化探索
反復深化探索(反復深化深さ優先探索, ID, Iterative deepening depth-first search)は深さを制限した深さ優先探索を最大深さ0から次第に大きくしながら目的のデータが見つかるまで繰り返す探索.深さ優先のメモリの効率性と幅優先探索の完全性、最適性を備え持っているため、深さ優先探索や幅優先探索よりも理論上優れていることが多い.
PV 1012
Fav 0
2018.07.22
深さ優先探索
深さ優先探索はグラフデータの中でスタートのデータからとりあえずグラフの分岐がなくなるまで探索し、なくなったら少し戻って次の候補を探していく探索.データが深いところにありうる場合には幅優先探索でなくこちらを使用します.際限なく深くなりそうなときは最大深さを決めて途中で打ち切る場合もあります.通常幅優先探索より空間計算量ははるかに小さくなる.
PV 256
Fav 0
2018.07.22
幅優先探索
幅優先探索はグラフデータの中でスタートのデータから浅いデータから探索し、見つからなければ更に深いところで次の候補を探していく探索.今まで見てきたデータを保持するため空間計算量が大きく、頂点数VでO(V)、または深さdと平均分岐数bを用いてO(b^d)と記述できます
PV 127
Fav 0
2018.07.22