目录
对什么区域进行垃圾回收？
什么情况下回收？
四种引用：
JVM内存分配策略：
1.对象优先在Eden分配
2.大对象直接进入老年代
3.动态对象年龄判断
4.长期存活的对象将进入老年代
5.空间分配担保
垃圾回收算法：
１．标记-清除算法
２．复制算法
３．标记-整理法
４．分代回收算法
什么是STW?
精确式GC：
savepoint :安全点
抢先式中断：
主动式中断：
安全区:
垃圾收集器
Serial收集器(新生代收集器)
ParNew收集器(新生代收集器)
Parallel Scavenge收集器(新生代收集器)
Serial Old收集器(老年代收集器)
Parallel Old (老年代的多线程版本)
CMS(Concurrent Mark Sweep)收集器
G1收集器(Gabage First)

对什么区域进行垃圾回收？

１．堆
２．方法区中静态属性引用的对象
３．方法区中常量引用的对象
４．本地方法栈中JNI引用的对象

例如： private native void sort(int[] array);


栈是线程私有的，不需要回收

什么情况下回收？

１．当引用计数器为０(循环调用则会出问题)
２．可达性分析遍历不到的对象进行回收．

四种引用：

强引用：可达性分析不可达的情况下，会被GC
软引用：内存不足时，会被GC
弱引用：只能存活到下一次GC前
虚引用：不会对对象的生命周期有任何影响，无法通过它获取对象实例，唯一的作用就是在对象被GC回收前收到一个通知．

JVM内存分配策略：
1.对象优先在Eden分配
大多数情况下，对象在新生代Eden区中分配。
2.大对象直接进入老年代
大对象是指，需要大量连续内存空间的java对象(字符串，数组)．-XX:PretenureSizeThreshold可以令大于这个值的对象直接在老年代分配内存，可以避免在Survivor区域发生大量的内存复制．

XX:PretenureSizeThreshold 该参数只能在ParNew和Serial两款收集器使用.

3.动态对象年龄判断
如果Survivor空间中的相同年龄的所有对象大小的总和大于Survivor空间的一半，大于该年龄的对象直接进入老年代．
4.长期存活的对象将进入老年代
对象在Survivor每熬过一次GC，对象年龄就会加１，当年龄到达默认值15，则进入老年代
5.空间分配担保
检测老年代的可用连续空间是否大于即将晋升到老年代的对象的大小，如果大于，则进行一次MinorGC，如果小于，或者设置不允许冒险，那次时需进行一次FullGC．
垃圾回收算法：
１．标记-清除算法
分为标记和清除两个阶段，首先标记出所有需要回收的对象，在标记完成后统一回收所有被标记的对象.



缺点：

效率不高
会产生不连续的内存碎片，空间碎片太多可能会导致以后在程 序运行过程中需要分配较大对象时，无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作

２．复制算法
将可用内存分为大小相等的两个区域，每次只使用其中一片区域．当这一片区域用完了，再将还活着的对象复制到另一块区域，将之前区域的对象清理掉．


缺点：

１．内存缩小为原来的一半，内存利用率太低
２．如果对象存活率高，复制浪费时间

３．标记-整理法
分为标记和整理两个阶段，先标记出所有需要回收的对象，然后将存活对象整理到内存的一端．然后清除回收的对象


４．分代回收算法

年轻代采用标记清除和整理算法
老年代采用复制算法

