深さと広さのまとめ

深さと広さのまとめ
1.深さ優先探索(遡及法)
[アルゴリズムの考え方]
深度優先探索(DFS,Depth-First Search)は探索の手段の一つである.ある状態から、状態が移行できないまで移行し、前の状態に戻り、他の状態に移行し続け、最終的な解が見つかるまで繰り返します.深度優先探索の特徴に基づいて、再帰関数(スタックを暗黙的に利用する計算)を採用することは比較的簡単である.
アルゴリズムの説明

void dfs(int step)
{
	    
	       for(i=1;i<=n;i++)
	{
		      dfs(step+1);
	}
	  
}

[アルゴリズム効率]
深度優先探索は、最初の状態から、到達可能なすべての状態を巡回する.これにより、全ての状態を操作することができる、あるいは全ての状態を列挙することができる.探索アルゴリズムの一つとして、DFSは一つの解を探すNP(NPCを含む)問題に対して大きな役割を果たす.
しかし、検索アルゴリズムは結局時間の複雑さです.
O(n!)
の階乗級アルゴリズムは、その効率が比較的に低く、データ規模が大きくなると、このアルゴリズムは力不足に見える.
深度優先探索の効率問題については、様々な解決方法がある.最も汎用性があるのは、枝切り(prunning)である、つまり無駄な探索分岐を除去することである.
実行可能性のある枝切りと最適性のある枝切りの2種類がある.また、多くの問題に対して、探索と動的計画(DP,dynamic programming)、完全整合(ハンガリーアルゴリズム)などの効率的なアルゴリズムを組み合わせることができる.
2.幅優先探索(分岐限界法)
[アルゴリズムの考え方]
幅優先探索(BFS,Breadth-First Search)も探索の手段の一つである.深さ優先検索と似ています
ある状態から到達可能なすべての状態を検索する.
幅優先探索の特徴により、キューによる実現が比較的簡単である.
アルゴリズムの説明
/*遍歴連通図*/

void BFS(Graph G,int v)
{    
    /*             G*/
    cout<=0;w=NextAdjVex(G,u,w))
       {  /*    u      w，FirstAdjVex(G,u)  u       */
          /*NextAdjVex(G,u,w)  u   w       ,w>=0       */
          if(!vistited[w])        /*w u          */
            {
             cout<

[アルゴリズム効率]
深さ優先とは異なる、探索の順序において、幅優先探索は常に初期状態に近い状態を探索する.すなわち,開始状態→1回の遷移で到達可能なすべての状態→2回の遷移で到達可能なすべての状態→…である.このような順序で検索を行う.同じ状態の場合、幅優先検索は1回のみ行われるため、複雑度は
O(状態数*遷移方式).最短経路、最小操作などの問題の答えを求めるのに容易に用いる.
広さ探索の判断が繰り返す直接判断に時間がかかる場合、ハッシュテーブルを用いて時間の複雑さを最適化するのが一般的である.
3.Death-Breadthまとめ
幅優先探索は、深さ優先探索と同様に遍歴可能なすべての状態を生成するので、すべての状態を処理する必要がある場合に幅優先を用いることも可能である.しかし、再帰関数は簡単に記述することができ、状態の管理も簡単であるため、深さ優先探索で実現することが多い.逆に、最短ルートを求める場合には深さ優先探索は同じ状態を繰り返す必要があるので、幅優先探索を用いるほうがよい.
幅優先探索は、状態を1つずつキューに入れるので、通常は状態数に比例するメモリ領域が必要となる.逆に、深さ優先探索は、最大の再帰深さに比例する.一般に状態数に比べる再帰的な深さはそれほど大きくないので、深さ優先探索の方がメモリを節約できると考える.