全探索アルゴリズムの例題＆解説まとめ

ひとことに全探索といっても様々な種類があります。

この記事では今まで解説してきた全探索アルゴリズムをまとめていきたいと思います。

単純な全探索は最も簡単な全探索です。for文を2重3重にして回すことで実装することができます。

実装は簡単ですが、計算量は大きくなるので注意しましょう。

順列全探索は $n !$ 通りの順列の組み合わせを全探索する手法です。

Pythonではitertoolsを使うことで簡単に全ての順列を生成することができます。

bit全探索はbit演算を利用して、Yes or Noのような2択を網羅的に探索することができます。

要するに、部分集合の全パターンを列挙することができます。

深さ優先探索は途中で分岐できる場合でも気にせず深くまで探索していく探索方法です。

スタックを用いて実装する方法と再帰を利用して実装する方法があります。

幅優先探索は最短経路を求めることができます。

深さ優先探索のスタックをキューに変更することで実装することができます。

nashidos’s diary