在新生代 中，每次垃圾收集时都发现有大批对象死去，只有少量存活，那就选用复制算法，只需要付出少量存活对象的复制成本就可以完成收集。而老年代中因为对象存活率高、没有额外空间对它进行分配担保，就使用“标记—整理”算法来进行回收。
什么是STW?
STW(Stop The World)：正常执行的用户线程全部停止．
精确式GC：
HotSpot===>OopMap
准确式GC,当执行系统停顿下来后，并不需要一个不漏地检查完所有 执行上下文(例如栈帧中的本地变量表)和全局(例如常量或类静态属性)的引用位置，虚拟机应当是有办法直接得知哪些地方存放着对象引用。在 HotSpot的实现中，是使用一组称为OopMap的数据结构来达到这个目的的，在类加载完成的时候，HotSpot就把对象内什么偏移量上是什么类型的数据计算出来，在JIT编译过程中，也会在特定的位置记录下栈和寄存器中哪些位置是引用。这样，GC在扫描时就可以直接得知这些信息了。
savepoint :安全点
在OopMap的协助下，HotSpot可以快速且准确地完成GC Roots枚举，但一个很现实的问 题随之而来：可能导致引用关系变化，或者说OopMap内容变化的指令非常多，如果为每一 条指令都生成对应的OopMap，那将会需要大量的额外空间，这样GC的空间成本将会变得很 高。实际上，HotSpot也的确没有为每条指令都生成OopMap，前面已经提到，只是在“特定的 位置”记录了这些信息，这些位置称为安全点（Safepoint），即程序执行时并非在所有地方都 能停顿下来开始GC，只有在到达安全点时才能暂停。Safepoint的选定既不能太少以致于让 GC等待时间太长，也不能过于频繁以致于过分增大运行时的负荷.
对于Sefepoint，另一个需要考虑的问题是如何在GC发生时让所有线程（这里不包括执行 JNI调用的线程）都“跑”到最近的安全点上再停顿下来。有两种方式:
抢先式中断：
先将线程主动中断，没有执行到指定安全点的据需执行，直到安全点．(用得少,几乎没有)

缺点：

Thread.sleep() wait(),有可能跑不到中断点．
主动式中断：
当GC需要中断线程时，不直接对线程进行操作，而是设置一个标志，让用户线程去检查，然后中断．
安全区:
使用Safepoint似乎已经完美地解决了如何进入GC的问题，但实际情况却并不一定。 Safepoint机制保证了程序执行时，在不太长的时间内就会遇到可进入GC的Safepoint。但是， 程序“不执行”的时候呢？所谓的程序不执行就是没有分配CPU时间，典型的例子就是线程处 于Sleep状态或者Blocked状态，这时候线程无法响应JVM的中断请求，“走”到安全的地方去 中断挂起，JVM也显然不太可能等待线程重新被分配CPU时间。对于这种情况，就需要安全 区域（Safe Region）来解决。 安全区域是指在一段代码片段之中，引用关系不会发生变化。在这个区域中的任意地方 开始GC都是安全的。
垃圾收集器
如果说收集算法是内存回收的方法论，那么垃圾收集器就是内存回收的具体实现。

连线表示可以搭配使用.


Serial收集器(新生代收集器)

开启参数：-XX:+UseSerialGC

单线程的收集器，"单线程"的意义并不仅仅说明他只会使用一个CPU或者一条收集线程去完成收集垃圾操作，最重要的是他在进行垃圾收集的时候，必须暂停其他线程的工作，直到它收集结束．新生代和老年代都会Stop The World.

就好比: “你妈妈在给你打扫房间的时候，肯定也会让你老老实实地在椅子上或者房间 外待着，如果她一边打扫，你一边乱扔纸屑，这房间还能打扫完？”
ParNew收集器(新生代收集器)

Serial收集器的多线程版本，除了使用多条线程进行垃圾收集之外，其余行为还包括Serial收集器的可用控制参数

(-XX:SurvivorRatio , -XX:PretenureSizeThreshold ,-XX:HandlePromotionFailure)，收集算法，Stop The World，对象分配规则，回收策略等都与Serial收集器完全一样.
对新生代并行收集，对老年代还是单线程收集．
Parallel Scavenge收集器(新生代收集器)
开启参数:-XX:+UseParallelGC
Parallel Scavenge关注点： 可控的吞吐量　(与ParNew相比可控制GC时用户现场停顿时间)

