回溯法也稱為試探法，該方法首先暫時(shí)放棄關(guān)于問題規(guī)模大小的限制，并將問題的候選解按某種順序逐一枚舉和檢驗(yàn)。當(dāng)發(fā)現(xiàn)當(dāng)前候選解不可能是解時(shí)，就選擇下一個(gè)候選解；倘若當(dāng)前候選解除了還不滿足問題規(guī)模要求外，滿足所有其他要求時(shí)，繼續(xù)擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探。如果當(dāng)前候選解滿足包括問題規(guī)模在內(nèi)的所有要求時(shí)，該候選解就是問題的一個(gè)解。在回溯法中，放棄當(dāng)前候選解，尋找下一個(gè)候選解的過程稱為回溯。擴(kuò)大當(dāng)前候選解的規(guī)模，以繼續(xù)試探的過程稱為向前試探。 1、回溯法的一般描述 可用回溯法求解的問題P，通常要能表達(dá)為：對(duì)于已知的由n元組（x1，x2，…，xn）組成的一個(gè)狀態(tài)空間E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，給定關(guān)于n元組中的一個(gè)分量的一個(gè)約束集D，要求E中滿足D的全部約束條件的所有n元組。其中Si是分量xi的定義域，且 |Si| 有限，i=1，2，…，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個(gè)解。 解問題P的最樸素的方法就是枚舉法，即對(duì)E中的所有n元組逐一地檢測(cè)其是否滿足D的全部約束，若滿足，則為問題P的一個(gè)解。但顯然，其計(jì)算量是相當(dāng)大的。 我們發(fā)現(xiàn)，對(duì)于許多問題，所給定的約束集D具有完備性，即i元組（x1，x2，…，xi）滿足D中僅涉及到x1，x2，…，xi的所有約束意味著j（ji）元組（x1，x2，…，xj）一定也滿足D中僅涉及到x1，x2，…，xj的所有約束，i=1，2，…，n。換句話說，只要存在0≤j≤n-1，使得（x1，x2，…，xj）違反D中僅涉及到x1，x2，…，xj的約束之一，則以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）一定也違反D中僅涉及到x1，x2，…，xi的一個(gè)約束，n≥ij。因此，對(duì)于約束集D具有完備性的問題P，一旦檢測(cè)斷定某個(gè)j元組（x1，x2，…，xj）違反D中僅涉及x1，x2，…，xj的一個(gè)約束，就可以肯定，以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）都不會(huì)是問題P的解，因而就不必去搜索它們、檢測(cè)它們?；厮莘ㄕ轻槍?duì)這類問題，利用這類問題的上述性質(zhì)而提出來的比枚舉法效率更高的算法。 回溯法首先將問題P的n元組的狀態(tài)空間E表示成一棵高為n的帶權(quán)有序樹T，把在E中求問題P的所有解轉(zhuǎn)化為在T中搜索問題P的所有解。樹T類似于檢索樹，它可以這樣構(gòu)造： 設(shè)Si中的元素可排成xi(1) ，xi(2) ，…，xi(mi-1) ，|Si| =mi，i=1，2，…，n。從根開始，讓T的第I層的每一個(gè)結(jié)點(diǎn)都有mi個(gè)兒子。這mi個(gè)兒子到它們的雙親的邊，按從左到右的次序，分別帶權(quán)xi+1(1) ，xi+1(2) ，…，xi+1(mi) ，i=0，1，2，…，n-1。照這種構(gòu)造方式，E中的一個(gè)n元組（x1，x2，…，xn）對(duì)應(yīng)于T中的一個(gè)葉子結(jié)點(diǎn)，T的根到這個(gè)葉子結(jié)點(diǎn)的路徑上依次的n條邊的權(quán)分別為x1，x2，…，xn，反之亦然。另外，對(duì)于任意的0≤i≤n-1，E中n元組（x1，x2，…，xn）的一個(gè)前綴I元組（x1，x2，…，xi）對(duì)應(yīng)于T中的一個(gè)非葉子結(jié)點(diǎn)，T的根到這個(gè)非葉子結(jié)點(diǎn)的路徑上依次的I條邊的權(quán)分別為x1，x2，…，xi，反之亦然。特別，E中的任意一個(gè)n元組的空前綴（），對(duì)應(yīng)于T的根。 因而，在E中尋找問題P的一個(gè)解等價(jià)于在T中搜索一個(gè)葉子結(jié)點(diǎn)，要求從T的根到該葉子結(jié)點(diǎn)的路徑上依次的n條邊相應(yīng)帶的n個(gè)權(quán)x1，x2，…，xn滿足約束集D的全部約束。在T中搜索所要求的葉子結(jié)點(diǎn)，很自然的一種方式是從根出發(fā)，按深度優(yōu)先的策略逐步深入，即依次搜索滿足約束條件的前綴1元組（x1i）、前綴2元組（x1，x2）、…，前綴I元組（x1，x2，…，xi），…，直到i=n為止。 在回溯法中，上述引入的樹被稱為問題P的狀態(tài)空間樹；樹T上任意一個(gè)結(jié)點(diǎn)被稱為問題P的狀態(tài)結(jié)點(diǎn)；樹T上的任意一個(gè)葉子結(jié)點(diǎn)被稱為問題P的一個(gè)解狀態(tài)結(jié)點(diǎn)；樹T上滿足約束集D的全部約束的任意一個(gè)葉子結(jié)點(diǎn)被稱為問題P的一個(gè)回答狀態(tài)結(jié)點(diǎn)，它對(duì)應(yīng)于問題P的一個(gè)解。 【問題】 組合問題 問題描述：找出從自然數(shù)1、2、……、n中任取r個(gè)數(shù)的所有組合。 例如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 則該問題的狀態(tài)空間為： E={（x1，x2，x3）∣xi∈S ，i=1，2，3 } 其中：S={1，2，3，4，5} 約束集為： x1x2x3 顯然該約束集具有完備性。 問題的狀態(tài)空間樹T： 2、回溯法的方法 對(duì)于具有完備約束集D的一般問題P及其相應(yīng)的狀態(tài)空間樹T，利用T的層次結(jié)構(gòu)和D的完備性，在T中搜索問題P的所有解的回溯法可以形象地描述為： 從T的根出發(fā)，按深度優(yōu)先的策略，系統(tǒng)地搜索以其為根的子樹中可能包含著回答結(jié)點(diǎn)的所有狀態(tài)結(jié)點(diǎn)，而跳過對(duì)肯定不含回答結(jié)點(diǎn)的所有子樹的搜索，以提高搜索效率。具體地說，當(dāng)搜索按深度優(yōu)先策略到達(dá)一個(gè)滿足D中所有有關(guān)約束的狀態(tài)結(jié)點(diǎn)時(shí)，即“激活”該狀態(tài)結(jié)點(diǎn)，以便繼續(xù)往深層搜索；否則跳過對(duì)以該狀態(tài)結(jié)點(diǎn)為根的子樹的搜索，而一邊逐層地向該狀態(tài)結(jié)點(diǎn)的祖先結(jié)點(diǎn)回溯，一邊“殺死”其兒子結(jié)點(diǎn)已被搜索遍的祖先結(jié)點(diǎn)，直到遇到其兒子結(jié)點(diǎn)未被搜索遍的祖先結(jié)點(diǎn)，即轉(zhuǎn)向其未被搜索的一個(gè)兒子結(jié)點(diǎn)繼續(xù)搜索。 在搜索過程中，只要所激活的狀態(tài)結(jié)點(diǎn)又滿足終結(jié)條件，那么它就是回答結(jié)點(diǎn)，應(yīng)該把它輸出或保存。由于在回溯法求解問題時(shí)，一般要求出問題的所有解，因此在得到回答結(jié)點(diǎn)后，同時(shí)也要進(jìn)行回溯，以便得到問題的其他解，直至回溯到T的根且根的所有兒子結(jié)點(diǎn)均已被搜索過為止。 例如在組合問題中，從T的根出發(fā)深度優(yōu)先遍歷該樹。當(dāng)遍歷到結(jié)點(diǎn)（1，2）時(shí)，雖然它滿足約束條件，但還不是回答結(jié)點(diǎn)，則應(yīng)繼續(xù)深度遍歷；當(dāng)遍歷到葉子結(jié)點(diǎn)（1，2，5）時(shí)，由于它已是一個(gè)回答結(jié)點(diǎn)，則保存（或輸出）該結(jié)點(diǎn)，并回溯到其雙親結(jié)點(diǎn)，繼續(xù)深度遍歷；當(dāng)遍歷到結(jié)點(diǎn)（1，5）時(shí)，由于它已是葉子結(jié)點(diǎn)，但不滿足約束條件，故也需回溯。 3、回溯法的一般流程和技術(shù) 在用回溯法求解有關(guān)問題的過程中，一般是一邊建樹，一邊遍歷該樹。在回溯法中我們一般采用非遞歸方法。下面，我們給出回溯法的非遞歸算法的一般流程： 在用回溯法求解問題，也即在遍歷狀態(tài)空間樹的過程中，如果采用非遞歸方法，則我們一般要用到棧的數(shù)據(jù)結(jié)構(gòu)。這時(shí)，不僅可以用棧來表示正在遍歷的樹的結(jié)點(diǎn)，而且可以很方便地表示建立孩子結(jié)點(diǎn)和回溯過程。 例如在組合問題中，我們用一個(gè)一維數(shù)組Stack[ ]表示棧。開始?？眨瑒t表示了樹的根結(jié)點(diǎn)。如果元素1進(jìn)棧，則表示建立并遍歷（1）結(jié)點(diǎn)；這時(shí)如果元素2進(jìn)棧，則表示建立并遍歷（1，2）結(jié)點(diǎn)；元素3再進(jìn)棧，則表示建立并遍歷（1，2，3）結(jié)點(diǎn)。這時(shí)可以判斷它滿足所有約束條件，是問題的一個(gè)解，輸出（或保存）。這時(shí)只要棧頂元素（3）出棧，即表示從結(jié)點(diǎn)（1，2，3）回溯到結(jié)點(diǎn)（1，2）。
成都創(chuàng)新互聯(lián)公司是專業(yè)的東區(qū)網(wǎng)站建設(shè)公司，東區(qū)接單;提供成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作,網(wǎng)頁設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行東區(qū)網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來合作!
N皇后問題的非遞歸迭代回溯法java代碼實(shí)現(xiàn)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class NQueen {
static int n; // 皇后個(gè)數(shù)
static int[] x; // 當(dāng)前解如{0，2，4，1，3}分別代表第1、2、3、4列的行值
static int totle; // 可行方案?jìng)€(gè)數(shù)
public static void main(String[] args) {
int input = 0; //輸入n值
int sum = 0; //可行方案?jìng)€(gè)數(shù)
String temp; //臨時(shí)存儲(chǔ)輸入值
System.out.println("請(qǐng)輸入N后問題的N值：");
try {
BufferedReader br = new BufferedReader(new InputStreamReader(
System.in));
temp = br.readLine();
input = Integer.parseInt(temp); //將輸入值轉(zhuǎn)換為int保存
if(input=0){
throw new IOException("別輸負(fù)數(shù)好不？");
}
System.out.println("輸入的數(shù)是：" + input);
sum = nQueen(input); //調(diào)用nqueen方法
System.out.println("可行方案?jìng)€(gè)數(shù)為：" + sum); //輸出sum
} catch (IOException e) {
System.out.println(e.getMessage());
}catch (NumberFormatException e){
System.out.println("請(qǐng)輸入數(shù)字。。。");
}
}
private static int nQueen(int input) {
n = input; //把輸入給全局變量n
totle = 0; //初始化totle
x = new int[n + 1];
for (int i = 0; i = n; i++)
x[i] = 0; //初始化x
backtrack(); //調(diào)用回溯算法
return totle;
}
private static void backtrack() {
int k = 1;
while (k 0) {
x[k] += 1; //第k列皇后向下移一行
while ((x[k] = n) !(place(k))){ //如果當(dāng)前第k列皇后未出界或者和其他皇后沖突
x[k] += 1; //第k列皇后向下移一行繼續(xù)尋找
System.out.println("在第"+k+"行 "+"第"+x[k]+"列放置皇后");
System.out.print("當(dāng)前方案為 ");
for(int i=1;i=k;i++) //打印尋找策略
System.out.print(x[i]+" ");
System.out.println();
}
if (x[k] = n) //找到一個(gè)值并且未出界
if (k == n) { //已是最后一列說明已找到一個(gè)方案
totle++;
System.out.print("可行方案為： ");
for (int i = 1; i = n; i++)
System.out.print(x[i] + " ");
System.out.println();
} else { //不是最后一列故尋找下一列
k++;
x[k] = 0;
}
else //找到的值已經(jīng)出界，回退到上一列
k--;
}
}
//判斷皇后是否沖突
private static boolean place(int k) {
for (int j = 1; j k; j++)
if ((Math.abs(k - j) == Math.abs(x[j] - x[k])) || (x[j] == x[k]))
return false;
return true;
}
}
遞歸的精華就在于大問題的分解，要學(xué)會(huì)宏觀的去看問題，如果這個(gè)大問題可以分解為若干個(gè)性質(zhì)相同的規(guī)模更小的問題，那么我們只要不斷地去做分解，當(dāng)這些小問題分解到我們能夠輕易解決的時(shí)候，大問題也就能迎刃而解了。如果你能獨(dú)立寫完遞歸創(chuàng)建二叉樹，前序、中序、后序遞歸遍歷以及遞歸計(jì)算二叉樹的最大深度，遞歸就基本能掌握了。回溯本人用得很少，僅限于八皇后問題，所以幫不上啥了。
你main方法也沒有加上，這樣吧，我給你看代碼，這個(gè)比較容易理解。
package?com.aice.queen;
public?class?Queen{
//同欄是否有皇后，1表示有
private?int[]column;
?
//右上至左下是否有皇后
private?int[]rup;
?
//左上至右下是否有皇后
private?int[]lup;
?
//解答
private?int[]queen;
?
//解答編號(hào)
private?int?num;
public?Queen(){
column?=?new?int[8+1];
rup?=new?int[(2*8)+1];
lup?=?new?int[(2*8)+1];
?
for(int?i?=?1;i=8;i++)
column[i]=1;
for(int?i?=?1;i=(2*8);i++)
rup[i]?=?lup[i]?=?1;
queen?=?new?int[8+1];
}
public?void?backtrack(int?i){
if(i8){
showAnswer();
}else{
for(int?j=1;j=8;j++){
if((column[j]==1)(rup[i+j]==1)
(lup[i-j+8]==1)){
queen[i]=j;
//設(shè)定為占用
column[j]=rup[i+j]=lup[i-j+8]=0;
backtrack(i+1);
column[j]=rup[i+j]=lup[i-j+8]=1;
}
}
}
}
protected?void?showAnswer(){
num++;
System.out.println("\n解答"+num);
?
for(int?y=1;y=8;y++){
for(int?x=1;x=8;x++){
if(queen[y]==x){
System.out.print("Q");
}else{
System.out.print(".");
}
}
System.out.println();
}
}
public?static?void?main(String[]args){
Queen?queen?=?new?Queen();
queen.backtrack(1);
}
}
Java回溯沒接觸過。這題是剛開始下一狀態(tài)為不可使用狀態(tài)，想要實(shí)現(xiàn)如何從綠-》紅-》黑的變換嗎？方向是單向的
因?yàn)槟惆裯和c 定義為static ,而且初始化為0,。數(shù)組也為靜態(tài)的,一個(gè)類中靜態(tài)的變量在這個(gè)類加載的時(shí)候就會(huì)執(zhí)行，所以當(dāng)你這類加載的時(shí)候，你的數(shù)組static int[] v = new int[n];
static int[] w = new int[n];
就已經(jīng)初始化完畢，而且數(shù)組大小為0。在main方法里動(dòng)態(tài)改變n的值是改變不了已經(jīng)初始化完畢的數(shù)組的大小的，因?yàn)榻M已經(jīng)加載完畢。
我建議你可以在定義n,c是就為其賦初值。比如（static int n=2 static int c=3）
重慶分公司
重慶分公司
