文章目錄
- 前言
- 一、回溯法概述
- 二、回溯法的基本思想
- 三、回溯法的設計步驟
- 四、回溯法效率分析
- 五、回溯法示例
- 總結
前言
大家好，越努力，越幸運，我是程式猿小猿。本篇文章小猿将跟您分享算法設計與分析中的回溯法，希望對您有所幫助。
一、回溯法概述
1、應用背景
（1）、有許多問題，當需要找出它的解集或者要求回答什麼解是滿足某些限制條件的最優解時，往往要使用回溯法。
（2）、回溯法有"通用解題法"之稱，是既有系統性又有跳躍性的搜尋算法。由于組織得井井有條、能避免不必要的窮舉式搜尋，是以這種方法适用于解一些組合數相當大的問題。
（3）、回溯法，在搜尋嘗試中找問題的解，當不滿足求解條件就"回溯"傳回，嘗試别的路徑。它采用了一種"走不通就掉頭"的思想，作為其控制結構。
2、問題的解空間
（1）、用回溯法解問題時：應明确問題的解空間；将解空間很好地組織起來，通常組織成樹或圖的形式。
（2）、問題的解向量：回溯法把一個問題的可能解表示成一個等長的n元式X=(x1，x2，x3，…，xn)形式。
（3）、限制條件：
顯限制：對分量xi的取值限定，即xi屬于集合Si。
隐限制：為滿足問題的解而對不同分量之間施加的限制。
（4）、解空間：滿足顯式限制條件的解向量(等長)的所有多元組，構成了問題執行個體的一個解空間。值得注意的是，同一個問題的解可以有多種表示，有些表示方法更簡單，所需表示的狀态空間更小(存儲量少，搜尋方法簡單)。
（5）、可行解：滿足限制條件的解，是解空間中的一個子集。
（6）、最優解：使目标函數取極值(極大或極小)的可行解，一個或少數幾個。
3、生成問題解的方法
（1）、擴充結點：正在産生孩子的結點稱為擴充結點。
（2）、活結點：一個自身己生成，但其孩子還沒有全部生成的結點稱做活結點。
（3）、死結點：所有孩子已經産生的結點稱做死結點。 注意：這些結點都是在搜尋過程中動态生成的。
（4）、深度優先的問題解生成法：如果對一個擴充結點R，一旦産生了它的一個孩子C，就把C當做新的擴充結點。在完成對子樹C(以C為根的子樹)的窮盡搜尋之後，将R重新變成擴充結點，繼續生成R的下一個孩子(如果存在)。.
（5）、廣度優先的問題解生成法：在一個擴充結點變成死結點之前，它一直是擴充結點。
（6）、回溯法：為了避免生成那些不可能産生最優解的問題狀态，在搜尋過程中，要不斷地利用限界函數來"處死"那些實際上不可能産生所需解的活結點，以減少問題的計算量。具有限界面數的深度優先的解生成法稱為回溯法。
二、回溯法的基本思想
回溯法在問題的解空間樹中，按深度優先政策，從根結點出發搜尋解空間樹。算法搜尋至解空間樹的任意一點時，先判斷該結點是否包含問題的解。如果肯定不包含，則跳過對該結點為根的子樹的搜尋，逐層向其祖先結點回溯；否則，進入該子樹，繼續按深度優先政策搜尋。為避免無效搜尋，采用限界/剪枝函數；用限制函數(條件)在擴充結點處剪去不滿足限制的子樹，即剪去得不到可行解的子樹；用目标函數剪去得不到最優解的子樹。
三、回溯法的設計步驟
回溯法的步驟
1、針對所給問題，定義問題的解空間；
2、确定易于搜尋的解空間結構；
3、以深度優先方式搜尋解空間，并在搜尋過程中用剪枝函數避免無效搜尋。
注意點
1、用回溯法解題的顯著特征
（1）、在搜尋過程中動态産生問題的解空間。這裡需要注意的是，解空間樹是虛拟的，不需要構造一棵真正的樹結構。
（2）、在任何時刻，算法隻儲存從根結點到目前擴充結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為0(h(n))。而顯式地存儲整個解空間則需要O(2^h(n))或O(h(n)!)記憶體空間。
2、回溯法的實作方式
( 1 )、遞歸回溯求解
回溯法對解空間作深度優先搜尋，是以，在一般情況下用遞歸方法實作回溯法。
算法描述
( 2 )、疊代回溯求解
采用樹的非遞歸深度優先周遊算法，可将回溯法表示為一個非遞歸疊代過程。
算法描述
3、解空間樹的類型
（1）、子集樹
當所給問題是從n個元素的集合S中找出滿足某種性質的子集時，相應的解空間樹稱為子集樹。
周遊子集樹需O(2^n)計算時間。
（2）、排列樹
當所給問題是确定n個元素滿足某種性質的排列時，相應的解空間樹稱為排列樹。
周遊排列樹需要Q(n!)計算時間。
四、回溯法效率分析
1、回溯算法的效率在很大程度上依賴于以下因素
（1）、産生x[k]的時間；
（2）、滿足顯限制的x[k]值的個數；
（3）、計算限制函數constraint的時間；
（4）、計算上界函數bound的時間；
（5）、滿足限制函數和上界函數限制的所有x[k]的個數。
2、好的限制函數能顯著地減少所生成的結點數。但這樣的限制函數往往計算量較大。是以，在選擇限制函數時通常存在生成結點數與限制函數計算量之間的折衷。
3、重排原理，确定解空間樹的結構，可以決定前三個因素。對于許多問題而言，在搜尋試探時選取x[i]值的順序是任意的。在其它條件相當的前提下，讓可取值最少的x[i]優先将較有效。
4、估算回溯法産生的結點數目，機率方法思想。在解空間樹上産性一條随機的路徑，然後沿此路徑估算解空間樹中滿足限制條件的結點總數m。計算回溯法産生的結點數。
五、回溯法示例
1、裝載問題
2、圖着色問題
3、旅行售貨員問題
4、n-皇後問題
5、批處理作業排程
…
總結
知識點總結
1、回溯法在搜尋嘗試中找問題的解，當不滿足求解條件就"回溯"傳回，嘗試别的路徑。即它采用了一種"走不通就掉頭"的思想，作為其控制結構。
2、用回溯法解問題時：應明确問題的解空間，将解空間組織成樹或圖的形式。
3、回溯法在問題的解空間樹中，按深度優先政策，從根結點出發搜尋解空間樹。當搜尋至解空間樹的任意一點時，利用剪枝函數判斷該結點是否包含問題的解：用限制函數(條件)在擴充結點處剪去不滿足限制的子樹，即剪去得不到可行解的子樹；用目标函數剪去得不到最優解的子樹。
4、遞歸和非遞歸求解架構。
結語
對回溯法的介紹就到這裡啦，希望這篇文章能給予你一些幫助，感謝各位人才的：點贊、收藏和評論，我們下次見。