再帰関数を用いた深さ優先探索(DFS)による全探索アルゴリズム
forループを用いた全探索などは比較的簡単な内容なので直感的にもわかりやすいですが、簡単なものしか全探索できません。
複雑な条件や構造を持つものを全探索したい場合には、再帰関数を用いた深さ優先探索(DFS)を用いる必要があ ...
順列(n!)の全探索
\(n!\) 通りの全探索を行いたい時に順列が用いられます。
順列(permutation)とは、n 個のものを順番に並べるのは何通りあるかを考える問題です。n 個全てを区別できるなら、\(n!\) 通りの並べ方があります ...
幅優先探索(Breadth First Search)の基本
幅優先探索とは、全探索アルゴリズムの一種です。最短経路を求める際に使用される基本的なアルゴリズムです。
木などのグラフやグラフと同一視できるものを探索する際に良く使われます。深さ優先探索と似ていますが、幅優先探索は始めの状 ...
深さ優先探索(Depth First Search)の基本
深さ優先探索とは、全探索アルゴリズムの一種です。グラフや、グラフと同一視できるものを探索する際に良く使われます。
幅優先探索(BFS)と似ていますが、深さ優先探索は末端に到達するまで「深く」探索してから、他のノードの探索を ...
二分探索(Binary Search)のアルゴリズム
二分探索とは、ソート済みである配列の中から、目的の値が存在するかを調べる探索アルゴリズムです。高速でわかりやすいため非常に良く使われます。
線形探索はソートしていない配列でも探索することができます。二分 ...
ビット全探索（ 2^n 通りの全探索）
bit演算を上手く用いると、それぞれの要素に対して「使うか」「使わないか」の2通りがあるような、\(2^n\) 通りの場合を全探索することができます。
言い換えると、集合 \(\{0,1,2,3,̷ ...
ループによる全探索アルゴリズム
特定の条件を満たすようなものを発見する方法を探索アルゴリズムと言います。全探索は全ての場合を確認して、条件を満たすものが存在するかを判定します。
全探索アルゴリズムの中でもループを使ったものは基本とな ...
線形探索(Linear Search)
線形探索とは、入力を数値\(n\)とした時に、それがあるリストや配列に入っているかどうかを判定するためのアルゴリズムです。
1つのループ文を使うことでプログラムすることができます。
アルゴリズム\(i\) ...