-
深度優先搜索
鎖定
深度優先搜索詳細解釋
事實上，深度優先搜索屬於圖算法的一種，英文縮寫為DFS即Depth First Search.其過程簡要來説是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次.
圖
深度優先搜索基本思路
深度優先遍歷圖的方法是，從圖中某頂點v出發：
（1）訪問頂點v；
（2）依次從v的未被訪問的鄰接點出發，對圖進行深度優先遍歷；直至圖中和v有路徑相通的頂點都被訪問；
（3）若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發，重新進行深度優先遍歷，直到圖中所有頂點均被訪問過為止。 當然，當人們剛剛掌握深度優先搜索的時候常常用它來走迷宮.事實上我們還有別的方法，那就是廣度優先搜索(BFS).
深度優先搜索窮舉
在我們遇到的一些問題當中，有些問題我們不能夠確切的找出數學模型，即找不出一種直接求解的方法，解決這一類問題，我們一般採用搜索的方法解決。搜索就是用問題的所有可能去試探，按照一定的順序、規則，不斷去試探，直到找到問題的解，試完了也沒有找到解，那就是無解，試探時一定要試探完所有的情況（實際上就是窮舉）；
[2]
對於問題的第一個狀態，叫初始狀態，要求的狀態叫目標狀態。
搜索就是把規則應用於實始狀態，在其產生的狀態中，直到得到一個目標狀態為止。
產生新的狀態的過程叫擴展（由一個狀態，應用規則，產生新狀態的過程）
搜索的要點：（1）初始狀態；
（2）重複產生新狀態；
如果搜索是以接近起始狀態的程序依次擴展狀態的，叫寬度優先搜索。
如果擴展是首先擴展新產生的狀態，則叫深度優先搜索。
深度優先搜索
深度優先搜索用一個數組存放產生的所有狀態。
（1） 把初始狀態放入數組中，設為當前狀態；
（2） 擴展當前的狀態，產生一個新的狀態放入數組中，同時把新產生的狀態設為當前狀態；
（3） 判斷當前狀態是否和前面的重複，如果重複則回到上一個狀態，產生它的另一狀態；
（4） 判斷當前狀態是否為目標狀態，如果是目標，則找到一個解答，結束算法。
（5） 如果數組為空，説明無解。
搜索是人工智能中的一種基本方法，是一項非常普遍使用的算法策略，能夠解決許許多多的常見問題，在某些情況下我們很難想到高效的解法時，搜索往往是可選的唯一選擇。按照標準的話來講：搜索算法是利用計算機的高性能來有目的的窮舉一個問題的部分或所有的可能情況，從而求出問題的解的一種方法。
搜索雖然簡單易學易於理解，但要掌握好並寫出速度快效率高優化好的程序卻又相當困難，總而言之，搜索算法靈活多變，一般的框架很容易寫出，但合適的優化卻要根據實際情況來確定。在搜索算法中，深度優先搜索（也可以稱為回溯法）是搜索算法裏最簡單也最常見的，今天我們就從這裏講起，下面的內容假設讀者已經知道最基本的程序設計和簡單的遞歸算法。
深度優先搜索系統算法
所有的搜索算法從其最終的算法實現上來看，都可以劃分成兩個部分──控制結構和產生系統。正如前面所説的，搜索算法簡而言之就是窮舉所有可能情況並找到合適的答案，所以最基本的問題就是羅列出所有可能的情況，這其實就是一種產生式系統。
[2]
我們將所要解答的問題劃分成若干個階段或者步驟，當一個階段計算完畢，下面往往有多種可選選擇，所有的選擇共同組成了問題的解空間，對搜索算法而言，將所有的階段或步驟畫出來就類似是樹的結構（如圖）。
上面的話可能難於理解，沒關係，我們通過基本框架和例子來闡述這個算法，你會發現其中的原理非常簡單自然。
深度優先搜索基本框架
–if 狀態 是 目標狀態then
·dosomething
–else
·for 每個新狀態
–if 新狀態合法
»dfs(新狀態)
·主程序：
·dfs(初始狀態)
深度優先搜索C++的實現
struct Node { int self; //數據 node *left; //左節點 node *right; //右節點 };
“ A B C D E F G ”
“
const int TREE_SIZE = 9;
std::stack<node*> visited, unvisited;
node nodes[TREE_SIZE];
node* current;
for( int i=0; i<TREE_SIZE; i++) //初始化樹
{
nodes[i].self = i;
int child = i*2+1;
if( child<TREE_SIZE ) //Left child
nodes[i].left = &nodes[child];
else nodes[i].left = NULL;
child++;
if( child<TREE_SIZE ) //Right child
nodes[i].right = &nodes[child];
else nodes[i].right = NULL;
}
unvisited.push(&nodes[0]); //先把0放入UNVISITED stack
while(!unvisited.empty()) //只有UNVISITED不空
{
current=(unvisited.top()); //當前應該訪問的
unvisited.pop();
if(current->right!=NULL)
unvisited.push(current->right); // 把右邊壓入 因為右邊的訪問次序是在左邊之後
if(current->left!=NULL)
unvisited.push(current->left);
visited.push(current);
cout<<current->self<<endl;
}
”
深度優先搜索舉例
這道題來舉例（迷宮）
1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 |
0 | 1 | 0 | 1 |
0 | 1 | 1 | 1 |
記錄起點為（1,1）找到所有的到（4,4）的路徑.
pascal程序如下：
const
b:array[1..4,1..4]of integer=(（1,1,1,1）,(0,1,0,1）,(0,1,0,1）,(0,1,1,1）);
c:array[1..4,1..2]of -1..1=((0,1）,(0,-1）,（1,0),(-1,0));
var
a:array[1..16,1..2]of integer;
procedure print;
var
i,j:integer;
begin
for i:=1 to 4 do
begin
for j:=1 to 4 do
write(b[i,j]:3）;
writeln;
end;
writeln('--------------');
end;
procedure try(k:integer);
var
i:integer;
begin
if (a[k,1]=4）and(a[k,2]=4） then
begin
print;
exit;
end;
for i:=1 to 4 do
begin
a[k+1,1]:=a[k,1]+c[i,1];
a[k+1,2]:=a[k,2]+c[i,2];
if (a[k+1,1]>=1） and (a[k+1,1]<=4 )and (a[k+1,2]>=1） and (a[k+1,2]<=4） and
（b[a[k+1,1],a[k+1,2]]=1） then
begin
b[a[k+1,1],a[k+1,2]]:=2;
try(k+1）;
b[a[k+1,1],a[k+1,2]]:=1;
end;
end;
end;
begin
a[1,1]:=1;
a[1,2]:=1;
b[1,1]:=2;
try（1）;
end.這個程序的意思就是：進行搜索一條路，直到不能走為止，換另一條路。
