回溯是用試錯的思想，它嘗試分步的去解決一個問題。深度優先回溯是指在樹或圖的回溯中，沿著樹的深度遍歷樹的節點，儘可能深的搜尋樹的分支。當節點v的所在邊都己被探尋過或者在搜尋時結點不滿足條件，搜尋將回溯到發現節點v的那條邊的起始節點。整個進程反覆進行直到所有節點都被訪問為止或已經找到有效的解答。
基本介紹
- 中文名：深度優先回溯
- 外文名：Depth-First backtracking
- 學科：計算機
- 定義：沿一個深度優先嘗試解決問題
- 有關術語：回溯法
- 領域：算法套用
回溯法,有關解釋,二類常見的解空間樹：,問題的解空間,深度優先搜尋,
回溯法
算法設計的基本方法之一。採用系統地搜尋給定問題的解空間的方法來確定問題的解。用一種所謂解空間的樹形結構將使這種搜尋容易實現。索之前，先把各種候選對象組織成一棵樹，每個樹葉對應著一個候選對象，每個內部結點表示若干個候選對象(即在此結點下面的各個樹葉所對應的候選對象)。
回溯法是從樹根開始按深度優先搜尋的原則向下搜尋，搜尋的情況可概括為一句話“向前走，碰壁回頭”，即沿著一個方向儘量向下搜尋，直到發現此方向上不可能存在解答時，就回到上一個結點，沿著另一個方向進行同樣的工作.有許多問題，需要找出它的解集或者要求回答什麼樣的解是滿足某些約束條件的最優解時，往往要使用回溯法來求解。般地，回溯法效率較低，但是描述比較簡明。種方法適用於解的組合數相當大但仍然有限的那一類問題，例如八皇后問題、圖的著色問題、哈密頓迴路問題等。試一些軟體系統也採用回溯法。
回溯法通常用最簡單的遞歸方法來實現，可能出現兩種情況：找到一個可能存在的正確的答案；在嘗試了所有可能的分步方法後宣告該問題沒有答案。在最壞的情況下，回溯法會導致一次複雜度為指數時間的計算。
有關解釋
二類常見的解空間樹：
子集樹：當所給的問題是從n個元素的集合S中找出滿足某種性質的子集時 相應的解空間樹稱為子集樹 子集樹通常有2 子集時，相應的解空間樹稱為子集樹。子集樹通常有2n個葉子結點，其總結點個數為2n+1 -1，遍歷子集樹時間為Ω(2n) 。如0-1背包問題，葉結點數為2n，總結點數2n+1；
排列樹：當所給問題是確定 當所給問題是確定n個元素滿足某種性質的排列時 個元素滿足某種性質的排列時，相應的解空間樹稱為排列樹。排列樹通常有n!個葉子結點，因此，遍歷排列樹需要Ω(n!)的計算時間。如TSP問題，葉結點數為n!，遍歷時間為Ω(n!)。
問題的解空間
— 問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式 (x1,x2,…,xn)
的形式。
— 顯約束：對分量xi的取值限定。
— 隱約束：為滿足問題的解而對不同分量之間施加的約束。
— 解空間：對於問題的一個實例，解向量滿足顯式約束條件的所有多元組，
構成了該實例的一個解空間。
深度優先搜尋
深度優先搜尋算法（Depth-First-Search，簡稱DFS）是一種用於遍歷或搜尋樹或圖的算法。沿著樹的深度遍歷樹的節點，儘可能深的搜尋樹的分支。當節點v的所在邊都己被探尋過，搜尋將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重複以上過程，整個進程反覆進行直到所有節點都被訪問為止。屬於盲目搜尋。
深度優先搜尋是圖論中的經典算法，利用深度優先搜尋算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。
代碼
struct Node { int self; //數據 Node *left; //左節點 Node *right; //右節點 };const int TREE_SIZE = 9;std::stack<Node*> 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// 只有UNVISITED不空while(!unvisited.empty()){ current=(unvisited.top()); //當前應該訪問的 unvisited.pop(); if(current->right!=NULL) unvisited.push(current->right); // 把右邊壓入 因為右邊的訪問次序是在左邊之後 if(current->left!=NULL) unvisited.push(current->left); cout<<current->self<<endl;}