回溯法也稱為試探法，該方法首先暫時放棄關(guān)于問題規(guī)模大小的限制，并將問題的候選解按某種順序逐一枚舉和檢驗。當發(fā)現(xiàn)當前候選解不可能是解時，就選擇下一個候選解；倘若當前候選解除了還不滿足問題規(guī)模要求外，滿足所有其他要求時，繼續(xù)擴大當前候選解的規(guī)模，并繼續(xù)試探。如果當前候選解滿足包括問題規(guī)模在內(nèi)的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當前候選解，尋找下一個候選解的過程稱為回溯。擴大當前候選解的規(guī)模，以繼續(xù)試探的過程稱為向前試探。 1、回溯法的一般描述 可用回溯法求解的問題P，通常要能表達為：對于已知的由n元組（x1，x2，…，xn）組成的一個狀態(tài)空間E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，給定關(guān)于n元組中的一個分量的一個約束集D，要求E中滿足D的全部約束條件的所有n元組。其中Si是分量xi的定義域，且 |Si| 有限，i=1，2，…，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。 解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計算量是相當大的。 我們發(fā)現(xiàn)，對于許多問題，所給定的約束集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的一個約束，n≥ij。因此，對于約束集D具有完備性的問題P，一旦檢測斷定某個j元組（x1，x2，…，xj）違反D中僅涉及x1，x2，…，xj的一個約束，就可以肯定，以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）都不會是問題P的解，因而就不必去搜索它們、檢測它們?；厮莘ㄕ轻槍@類問題，利用這類問題的上述性質(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層的每一個結(jié)點都有mi個兒子。這mi個兒子到它們的雙親的邊，按從左到右的次序，分別帶權(quán)xi+1(1) ，xi+1(2) ，…，xi+1(mi) ，i=0，1，2，…，n-1。照這種構(gòu)造方式，E中的一個n元組（x1，x2，…，xn）對應(yīng)于T中的一個葉子結(jié)點，T的根到這個葉子結(jié)點的路徑上依次的n條邊的權(quán)分別為x1，x2，…，xn，反之亦然。另外，對于任意的0≤i≤n-1，E中n元組（x1，x2，…，xn）的一個前綴I元組（x1，x2，…，xi）對應(yīng)于T中的一個非葉子結(jié)點，T的根到這個非葉子結(jié)點的路徑上依次的I條邊的權(quán)分別為x1，x2，…，xi，反之亦然。特別，E中的任意一個n元組的空前綴（），對應(yīng)于T的根。 因而，在E中尋找問題P的一個解等價于在T中搜索一個葉子結(jié)點，要求從T的根到該葉子結(jié)點的路徑上依次的n條邊相應(yīng)帶的n個權(quán)x1，x2，…，xn滿足約束集D的全部約束。在T中搜索所要求的葉子結(jié)點，很自然的一種方式是從根出發(fā)，按深度優(yōu)先的策略逐步深入，即依次搜索滿足約束條件的前綴1元組（x1i）、前綴2元組（x1，x2）、…，前綴I元組（x1，x2，…，xi），…，直到i=n為止。 在回溯法中，上述引入的樹被稱為問題P的狀態(tài)空間樹；樹T上任意一個結(jié)點被稱為問題P的狀態(tài)結(jié)點；樹T上的任意一個葉子結(jié)點被稱為問題P的一個解狀態(tài)結(jié)點；樹T上滿足約束集D的全部約束的任意一個葉子結(jié)點被稱為問題P的一個回答狀態(tài)結(jié)點，它對應(yīng)于問題P的一個解。 【問題】 組合問題 問題描述：找出從自然數(shù)1、2、……、n中任取r個數(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、回溯法的方法 對于具有完備約束集D的一般問題P及其相應(yīng)的狀態(tài)空間樹T，利用T的層次結(jié)構(gòu)和D的完備性，在T中搜索問題P的所有解的回溯法可以形象地描述為： 從T的根出發(fā)，按深度優(yōu)先的策略，系統(tǒng)地搜索以其為根的子樹中可能包含著回答結(jié)點的所有狀態(tài)結(jié)點，而跳過對肯定不含回答結(jié)點的所有子樹的搜索，以提高搜索效率。具體地說，當搜索按深度優(yōu)先策略到達一個滿足D中所有有關(guān)約束的狀態(tài)結(jié)點時，即“激活”該狀態(tài)結(jié)點，以便繼續(xù)往深層搜索；否則跳過對以該狀態(tài)結(jié)點為根的子樹的搜索，而一邊逐層地向該狀態(tài)結(jié)點的祖先結(jié)點回溯，一邊“殺死”其兒子結(jié)點已被搜索遍的祖先結(jié)點，直到遇到其兒子結(jié)點未被搜索遍的祖先結(jié)點，即轉(zhuǎn)向其未被搜索的一個兒子結(jié)點繼續(xù)搜索。 在搜索過程中，只要所激活的狀態(tài)結(jié)點又滿足終結(jié)條件，那么它就是回答結(jié)點，應(yīng)該把它輸出或保存。由于在回溯法求解問題時，一般要求出問題的所有解，因此在得到回答結(jié)點后，同時也要進行回溯，以便得到問題的其他解，直至回溯到T的根且根的所有兒子結(jié)點均已被搜索過為止。 例如在組合問題中，從T的根出發(fā)深度優(yōu)先遍歷該樹。當遍歷到結(jié)點（1，2）時，雖然它滿足約束條件，但還不是回答結(jié)點，則應(yīng)繼續(xù)深度遍歷；當遍歷到葉子結(jié)點（1，2，5）時，由于它已是一個回答結(jié)點，則保存（或輸出）該結(jié)點，并回溯到其雙親結(jié)點，繼續(xù)深度遍歷；當遍歷到結(jié)點（1，5）時，由于它已是葉子結(jié)點，但不滿足約束條件，故也需回溯。 3、回溯法的一般流程和技術(shù) 在用回溯法求解有關(guān)問題的過程中，一般是一邊建樹，一邊遍歷該樹。在回溯法中我們一般采用非遞歸方法。下面，我們給出回溯法的非遞歸算法的一般流程： 在用回溯法求解問題，也即在遍歷狀態(tài)空間樹的過程中，如果采用非遞歸方法，則我們一般要用到棧的數(shù)據(jù)結(jié)構(gòu)。這時，不僅可以用棧來表示正在遍歷的樹的結(jié)點，而且可以很方便地表示建立孩子結(jié)點和回溯過程。 例如在組合問題中，我們用一個一維數(shù)組Stack[ ]表示棧。開始棧空，則表示了樹的根結(jié)點。如果元素1進棧，則表示建立并遍歷（1）結(jié)點；這時如果元素2進棧，則表示建立并遍歷（1，2）結(jié)點；元素3再進棧，則表示建立并遍歷（1，2，3）結(jié)點。這時可以判斷它滿足所有約束條件，是問題的一個解，輸出（或保存）。這時只要棧頂元素（3）出棧，即表示從結(jié)點（1，2，3）回溯到結(jié)點（1，2）。
讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價值的長期合作伙伴，公司提供的服務(wù)項目有：域名注冊、網(wǎng)站空間、營銷軟件、網(wǎng)站建設(shè)、杜集網(wǎng)站維護、網(wǎng)站推廣。
Java語言提供兩種異常處理機制：捕獲異常和聲明拋棄異常。
1、捕獲異常：
（1）在Java程序運行過程中系統(tǒng)得到一個異常對象是，它將會沿著方法的調(diào)用棧逐層回溯，尋找處理這一異常的代碼。
（2）找到能夠處理這種類型異常的方法后，運行時系統(tǒng)把當前異常交給這個方法處理；如果找不到可以捕獲異常的方法，則運行時系統(tǒng)將終止，相應(yīng)的Java程序也將退出。
（3）捕獲異常是通過try-catch-finally語句實現(xiàn)的。語法為：
try{
...
}catch(ExceptionName1e){
...
}catch(ExceptionName2e){
...
}
...
}finally{
...
}
2、聲明拋棄異常：
（1）當Java程序運行時系統(tǒng)得到一個異常對象時，如果一個方法并不知道如何處理所出現(xiàn)的異常，則可在方法聲明時，聲明拋棄異常。
（2）聲明拋棄異常是在一個方法聲明中的throws子句中指明的。如：
publicintread()throwsIOException{
...
}
其中throwsIOException就是聲明拋棄異常，throws后可以跟多個異常類型。
擴展資料：
程序設(shè)計語言的異常機制：
1、多數(shù)語言的異常機制的語法是類似的：用throw或raise拋出一個異常對象（Java或C++等）或一個特殊可擴展的枚舉類型的值（如Ada語言）；
2、異常處理代碼的作用范圍用標記子句（try或begin開始的語言作用域）標示其起始，以第一個異常處理子句（catch,except,resuce等）標示其結(jié)束；可連續(xù)出現(xiàn)若干個異常處理子句，每個處理特定類型的異常。
3、某些語言允許else子句，用于無異常出現(xiàn)的情況。更多見的是finally,ensure子句，無論是否出現(xiàn)異常它都將執(zhí)行，用于釋放異常處理所需的一些資源。
（1）C++異常處理是資源獲取即初始化（Resource-Acquisition-Is-Initialization）的基礎(chǔ)。
（2）C語言一般認為是不支持異常處理的。Perl語言可選擇支持結(jié)構(gòu)化異常處理（structuredexceptionhandling）。
（3）Python語言對異常處理機制是非常普遍深入的，所以想寫出不含try,except的程序非常困難。
參考資料來源：
百度百科-異常處理
數(shù)組實現(xiàn)的堆棧：ArrayStack.java
public class ArrayStack {
Object[] m_elements;
int m_size;
public ArrayStack(int len) {
m_elements = new Object[len];
m_size = 0;
}
public ArrayStack() {
this(50);
}
// insert onto stack
public void push(Object element) {
m_elements[m_size] = element;
m_size++;
}
// return and remove the top element
public Object pop() {
if (!this.isEmpty()) {
Object obj = m_elements[m_size - 1];
m_elements[m_size - 1] = null;
m_size--;
return obj;
} else {
return null;
}
}
// return the top element
public Object top() {
if (!this.isEmpty()) {
return m_elements[m_size - 1];
} else {
return null;
}
}
// return 1 -- is empty
// return 0 -- is not empty
public boolean isEmpty() {
return this.size() == 0;
}
public int size() {
return m_size;
}
}
使用鏈表實現(xiàn)(單鏈表) ：
public class Stacklist {
Node m_header;
int m_size;
public ListStack() {
m_header = null;
m_size = 0;
}
public void push(Object value) {
m_header = new Node(value, m_header);
}
public Object pop() {
if (!this.isEmpty()) {
throw new RuntimeException("Stack underflow");
}
Object obj = m_header.element;
m_header = m_header.next;
return obj;
}
// return reference to most recently added elemenet
public Object peek() {
if (!this.isEmpty()) {
throw new RuntimeException("Stack underflow");
}
return m_header.element;
}
public boolean isEmpty() {
return this.size() == 0;
}
//return the number of the queue's elements;
public int size() {
return m_size;
}
}
鏈表的需要用到一個結(jié)點類 Node.java 代碼如下
public class Node {
Object element;
Node next;
public Node(Object theElement) {
this(theElement, null);
}
public Node(Object theElement, Node n) {
element = theElement;
next = n;
}
public Object getElement() {
return element;
}
public void setElement(Object element) {
this.element = element;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
這是異常產(chǎn)生的調(diào)用堆?；厮?，幫助你快速定位代碼有問題的地方。
它明確的告訴你，錯誤是怎樣一步一步發(fā)生的。
簡單的說：Java把內(nèi)存劃分成兩種：一種是棧內(nèi)存，一種是堆內(nèi)存。
在函數(shù)中定義的一些基本類型的變量和對象的引用變量都在函數(shù)的棧內(nèi)存中分配。當在一段代碼塊定義一個變量時，Java就在棧中為這個變量分配內(nèi)存空間，當超過變量的作用域后，Java會自動釋放掉為該變量所分配的內(nèi)存空間，該內(nèi)存空間可以立即被另作他用。
堆內(nèi)存用來存放由new創(chuàng)建的對象和數(shù)組。在堆中分配的內(nèi)存，由Java虛擬機的自動垃圾回收器來管理。在堆中產(chǎn)生了一個數(shù)組或?qū)ο蠛?，還可以在棧中定義一個特殊的變量，讓棧中這個變量的取值等于數(shù)組或?qū)ο笤诙褍?nèi)存中的首地址，棧中的這個變量就成了數(shù)組或?qū)ο蟮囊米兞俊Ｒ米兞烤拖喈斢谑菫閿?shù)組或?qū)ο笃鸬囊粋€名稱，以后就可以在程序中使用棧中的引用變量來訪問堆中的數(shù)組或?qū)ο?/p>
Java回溯沒接觸過。這題是剛開始下一狀態(tài)為不可使用狀態(tài)，想要實現(xiàn)如何從綠-》紅-》黑的變換嗎？方向是單向的
重慶分公司
重慶分公司