吞吐量计算公式： 运行用户代码时间/(运行用户代码时间＋垃圾收集时间) 例:虚拟机总共运行了100分钟，其中垃圾收集花掉1分钟，那吞吐量就是99%
停顿时间越短就越适合需要与用户交互的程序，良好的响应速度能提升用户体验，而高吞吐量则可以高效的利用CPU时间，尽快完成程序的运算任务
Parallel Scavenge提供参数用于精确控制吞吐量

-XX:MaxGCPauseMills  //最大垃圾收集停顿时间，收集器将尽可能地保证内存回收花费的时间不超过设定值
-XX:GCTimeRatio     //吞吐量大小,也就是垃圾收集时间占总时间的比率，相当于是吞吐量的倒数
-XX:+UseAdaptiveSizePolicy  //内存调优委托给虚拟机管理,这是一个开关参数，当这个参数打开之后，就不需要手工指定新生代的大小（-Xmn）、 Eden与Survivor区的比例（-XX：SurvivorRatio）、晋升老年代对象年龄（-XX： PretenureSizeThreshold）等细节参数了，虚拟机会根据当前系统的运行情况收集性能监控信 息，动态调整这些参数以提供最合适的停顿时间或者最大的吞吐量，这种调节方式称为GC 自适应的调节策略。

Serial Old收集器(老年代收集器)
Serial Old是Serial收集器的老年代版本，它同样是一个单线程收集器，使用“标记-整理”算法。
图可看Serial收集器
Parallel Old (老年代的多线程版本)

Parallel Old是Parallel Scavenge收集器的老年代版本，使用多线程和“标记-整理”算法
CMS(Concurrent Mark Sweep)收集器


开启: -XX:+UseConcMarkSweepGC
（CMS收集器是一种以获得最短回收停顿时间为目标的收集器．CMS收集器是基于标记清除算法实现的．整个过程分为4个步骤：

初始标记(CMS initial Mark)  ：标记一下GC Roots能直接关联到的对象(GCRoot和它的子节点)，速度很快
并发标记(CMS concurrent Mark)　：对未标记的节点进行标记
重新标记(CMS Remark)　：修正并发标记期间因用户程序继续运作而导致标记产生变动的那一部分对象的标记记录
并发清除(CMS concurrent sweep)　：　最后进行对象清除

在初始标记和重新标记会STW

由于整个过程中耗时最长的并发标记和并发清除过程收集器线程都可以与用户线程一起 工作，所以，从总体上来说，CMS收集器的内存回收过程是与用户线程一起并发执行的。

CMS默认回收的线程= (CPU数量＋３)/4
3个明显的缺点：


CMS收集器对CPU资源非常敏感

在并发标记的时候,占用了一部分线程(CPU资源)导致应用程序变慢


CMS收集器无法处理浮动垃圾（Floating Garbage），可能出现“Concurrent Mode Failure”失败而导致另一次Full GC的产生。

由于CMS并发清理阶段用户线程还在运行着，伴随程序运行自然就还会有新的垃圾不断产生，这一部分垃圾出现在标记过程之后，CMS无法 在当次收集中处理掉它们，只好留待下一次GC时再清理掉。


有大量空间碎片产生

因为该收集器是基于标记-清除算法实现的.所以会意味着产生大量空间碎片.

为了解决这个问题，CMS收集器提供了一个-XX：+UseCMSCompactAtFullCollection开 关参数（默认就是开启的），用于在CMS收集器顶不住要进行FullGC时开启内存碎片的合并整理过程，内存整理的过程是无法并发的，空间碎片问题没有了，但停顿时间不得不变长。
还提供了另外一个参数-XX：CMSFullGCsBeforeCompaction，这个参数是用于设置执行多少次不压缩的Full GC后，跟着来一次带压缩的（默认值为0，表示每次进入Full GC时都进行碎片整理）。




G1收集器(Gabage First)

