锐客网

  1. 首页 > 睿知 > it技术 > >

Java代码堆栈回溯 java堆栈分析

IT技术结点

JAVA回溯编程，如何实现图中的功能Java回溯没接触过 。这题是刚开始下一状态为不可使用状态Java代码堆栈回溯，想要实现如何从绿-》红-》黑Java代码堆栈回溯的变换吗？方向是单向的
java回溯法如何执行回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制 ， 并将问题的候选解按某种顺序逐一枚举和检验 。当发现当前候选解不可能是解时 ， 就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探 。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解 。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯 。扩大当前候选解的规模，以继续试探的过程称为向前试探 。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异常处理的机制有哪几种Java语言提供两种异常处理机制：捕获异常和声明抛弃异常；
1）捕获异常：在Java程序运行过程中系统得到一个异常对象是，它将会沿着方法的调用栈逐层回溯，寻找处理这一异常的代码 。找到能够处理这种类型异常的方法后，运行时系统把当前异常交给这个方法处理；如果找不到可以捕获异常的方法 ， 则运行时系统将终止，相应的Java程序也将退出 。捕获异常是通过try-catch-finally语句实现的 。语法为：
try{
...
}catch(ExceptionName1 e){
...
}catch(ExceptionName2 e){
...
}
...
}finally{
...
}
2)声明抛弃异常：当Java程序运行时系统得到一个异常对象时，如果一个方法并不知道如何处理所出现的异常，则可在方法声明时，声明抛弃异常 。声明抛弃异常是在一个方法声明中的throws子句中指明的 。如：
public int read() throws IOException{
...
}
其中throws IOException就是声明抛弃异常，throws后可以跟多个异常类型 。
java中异常是用来处理程序出现错误的情况，那为什么不直接用if语句，把可能出现的错误放在if中呢?java中异常是用来处理程序出现错误的情况，不直接用if语句，把可能出现的错误放在if中的原因：因为有些错误是人们不能预料的 ， 比如内存溢出等，所以还是需要try/catch一下 。
（1）在Java程序运行过程中系统得到一个异常对象是，它将会沿着方法的调用栈逐层回溯，寻找处理这一异常的代码 。
（2）找到能够处理这种类型异常的方法后，运行时系统把当前异常交给这个方法处理；如果找不到可以捕获异常的方法，则运行时系统将终止，相应的Java程序也将退出 。
概述
异常处理 ， 是编程语言或计算机硬件里的一种机制，用于处理软件或信息系统中出现的异常状况（即超出程序正常执行流程的某些特殊条件） 。
各种编程语言在处理异常方面具有非常显著的不同点（错误检测与异常处理区别在于：错误检测是在正常的程序流中，处理不可预见问题的代码，例如一个调用操作未能成功结束） 。某些编程语言有这样的函数：当输入存在非法数据时不能被安全地调用，或者返回值不能与异常进行有效的区别 。
【Java代码堆栈回溯 java堆栈分析】关于Java代码堆栈回溯和java堆栈分析的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站 。

    推荐阅读


    上一篇：如何在老团子服务器上畅玩？ 老团子服务器怎么玩

    下一篇：mysql命令行换行 mysql语句怎么换行