189 8069 5689
回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。 1、回溯法的一般描述 可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且 |Si| 有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。 解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。 我们发现，对于许多问题，所给定的约束集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的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。 回溯法首先将问题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={（x1，x2，x3）∣xi∈S ，i=1，2，3 } 其中：S={1，2，3，4，5} 约束集为： x1x2x3 显然该约束集具有完备性。 问题的状态空间树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）。
让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：域名注册、网站空间、营销软件、网站建设、杜集网站维护、网站推广。
Java语言提供两种异常处理机制：捕获异常和声明抛弃异常。
1、捕获异常：
（1）在Java程序运行过程中系统得到一个异常对象是，它将会沿着方法的调用栈逐层回溯，寻找处理这一异常的代码。
（2）找到能够处理这种类型异常的方法后，运行时系统把当前异常交给这个方法处理；如果找不到可以捕获异常的方法，则运行时系统将终止，相应的Java程序也将退出。
（3）捕获异常是通过try-catch-finally语句实现的。语法为：
try{
...
}catch(ExceptionName1e){
...
}catch(ExceptionName2e){
...
}
...
}finally{
...
}
2、声明抛弃异常：
（1）当Java程序运行时系统得到一个异常对象时，如果一个方法并不知道如何处理所出现的异常，则可在方法声明时，声明抛弃异常。
（2）声明抛弃异常是在一个方法声明中的throws子句中指明的。如：
publicintread()throwsIOException{
...
}
其中throwsIOException就是声明抛弃异常，throws后可以跟多个异常类型。
扩展资料：
程序设计语言的异常机制：
1、多数语言的异常机制的语法是类似的：用throw或raise抛出一个异常对象（Java或C++等）或一个特殊可扩展的枚举类型的值（如Ada语言）；
2、异常处理代码的作用范围用标记子句（try或begin开始的语言作用域）标示其起始，以第一个异常处理子句（catch,except,resuce等）标示其结束；可连续出现若干个异常处理子句，每个处理特定类型的异常。
3、某些语言允许else子句，用于无异常出现的情况。更多见的是finally,ensure子句，无论是否出现异常它都将执行，用于释放异常处理所需的一些资源。
（1）C++异常处理是资源获取即初始化（Resource-Acquisition-Is-Initialization）的基础。
（2）C语言一般认为是不支持异常处理的。Perl语言可选择支持结构化异常处理（structuredexceptionhandling）。
（3）Python语言对异常处理机制是非常普遍深入的，所以想写出不含try,except的程序非常困难。
参考资料来源：
百度百科-异常处理
数组实现的堆栈：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;
}
}
使用链表实现(单链表) ：
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;
}
}
链表的需要用到一个结点类 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;
}
}
这是异常产生的调用堆栈回溯，帮助你快速定位代码有问题的地方。
它明确的告诉你，错误是怎样一步一步发生的。
简单的说：Java把内存划分成两种：一种是栈内存，一种是堆内存。
在函数中定义的一些基本类型的变量和对象的引用变量都在函数的栈内存中分配。当在一段代码块定义一个变量时，Java就在栈中为这个变量分配内存空间，当超过变量的作用域后，Java会自动释放掉为该变量所分配的内存空间，该内存空间可以立即被另作他用。
堆内存用来存放由new创建的对象和数组。在堆中分配的内存，由Java虚拟机的自动垃圾回收器来管理。在堆中产生了一个数组或对象后，还可以在栈中定义一个特殊的变量，让栈中这个变量的取值等于数组或对象在堆内存中的首地址，栈中的这个变量就成了数组或对象的引用变量。引用变量就相当于是为数组或对象起的一个名称，以后就可以在程序中使用栈中的引用变量来访问堆中的数组或对象
Java回溯没接触过。这题是刚开始下一状态为不可使用状态，想要实现如何从绿-》红-》黑的变换吗？方向是单向的