G1能充分利用多CPU、多核环境下的硬件优势，使用多个CPU（CPU或者 CPU核心）来缩短Stop-The-World停顿的时间，部分其他收集器原本需要停顿Java线程执行的 GC动作，G1收集器仍然可以通过并发的方式让Java程序继续执行。
G1收集器之所以能建立可预测的停顿时间模型，是因为它可以有计划地避免在整个Java 堆中进行全区域的垃圾收集。G1跟踪各个Region里面的垃圾堆积的价值大小（回收所获得的 空间大小以及回收所需时间的经验值），在后台维护一个优先列表，每次根据允许的收集时间，优先回收价值最大的Region（这也就是Garbage-First名称的来由）。这种使用Region划分 内存空间以及有优先级的区域回收方式，保证了G1收集器在有限的时间内可以获取尽可能高 的收集效率。
仍然属于分代收集器，只不过将内存划分为多个Regin

特点： 空间整合

算法： 既属于标记整理，又属于复制
分为四个阶段:

初始标记阶段:

仅仅只是标记一下GC Roots能直接关联到的对象，并且修改 TAMS（Next Top at Mark Start）的值，让下一阶段用户程序并发运行时，能在正确可用的 Region中创建新对象，这阶段需要停顿线程，但耗时很短。
并发标记阶段:

是从GC Root开始对堆中对象进行可达性分析，找出存活的对象，这阶段耗时较长，但可与用户程序并发执行。
最终标记阶段:

为了修正在并发标记期间因用户程序继续运作而导致标记产生变动的那一部分标记记录，虚拟机将这段时间对象变化记录在线程Remembered Set Logs里面,最终标记阶段需要把Remembered Set Logs的数据合并到Remembered Set中，这阶段需要停顿线程，但是可并行执行。
筛选回收阶段:

首先对各个Region的回收价值和成本进行排序， 根据用户所期望的GC停顿时间来制定回收计划，这个阶段其实也可以做到与用户程序一起并发执行，但是因为只回收一部分Region，时间是用户可控制的，而且停顿用户线程将大幅提高收集效率。

Young GC:

１．扫描根GCRoots

２．更新RememberSet记录回收对象的数据结构

３．检测RememberSer哪些是要从年轻代到老年代的

４．Copy对象，要么去to区，要么去老年代

５．清理工作

MixedGC
与其他GC收集器相比，G1具备如下特 点。

并行与并发：G1能充分利用多CPU、多核环境下的硬件优势，使用多个CPU（CPU或者 CPU核心）来缩短Stop-The-World停顿的时间
分代收集：与其他收集器一样，分代概念在G1中依然得以保留。虽然G1可以不需要其他收集器配合就能独立管理整个GC堆，但它能够采用不同的方式去处理新创建的对象和已 经存活了一段时间、熬过多次GC的旧对象以获取更好的收集效果。
空间整合：与CMS的“标记—清理”算法不同，G1从整体来看是基于“标记—整理”算法实现的收集器，从局部（两个Region之间）上来看是基于“复制”算法实现的，但无论如何，这 两种算法都意味着G1运作期间不会产生内存空间碎片，收集后能提供规整的可用内存。这种 特性有利于程序长时间运行，分配大对象时不会因为无法找到连续内存空间而提前触发下一 次GC。
可预测的停顿：这是G1相对于CMS的另一大优势，降低停顿时间是G1和CMS共同的关 注点，但G1除了追求低停顿外，还能建立可预测的停顿时间模型，能让使用者明确指定在一 个长度为M毫秒的时间片段内，消耗在垃圾收集上的时间不得超过N毫秒.

1、什么是搜索？
       搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。在竞赛中，搜索法还被当做“救命稻草”——大多数问题都可以使用搜索来谋取部分分数。        搜索策略有很多，常见的有：深度优先搜索、宽度优先搜索、迭代加深搜索等。搜索算法的设计主要是一下几个步骤：确定状态和扩展方式、选用合适的搜索方式、优化。

