KATUBLO | エンジニアの日常BLOG

プログラミング、数学、旅行などを中心に役立つ情報をお届け

2019年07月23日

【組み合わせアルゴリズム】深さ優先探索と幅優先探索とは?違いなどを解説

深さ優先探索(depth first search)

アルゴリズムの全体像

深さ優先探索は左から順番に根の一番奥まで一気検索し、末端についたら近いところを1つずつ調べて行くアルゴリズムです。存在しなかったら分岐の1つ前に戻り、次のノードを調べます。以下の図のイメージです。

計算量

アルゴリズム全体像からわかる通り、深いノードから1つ1つを調べていくことになるので、最悪計算量はエッジ数[math]| E | [/math]に比例することになり、[math] O ( | E | )[/math]となります。

 

幅優先探索(breadth first search)

アルゴリズムの全体像

幅優先探索は上から同じ深さのノードを調べて、末端に向かって行くアルゴリズムです。イメージとしては以下の図です。

計算量

実は幅優先探索も深さ優先探索と同じで、最悪計算量はエッジ数[math]| E | [/math]に比例することになり、[math] O ( | E | )[/math]となります。

 

深さ優先探索と幅優先探索を比較

深さ優先探索

メリット デメリット
解を素早く見つけられる(メモリの消費量が少ない) 解が最適解でない可能性がある
根が深いと計算量が多くなる

幅優先探索

メリット デメリット
確実に解を見つけることができる 確実な分、計算量が多くなる
最適解(浅い所にある解)を見つけることができる

 

 

 

プログラムを実際に書きたい人はatcoderとかで問題を解きながら書くといいかもしれません。

 

 

 

参考サイト

http://kussharo.complex.eng.hokudai.ac.jp/~kurihara/classes/AI/blind.pdf

https://mathtrain.jp/dfsbfs

https://pyteyon.hatenablog.com/entry/2019/03/01/211133

 

 

最後まで読んで頂き、ありがとうございました。
SNS等でのシェアが頂ければ幸いです!

プロフィール

@KATUO

現在都内私立大学に通う大学4年生。大学では電気電子工学を専攻。大学2年の夏頃に、プログラマーの長期インターン募集の広告が目に止まり、独学でプログラミングの学習を開始。現在は「ToC向け大規模サービスを運営するメガベンチャー」と「AIスタートアップ」でインターンで修行中。2020年4月からwebエンジニアとして社会人生活スタート。

広告

特集記事