今回のお話では、人工知能やニューラルネットワークの基礎としてよく使われる2つのアルゴリズム、深さ優先探索と幅優先探索の比較をします。 この2つのアルゴリズムが理解できていない方は、私の他の記事で5分ほど説明すれば理解できるようになりますので、ご確認ください。
DFS:https://medium.com/@tingyan.deng/depth-first-search-short-tutorial-165b41f1b1c0
BFS:https://medium.com/@tingyan.deng/breadth-first-search-short-tutorial-a1ceb78b0c11
まず、どちらも非情報探索アルゴリズムであり、総当り的に操作していることになるので、ツリーをどう横断するかという以外に状態や探索空間についての追加情報を持っていないことになります。 DFS や BFS に関する私の過去の記事を読んだことがあれば、いずれも探索プロセス中に各ステップの重みを調べないことをご存知でしょう。
- ランタイム。
- when DFS>BFS: 探しているノードが非常に深い場合や、かなり深いところにいくつかのゴールノードがある場合は、DFSを使うべきでしょう。 この場合、BFSは深いノードを訪問する前に上のノードをすべて訪問しなければならず、時間がかかりすぎる。
- when BFS>DFS: BFSは重みのないグラフのシングルソース最短パスを見つけるのに使える。BFSではソース頂点から最小数の辺で頂点に到達するからだ。 一方、DFSでは、送信元から送信先の頂点に到達するために、より多くのエッジを通過する可能性がある。
- search type: どちらもuninformed search
- memory comparison: BFSは、一般にDFSよりもバックトラックが必要なため、より多くのメモリを消費します。
- データ構造。 DFS はスタックを使用し、ルートから検索中のノードまでが格納されています。 BFSはキューを使用し、検索の先頭にあるノードを含む。