2、、深度优先搜索与宽度优先搜索        搜索算法设计过程中，主要需要考虑的问题有两个：状态与状态之间的关系（即扩展方式）。如果将状态对应顶点，状态之间的关系对应边，原搜索问题可抽象成一棵搜索树。初始状态对应根节点，目标状态对应目标节点，搜索算法即找到一条从根节点到目标节点的路径（一个可行解）。详见下图：

    不同的搜索算法相当于搜索树的不同遍历方式。最常见的深度优先搜索（DFS
 -- Depth First Search）和宽度优先搜索（BFS -- Breadth First Search）对应着搜索树的两种遍历方式，如下图：



深度优先搜索所遵循的搜索策略是尽可能“深”地遍历搜索树，对应树的前序遍历。在深度优先搜索中，对于当前节点，如果有可行子节点，则向下遍历，否则回溯。        宽度优先搜索所遵循的搜索策略是尽可能“广”的遍历搜索树，对应树的分层遍历。在宽度优先搜索中，每次都先将搜索树某一层的所有结点全部访问完毕后再访问下一层，首次达到的目标节点通常就是最优解。

 什么是分支限界法？

        广度优先搜索是—种依照“由近及远，按层展开”的策略进行的枚举算法，也意味着它需要遍历整个状态空间图，导致算法效率不高。给定一个问题的状态间表示，设计搜索算法时需要考虑以下两个事实

       ◆并不是所有的分支都包含可行解

       ◆并不是所有的分支都包含最优解

      分支限界算法=广度优先搜索+剪枝策略

      分支限界算法需要设计合适的剪枝策略，限制某些分支的扩展，尽量避免不必要的搜索。常用的剪枝策略包括两大类

     1.约束函数剪枝：根据约束条件，状态空间图中的部分状态可能是不合法的。因此，在状态空间图中以不合法状态为根的分支不包含可行解，故其分支可以剪枝。

     2.限界函数剪枝：这种策略一般应用于最优化问题。假设搜索算法当前访问的状态为S，且存在一个判定函数：它能判定以S为根的分支不包含最优解，因此该分支可以剪除而无需搜索



    约束函数剪枝可以剪除状态空间图中的不可行解

    限界函数剪枝用于剪除状态空间图中的可行但是非最优的解

             

经典应用

       装载问题

       0-1背包问题

       旅行商问题

       最短路径问题

 

装载问题：

 

TSP问题：

借鉴：https://blog.csdn.net/qq_35649945/article/details/93056866

问题描述：

       旅行家要旅行n个城市，已知各城市之间的路程。要求选定一条从驻地出发经过每个城市一次，最后回到驻地的路线，使总的路程最小。例如：从如图中的无向带权图G=(V,E)中的1号点出发，经过图中的每个点，并且不能重复，然后回到1号点，要求经过的路径长度是最短的（即求图中 路径 ）。

                                          

算法思想：

定义解空间树后，对解空间进行搜索，需要先找到限界条件和约束条件

（1）约束条件：如果带权邻接矩阵maps[i][j]不为无穷，即<i,j>能走通，否则继续寻找能走通的路。队列不为空。

（2）限界条件：cl<bestw,cl初始值为0，bestw初始值为无穷。

   cl表示当前已走过的路径长度。
