回溯法首先將問題p的n元組的狀態空間e表示成一棵高為n的帶權有序樹t，把在e中求問題p的所有解轉化為在t中搜尋問題p的所有解。樹t類似於檢索樹，它可以這樣構造：
設si中的元素可排成xi(1) ，xi(2) ，…，xi(mi-1) ，|si| =mi，i=1，2，…，n。從根開始，讓t的第i層的每乙個結點都有mi個兒子。這mi個兒子到它們的雙親的邊，按從左到右的次序，分別帶權xi+1(1) ，xi+1(2) ，…，xi+1(mi) ，i=0，1，2，…，n-1。
照這種構造方式，e中的乙個n元組（x1，x2，…，xn）對應於t中的乙個葉子結點，t的根到這個葉子結點的路徑上依次的n條邊的權分別為x1，x2，…，xn，反之亦然。另外，對於任意的0≤i≤n-1，e中n元組（x1，x2，…，xn）的乙個字首i元組（x1，x2，…，xi）對應於t中的乙個非葉子結點，t的根到這個非葉子結點的路徑上依次的i條邊的權分別為x1，x2，…，xi，反之亦然。特別，e中的任意乙個n元組的空前綴（），對應於t的根。
因而，在e中尋找問題p的乙個解等價於在t中搜尋乙個葉子結點，要求從t的根到該葉子結點的路徑上依次的n條邊相應帶的n個權x1，x2，…，xn滿足約束集d的全部約束。在t中搜尋所要求的葉子結點，很自然的一種方式是從根出發，按深度優先的策略逐步深入，即依次搜尋滿足約束條件的字首1元組（x1i）、字首2元組（x1，x2）、…，字首i元組（x1，x2，…，xi），…，直到i=n為止。
在回溯法中，上述引入的樹被稱為問題p的狀態空間樹；樹t上任意乙個結點被稱為問題p的狀態結點；樹t上的任意乙個葉子結點被稱為問題p的乙個解狀態結點；樹t上滿足約束集d的全部約束的任意乙個葉子結點被稱為問題p的乙個回答狀態結點，它對應於問題p的乙個解。
【問題】 組合問題
問題描述：找出從自然數1、2、……、n中任取r個數的所有組合。
例如n=5，r=3的所有組合為：
（1）1、2、3 （2）1、2、4 （3）1、2、5
（4）1、3、4 （5）1、3、5 （6）1、4、5
（7）2、3、4 （8）2、3、5 （9）2、4、5
（10）3、4、5
則該問題的狀態空間為：
e= 其中：s=
約束集為： x1 顯然該約束集具有完備性。
問題的狀態空間樹t：
2、回溯法的方法
對於具有完備約束集d的一般問題p及其相應的狀態空間樹t，利用t的層次結構和d的完備性，在t中搜尋問題p的所有解的回溯法可以形象地描述為：
從t的根出發，按深度優先的策略，系統地搜尋以其為根的子樹中可能包含著回答結點的所有狀態結點，而跳過對肯定不含回答結點的所有子樹的搜尋，以提高搜尋效率。具體地說，當搜尋按深度優先策略到達乙個滿足d中所有有關約束的狀態結點時，即「啟用」該狀態結點，以便繼續往深層搜尋；否則跳過對以該狀態結點為根的子樹的搜尋，而一邊逐層地向該狀態結點的祖先結點回溯，一邊「殺死」其兒子結點已被搜尋遍的祖先結點，直到遇到其兒子結點未被搜尋遍的祖先結點，即轉向其未被搜尋的乙個兒子結點繼續搜尋。
在搜尋過程中，只要所啟用的狀態結點又滿足終結條件，那麼它就是回答結點，應該把它輸出或儲存。由於在回溯法求解問題時，一般要求出問題的所有解，因此在得到回答結點後，同時也要進行回溯，以便得到問題的其他解，直至回溯到t的根且根的所有兒子結點均已被搜尋過為止。
例如在組合問題中，從t的根出發深度優先遍歷該樹。當遍歷到結點（1，2）時，雖然它滿足約束條件，但還不是回答結點，則應繼續深度遍歷；當遍歷到葉子結點（1，2，5）時，由於它已是乙個回答結點，則儲存（或輸出）該結點，並回溯到其雙親結點，繼續深度遍歷；當遍歷到結點（1，5）時，由於它已是葉子結點，但不滿足約束條件，故也需回溯。
3、回溯法的一般流程和技術
在用回溯法求解有關問題的過程中，一般是一邊建樹，一邊遍歷該樹。在回溯法中我們一般採用非遞迴方法。下面，我們給出回溯法的非遞迴演算法的一般流程：
在用回溯法求解問題，也即在遍歷狀態空間樹的過程中，如果採用非遞迴方法，則我們一般要用到棧的資料結構。這時，不僅可以用棧來表示正在遍歷的樹的結點，而且可以很方便地表示建立孩子結點和回溯過程。
例如在組合問題中，我們用乙個一維陣列stack[ ]表示棧。開始棧空，則表示了樹的根結點。如果元素1進棧，則表示建立並遍歷（1）結點；這時如果元素2進棧，則表示建立並遍歷（1，2）結點；元素3再進棧，則表示建立並遍歷（1，2，3）結點。
這時可以判斷它滿足所有約束條件，是問題的乙個解，輸出（或儲存）。這時只要棧頂元素（3）出棧，即表示從結點（1，2，3）回溯到結點（1，2）。
【問題】 組合問題
問題描述：找出從自然數1，2，…，n中任取r個數的所有組合。
採用回溯法找問題的解，將找到的組合以從小到大順序存於a[0]，a[1]，…，a[r-1]中，組合的元素滿足以下性質：
（1） a[i+1]>a[i]，後乙個數字比前乙個大；
（2） a[i]-i<=n-r+1。
按回溯法的思想，找解過程可以敘述如下：
首先放棄組合數個數為r的條件，候選組合從只有乙個數字1開始。因該候選解滿足除問題規模之外的全部條件，擴大其規模，並使其滿足上述條件（1），候選組合改為1，2。繼續這一過程，得到候選組合1，2，3。
該候選解滿足包括問題規模在內的全部條件，因而是乙個解。在該解的基礎上，選下乙個候選解，因a[2]上的3調整為4，以及以後調整為5都滿足問題的全部要求，得到解1，2，4和1，2，5。由於對5不能再作調整，就要從a[2]回溯到a[1]，這時，a[1]=2，可以調整為3，並向前試探，得到解1，3，4。
重複上述向前試探和向後回溯，直至要從a[0]再回溯時，說明已經找完問題的全部解。按上述思想寫成程式如下：
【程式】
# define maxn 100
int a[maxn];
void comb(int m,int r)
else
if (i==0)
return;
a[--i]++;
}} while (1)
}main()
【問題】 填字遊戲
問題描述：在3×3個方格的方陣中要填入數字1到n（n≥10）內的某9個數字，每個方格填乙個整數，似的所有相鄰兩個方格內的兩個整數之和為質數。試求出所有滿足這個要求的各種數字填法。
可用試探發找到問題的解，即從第乙個方格開始，為當前方格尋找乙個合理的整數填入，並在當前位置正確填入後，為下一方格尋找可填入的合理整數。如不能為當前方格找到乙個合理的可填證書，就要回退到前一方格，調整前一方格的填入數。當第九個方格也填入合理的整數後，就找到了乙個解，將該解輸出，並調整第九個的填入的整數，尋找下乙個解。
為找到乙個滿足要求的9個數的填法，從還未填乙個數開始，按某種順序（如從小到大的順序）每次在當前位置填入乙個整數，然後檢查當前填入的整數是否能滿足要求。在滿足要求的情況下，繼續用同樣的方法為下一方格填入整數。如果最近填入的整數不能滿足要求，就改變填入的整數。
如對當前方格試盡所有可能的整數，都不能滿足要求，就得回退到前一方格，並調整前一方格填入的整數。如此重複執行擴充套件、檢查或調整、檢查，直到找到乙個滿足問題要求的解，將解輸出。
回溯法找乙個解的演算法：
while ((!ok||m!=n)&&(m!=0))
if (m!=0) 輸出解;
else 輸出無解報告；
}如果程式要找全部解，則在將找到的解輸出後，應繼續調整最後位置上填放的整數，試圖去找下乙個解。相應的演算法如下：
回溯法找全部解的演算法：
else 擴充套件;
else 調整;
ok=檢查前m個整數填放的合理性;
} while (m!=0);
}為了確保程式能夠終止，調整時必須保證曾被放棄過的填數序列不會再次實驗，即要求按某種有許模型生成填數序列。給解的候選者設定乙個被檢驗的順序，按這個順序逐一形成候選者並檢驗。從小到大或從大到小，都是可以採用的方法。
如擴充套件時，先在新位置填入整數1，調整時，找當前候選解中下乙個還未被使用過的整數。將上述擴充套件、調整、檢驗都編寫成程式，細節見以下找全部解的程式。
【程式】
# include <>
# define n 12
void write(int a[ ])
scanf(「%*c」);
}int b[n+1];
int a[10];
int isprime(int m)
; if (m==1||m%2=0) return 0;
for (i=0;primes[i]>0;i++)
if (m==primes[i]) return 1;
for (i=3;i*i<=m;)
return 1;
}int checkmatrix[ ][3]=,,,,,
2,4,-1},,,};
int selectnum(int start)
{ int j;
for (j=start;j<=n;j++)
程式及演算法流程設計例項
程式設計與演算法分析 題目1 給定10個整數，求出其最大值並輸出。演算法分析 利用計算機迴圈程式，用陣列a 存放題中的10個整數，借助中間變數temp，通過一次氣泡排序，把最大的數求出來 先將a 0 和a 1 比較，如果a 0 程式設計 int main for inti 0 iif a 0 tem...
離職率常見演算法介紹
離職率在離職管理中常見的演算法有四種 度量1選取了期初人數和期末人數的平均值作為樣本，預設該平均值是企業期間內人力資源管理所面對的平均被管理人數，其離職率相應用來衡量期間內離職管理的效果。這種離職率較為適用於人力保持穩定或者穩定增長的企業在中短期 半年，季度，月 衡量離職率。但是，由於企業在乙個完整...
常見論證方法及作用
1 舉例論證 通過舉具體的事例加以論證，從而使論證更具體 更有說服力。答題格式 使用了舉例論證的論證方法，舉 概括事例 證明了 如果有分論點，則寫出它證明的分論點，否則寫中心論點 從而使論證更具體理會有說服力。2 道理論證 通過講道理的方式證明論點，使論證更概括更深入。答題格式 使用了道理論證的論證...