搜索过程：

       将满足条件（即上一层节点的路径长度+上层节点到扩展节点的长度<bestw）的节点加入队列，为了加快搜索速度，使用优先队列，优先队列中的优先级为已走过的路径长度cl,cl值越小，越优先。

                                   

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
class Node1{
	int  cl; //已经走过的路径长度
	int id;//表示所在解空间树的第几层
	int x[]=new int[105];//存储路径
	public Node1(int cl,int id){
		this.cl=cl;
		this.id=id;
	}
}
public class Main {
	   static final int MAX=105;
	   static final int INF=(int)1e9;
	   //优先队列存储,每次自动排序，cl小的优先处理
	   static PriorityQueue<Node1> q=new PriorityQueue<Node1>(new Comparator<Node1>() {
			    	      public int compare(Node1 o1, Node1 o2) {
			    	    	       if(o1.cl>o2.cl) return 1;
			    	    	       else return -1;
			    	      }
				});
	   static int g[][]=new int[MAX][MAX];
	   static int bestw;//最短路径长度
	   static int best[]=new int[MAX];//最短路径
	   static int n,m;//n个点，m条边
	   static void bfs(){
		         Node1 node=new Node1(0,2);//初始经过的路径为0,起点1位于第树的第二层
		         for(int i=1;i<=n;i++)
		        	    node.x[i]=i;
		         q.add(node);
		         while(!q.isEmpty()){
		        	      Node1 newnode=q.poll();
		        	      int t=newnode.id;
		        	      if(t==n){
		        	    	     if(g[newnode.x[t-1]][newnode.x[n]]!=INF && g[newnode.x[n]][newnode.x[1]]!=INF){
		        	    	    	     if(newnode.cl+g[newnode.x[t-1]][newnode.x[n]]+g[newnode.x[n]][newnode.x[1]]<bestw){
		        	    	    	    	      bestw=newnode.cl+g[newnode.x[t-1]][newnode.x[n]]+g[newnode.x[n]][newnode.x[1]];
		        	    	    	    	      for(int i=1;i<=n;i++){
		        	    	    	    	    	     best[i]=newnode.x[i];
		        	    	    	    	      }
		        	    	    	     }
		        	    	     }
		        	      }
		        	      if(newnode.cl>=bestw) continue;//约束条件 两点不可达
		        	      //对当前节点进行扩展子节点
		        	      for(int j=t;j<=n;j++){
		        	    	     if(newnode.cl+g[newnode.x[t-1]][newnode.x[j]]<bestw){ //限界条件
		        	    	    	     int c=newnode.cl+g[newnode.x[t-1]][newnode.x[j]];
		        	    	    	     node=new Node1(c,t+1);
		        	    	    	     for(int i=1;i<=n;i++){
		        	    	    	    	    node.x[i]=newnode.x[i];
		        	    	    	     }
		        	    	    	     //通过交换实现路径节点更新
		        	    	    	     int tmp=node.x[t];
		        	    	    	     node.x[t]=node.x[j];
		        	    	    	     node.x[j]=tmp;
		        	    	    	     q.add(node);
		        	    	     }
		        	      }
		         }
	   }
       public static void main(String[] args) {
    	       Scanner scan=new Scanner(System.in);
		       n=scan.nextInt();
		       m=scan.nextInt();
		       for(int i=0;i<n;i++){
		    	   Arrays.fill(g[i], INF);
		       }
		       for(int i=0;i<m;i++){
		    	   int a=scan.nextInt();
		    	   int b=scan.nextInt();
		    	   int c=scan.nextInt();
		    	   g[a][b]=g[b][a]=c;
		       }
		       bestw=INF;//最短路径初始为0
		       bfs();
		       System.out.println("最短路径长度:"+bestw);
		       for(int i=1;i<=n;i++){
		    	    System.out.println(best[i]);
		       }
		       System.out.println(best[1]);
	  }
}
//4 6
//1 2 15
//1 3 30
//1 4 5
//2 3 6
//2 4 12
//3 4 3



 

回溯法（backtrack）
有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。回溯法的基本做法是 搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。
回溯法在问题的解空间树中，按 深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
算法过程
回溯法会用深度优先的方式搜索解空间，并在搜索的过程中用剪枝函数减去不可能产生最优解的子树，从而避免无效搜索。剪枝函数有两个，用 约束函数（constrain function） 可以在扩展结点处剪去不满足约束的子树；用
限界函数（bound function） 可以剪去得不到最优解的子树。
用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为
h(n)，则回溯法所需的计算空间通常为
O(h(n))。而显式地存储整个解空间则需要
O(2h(n))（子集树）
 或 O(h(n)!)（排列树）
 的内存空间。
回溯法的伪代码如下：
// 子集树
void backtrack (int t) {
    if (t > n) return output(x); 
    for (int i = f(n,t); i <= g(n,t); i++) {
        x[t] = h(i);
        if (constraint(t) && bound(t))
            backtrack(t+1); 
    }
}

// 排列树
void backtrack (int t) {
    if (t > n) return output(x); 
    for (int i = f(n,t); i <= g(n,t); i++) {
        swap(x[t], x[i])
        if (constraint(t) && bound(t))
            backtrack(t+1); 
        swap(x[t), x[i])
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
解空间
回溯法希望一个问题的解能够表示成一个 n
 元向量 (x1,x2,...,xn)
 的形式，这个向量叫做问题的 解向量。解向量的约束分成了显约束和隐约束。显约束 指的是分量 
xi
 的取值约束，比如 0-1 背包只能取 0 或者 1 两个值。隐约束 指的是为满足问题的解对不同的分量之间施加的约束。对于问题的一个实例，解向量满足显示约束条件的所有多元组，构成了该实例的一个
解空间。
生成问题状态的基本方法
在回溯法搜索的过程中，有序树的结点根据状态可以分成下面三种：
扩展结点：一个正在产生儿子的结点称为扩展结点
活结点：一个自身已生成但其儿子还没有全部生成的节点称做活结点
死结点：一个所有儿子已经产生的结点称做死结点 
生成问题状态有两种方法
深度优先的问题状态生成法
如果对一个扩展结点 R，一旦产生了它的一个儿子 C，就把 C 当做新的扩展结点。在完成对子树 C （以 C 为根的子树）的穷尽搜索之后，将 R 重新变成扩展结点，继续生成 R 的下一个儿子（如果存在）。
宽度优先的问题状态生成法
在一个扩展结点变成死结点之前，它一直是扩展结点。
为了避免生成那些不可能产生最佳解的问题状态（需要剪枝），要不断地利用限界函数来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。
回溯法效率分析
回溯法的效率在很大程度上依赖于一下的因素：
产生 xk
 的时间
满足显约束的 xk
 值的个数
计算约束函数 constraint 的时间
计算上界函数 bound 的时间
满足约束函数和上界函数约束的所有 xk
 的个数
好的约束函数能够显著地减少生成的节点的个数，但是这样的约束函数往往计算量较大，因此选择约束函数时，会在生成节点个数和约束函数计算量之间的折中。
举例
0-1 背包问题（解空间：子集树）
旅行售货员问题（解空间：排列树） TSP 即旅行商问题
装载问题：把 n 个集装箱，装载到两个轮船中去；
批处理作业调度
符号三角形问题
n 后问题
最大团问题
图的 m 着色问题
圆排列问题
连续邮资问题
分支限界法
和回溯法的区别
回溯法 
是找出解空间树中满足约束条件的所有解
深度优先搜索
分支限界法 
是找出解空间中满足约束条件的一个解，或者是某种意义下的最优解
广度优先搜索或者是最小耗费（最大效益）
常见的两种分支限界法
队列式（FIFO）分支限界法
优先队列分支限界法
搜索策略
分支限界法的搜索策略：在拓展节点处，首先会生成其所有儿子节点（分支），然后再从当前的活节点表中选择下一个扩展节点。为了有效地选择下一扩展节点，以加速搜索进程，在每一个活节点处，计算一个函数值，并根据这些已计算出的函数值，在当前活节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间树上最优解推进。
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。
举例
0-1 背包问题（子集树）
旅行商问题（用到了最小堆和优先队列，排列数）
单源最短路径问题
装载问题（队列式分支限界法；优先队列分支限界法 ）
布线问题
最大团问题
电路板排列问题
批处理作业调度问题