算法一：分治法
基本概念
1. 把一个简单的问题分成两个或更多的雷同或类似的子问题，再把子问题分成更小的子问题……直到最初子问题能够简略的间接求解，原问题的解即子问题的解的合并。
2. 分治策略是对于一个规模为 n 的问题，若该问题能够容易地解决（比如说规模 n 较小）则间接解决，否则将其合成为 k 个规模较小的子问题，这些子问题相互独立且与原问题模式雷同，递归地解这些子问题，而后将各子问题的解合并失去原问题的解。
实用状况
1)该问题的规模放大到肯定的水平就能够容易地解决
2) 该问题能够合成为若干个规模较小的雷同问题，即该问题具备最优子结构性质。
3)利用该问题合成出的子问题的解能够合并为该问题的解；
该问题所合成出的各个子问题是互相独立的，即子问题之间不蕴含公共的子子问题。
分治法的复杂性剖析
一个分治法将规模为 n 的问题分成 k 个规模为 n/m 的子问题去解。设合成阀值 n0=1，且 adhoc 解规模为 1 的问题消耗 1 个单位工夫。再设将原问题合成为 k 个子问题以及用 merge 将 k 个子问题的解合并为原问题的解需用 f(n)个单位工夫。用 T(n)示意该分治法解规模为 |P|= n 的问题所需的计算工夫，则有：
T（n）= k T(n/m)+f(n)
通过迭代法求得方程的解：
递归方程及其解只给出 n 等于 m 的方幂时 T(n)的值，然而如果认为 T(n)足够平滑，那么由 n 等于 m 的方幂时 T(n)的值能够预计 T(n)的增长速度。通常假设 T(n)是枯燥回升的，从而当 mi≤n<mi+ 1 时，T(mi)≤T(n)<T(mi+1)。
分治法例题：合并排序和疾速排序
public class 分治_合并排序 {
/**
* 函数阐明：在数组被拆分当前进行合并
*/
static void Merge(int a[], int left, int middle, int rigth) {
// 定义左端数组大小
int n1 = middle - left+1;
int n2 = rigth - middle;
// 初始化数组，分配内存
int bejin[] = new int[n1];
int end[] = new int[n2];
// 数组赋值
for(int i = 0; i < n1; i++)
bejin[i] = a[left + i];
for(int i = 0; i < n2; i++)
end[i] = a[middle+1+i];
// 用 key 做原数组索引，没调用一次函数从新给原数组付一次值
int i = 0, j = 0, key;
for(key = left; key <= rigth; key++){if(n1>i&&n2>j&&i < n1 && bejin[i] <= end[j])
a[key] = bejin[i++];
else if(n1>i&&n2>j&&j < n2 && bejin[i] >= end[j])
a[key] = end[j++];
else if(i == n1 && j < n2)
a[key] = end[j++];
else if(j == n2 && i < n1)
a[key] = bejin[i++];
}
}
/**
* 差分数组区间，一直分支
*/
static void MergeSort(int a[],int left,int rigth) {
int middle=0;
if(left<rigth) {middle =(rigth+left)/2;
MergeSort(a, left, middle);
MergeSort(a, middle+1, rigth);
Merge(a, left, middle, rigth);
}
}
public static void main(String[] args) {int a[]= {85,3,52,9,7,1,5,4};
MergeSort(a, 0,7);
for(int i=0;i<8;i++) {System.out.print(" "+a[i]);
}
}
}public class 分治_疾速排序 {
/**
* 替换函数，i，j 为数组索引
*/
static void swap(int A[], int i, int j)
{int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
/**
* 选取一个关键字 (key) 作为枢轴，个别取整组记录的第一个数 / 最初一个，这里采纳选取序列最初一个数为枢轴。* 设置两个变量 left = 0;right = N - 1;
* 从 left 始终向后走，直到找到一个大于 key 的值，right 从后至前，直至找到一个小于 key 的值，而后替换这两个数。* 反复第三步，始终往后找，直到 left 和 right 相遇，这时将 key 搁置 left 的地位即可。* @return
*/
static int PartSort(int[] array,int left,int right)
{int key = array[right];// 定义基准
int count=right;// 保留 rigth 值
while(left < right)// 避免数组越界
{while(left < right && array[left] <= key)
{++left;}
while(left < right && array[right] >= key)
{--right;}
swap(array,left,right);
}
swap(array,right,count);
return right;
}
/**
* 分治思维，递归调用
*/
static void QuickSort(int array[],int left,int right)
{if(left >= right)// 示意曾经实现一个组
{return;}
int index = PartSort(array,left,right);// 枢轴的地位
QuickSort(array,left,index - 1);
QuickSort(array,index + 1,right);
}
public static void main(String[] args) {int a[]= {1,5,-5,54,15,67,16,23};
QuickSort(a,0,7);
for(int i=0;i<a.length;i++) {System.out.print(" "+a[i]);
}
System.out.print("\n");
}
}算法心得
作为分治法里很典型的一种算法，合并排序和疾速排序充沛展示了分治法的思维，分而治之，在此次编程应用此办法中，给我的领会是程序简略分为两局部，第一局部，一直“拆”，放大子问题规模，达到最优子结构。而后合并，在合并过程中，应为子问题足够小，容易计算，再者一直合并子问题答案，最终求出问题解。
算法二：贪婪算法
一、基本概念：
所谓贪婪算法是指，在对问题求解时，总是做出在以后看来是最好的抉择。也就是说，不从整体最优上加以思考，他所做出的仅是在某种意义上的部分最优解。
贪婪算法没有固定的算法框架，算法设计的要害是贪婪策略的抉择。必须留神的是，贪婪算法不是对所有问题都能失去整体最优解，抉择的贪婪策略必须具备无后效性，即某个状态当前的过程不会影响以前的状态，只与以后状态无关。
所以对所采纳的贪婪策略肯定要仔细分析其是否满足无后效性。
二、贪婪算法的基本思路：
1. 建设数学模型来形容问题。
2. 把求解的问题分成若干个子问题。
3. 对每一子问题求解，失去子问题的部分最优解。
4. 把子问题的解部分最优解合成原来解问题的一个解。
三、贪婪算法实用的问题
贪婪策略实用的前提是：部分最优策略能导致产生全局最优解。
实际上，贪婪算法实用的状况很少。个别，对一个问题剖析是否实用于贪婪算法，能够先抉择该问题下的几个理论数据进行剖析，就可做出判断。
四、贪婪算法的实现框架
从问题的某一初始解登程；
while（能朝给定总指标前进一步）
利用可行的决策，求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
五、贪婪策略的抉择
因为用贪婪算法只能通过解部分最优解的策略来达到全局最优解，因而，肯定要留神判断问题是否适宜采纳贪婪算法策略，找到的解是否肯定是问题的最优解。
贪婪策略例题：prim 算法
import java.util.*;
public class 贪婪算法_prim 算法 {
static int MAX = Integer.MAX_VALUE;
public static void main(String[] args) {
// 定义无向图矩阵
int[][] map = new int[][] {{ 0, 1, 6, 2},
{1, 0, 3, 2},
{6, 3, 0, 1},
{2, 2, 1, 0}
};
prim(map, map.length);
}
public static void prim(int[][] graph, int n){
// 定义节点名字
char[] c = new char[]{'A','B','C','D'};
int[] lowcost = new int[n]; // 到新汇合的最小权
int[] mid= new int[n];// 存取前驱结点
List<Character> list=new ArrayList<Character>();// 用来存储退出结点的程序
int i, j, min, minid , sum = 0;
// 初始化辅助数组
for(i=1;i<n;i++)
{lowcost[i]=graph[0][i];
mid[i]=0;
}
list.add(c[0]);
// 一共须要退出 n - 1 个点
for(i=1;i<n;i++)
{
min=MAX;
minid=0;
// 每次找到间隔汇合最近的点
for(j=1;j<n;j++)
{if(lowcost[j]!=0&&lowcost[j]<min)
{min=lowcost[j];
minid=j;
}
}
if(minid==0) return;
list.add(c[minid]);
lowcost[minid]=0;
sum+=min;
System.out.println(c[mid[minid]] + "到" + c[minid] + "权值：" + min);
// 退出该点后，更新其它点到汇合的间隔
for(j=1;j<n;j++)
{if(lowcost[j]!=0&&lowcost[j]>graph[minid][j])
{lowcost[j]=graph[minid][j];
mid[j]=minid;
}
}
System.out.print("\n");
}
System.out.println("sum:" + sum);
}
}
算法心得
Prim 算法是贪心策略的一种很好的体现，在实现 prim 算法中，意识到，贪心策略是在做当先抉择的状况下，后行囊括所有的抉择贮存好，在依据贪心策略，选出最合乎的步骤进行上来。尽管贪心策略比拟迅捷，应为它不须要估算所有状况（相似回溯），但应为每次所求只是部分最优解，所以后果不肯定是最优解，算法准确性在与贪心策略的选取好坏，所以也具备肯定的局限性！
算法三：动静布局算法
一、基本概念
动静布局过程是：每次决策依赖于以后状态，又随即引起状态的转移。一个决策序列就是在变动的状态中产生进去的，所以，这种多阶段最优化决策解决问题的过程就称为动静布局。
二、根本思维与策略
根本思维与分治法相似，也是将待求解的问题合成为若干个子问题（阶段），按程序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的部分解，通过决策保留那些有可能达到最优的部分解，抛弃其余部分解。顺次解决各子问题，最初一个子问题就是初始问题的解。
因为动静布局解决的问题少数有重叠子问题这个特点，为缩小反复计算，对每一个子问题只解一次，将其不同阶段的不同状态保留在一个二维数组中。
与分治法最大的差异是：适宜于用动静规划法求解的问题，经合成后失去的子问题往往不是相互独立的（即下一个子阶段的求解是建设在上一个子阶段的解的根底上，进行进一步的求解）。
三、实用的状况
能采纳动静布局求解的问题的个别要具备 3 个性质：
(1) 最优化原理：如果问题的最优解所蕴含的子问题的解也是最优的，就称该问题具备最优子结构，即满足最优化原理。
(2) 无后效性：即某阶段状态一旦确定，就不受这个状态当前决策的影响。也就是说，某状态当前的过程不会影响以前的状态，只与以后状态无关。
（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被屡次应用到。（该性质并不是动静布局实用的必要条件，然而如果没有这条性质，动静布局算法同其余算法相比就不具备劣势）
算法实例：背包问题
public class 动静布局_背包问题 {public static void main(String[] args) {
// 物品价值, 分量, 和背包承重
int v[]={0,8,10,6,3,7,2};
int w[]={0,4,6,2,2,5,1};
int c=12;
// 定义二位数组动静布局背包价值和分量
int m[][]=new int[v.length][c+1];
for (int i = 1; i <v.length; i++) {for (int j = 1; j <=c; j++) {if(j>=w[i])
m[i][j]=m[i-1][j-w[i]]+v[i]>m[i-1][j]?m[i-1][j-w[i]]+v[i]:m[i-1][j];
else
m[i][j]=m[i-1][j];
}
}
int max=0;
for (int i = 0; i <v.length; i++) {for (int j = 0; j <=c; j++) {if(m[i][j]>max)
max=m[i][j];
}
}
System.out.println(max);
}
}四、算法心得
在此次编程中，使用动态内存算法解决背包问题，发先所需调配空间量比拟大，在做背包容量小，物平少时还好。如果波及数量打一是内存占用会比较严重，计算量也会大大提高。动静分配内存相似分治法，把问题分成多个子问题，一步步求解，且后面求出的子问题会对前面所求子问题有影响，不像是分治法的子问题都是独立的。并且时刻给与一个状态值，记录最优解，当所有子问题都解决完时，最优解也就会成为了问题的解了。重点次要在于对内存的调配，和子问题的计算。
算法四：回溯法
1、概念
回溯算法实际上一个相似枚举的搜寻尝试过程，次要是在搜寻尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的门路。
回溯法是一种选优搜寻法，按选优条件向前搜寻，以达到目标。但当摸索到某一步时，发现原先抉择并不优或达不到指标，就退回一步从新抉择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
许多简单的，规模较大的问题都能够应用回溯法，有“通用解题办法”的美称。
2、根本思维
在蕴含问题的所有解的解空间树中，依照深度优先搜寻的策略，从根结点登程深度摸索解空间树。当摸索到某一结点时，要先判断该结点是否蕴含问题的解，如果蕴含，就从该结点登程持续摸索上来，如果该结点不蕴含问题的解，则逐层向其先人结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。
若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜寻遍才完结。
而若应用回溯法求任一个解时，只有搜寻到问题的一个解就能够完结。
3、用回溯法解题的个别步骤：
（1）针对所给问题，确定问题的解空间：
首先应明确定义问题的解空间，问题的解空间应至多蕴含问题的一个（最优）解。
（2）确定结点的扩大搜寻规定
（3）以深度优先形式搜寻解空间，并在搜寻过程中用剪枝函数防止有效搜寻。
4、算法实例：求子集问题
public class 回溯法_求子集问题 {private static int[] s = {2,2,3};
private static int n = s.length;
private static int[] x = new int[n];
/**
* 输入汇合的子集
* @param limit 决定选出特定条件的子集
* 注：all 为所有子集,num 为限定元素数量的子集,
* sp 为限定元素奇偶性雷同，且和小于 8。*/
public static void all_subset(String limit){switch(limit){case "all":backtrack(0);break;
case "num":backtrack1(0);break;
case "sp":backtrack2(0);break;
}
}
/**
* 回溯法求汇合的所有子集，顺次递归
* 注：是否回溯的条件为精华
* @param t
*/
private static void backtrack(int t){if(t >= n)
output(x);
else
for (int i = 0; i <= 1; i++) {x[t] = i;
backtrack(t+1);
}
}
/**
* 回溯法求汇合的所有 (元素个数小于 4) 的子集，顺次递归
* @param t
*/
private static void backtrack1(int t){if(t >= n)
output(x);
else
for (int i = 0; i <= 1; i++) {x[t] = i;
if(count(x, t) < 4)
backtrack1(t+1);
}
}
/**
* (剪枝)
* 限度条件：子集元素小于 4, 判断 0~t 之间已被选中的元素个数，* 因为此时 t 之后的元素还未被递归, 即决定之后的元素
* 是否应该被递归调用
* @param x
* @param t
* @return
*/
private static int count(int[] x, int t) {
int num = 0;
for (int i = 0; i <= t; i++) {if(x[i] == 1){num++;}
}
return num;
}
/**
* 回溯法求汇合中元素奇偶性雷同，且和小于 8 的子集, 顺次递归
* @param t
*/
private static void backtrack2(int t){if(t >= n)
output(x);
else
for (int i = 0; i <= 1; i++) {x[t] = i;
if(legal(x, t))
backtrack2(t+1);
}
}
/**
* 对子集中元素奇偶性进行判断，还需元素的数组和小于 8
* @param x
* @param t
* @return
*/
private static boolean legal(int[] x, int t) {
boolean bRet = true; // 判断是否须要剪枝
int part = 0; // 奇偶性判断的基准
for (int i = 0; i <= t; i++) { // 抉择第一个元素作为奇偶性判断的基准
if(x[i] == 1){
part = i;
break;
}
}
for (int i = 0; i <= t; i++) {if(x[i] == 1){bRet &= ((s[part] - s[i]) % 2 == 0);
}
}
int sum = 0;
for(int i = 0; i <= t; i++){if(x[i] == 1)
sum += s[i];
}
bRet &= (sum < 8);
return bRet;
}
/**
* 子集输入函数
* @param x
*/
private static void output(int[] x) {for (int i = 0; i < x.length; i++) {if(x[i] == 1){System.out.print(s[i]);
}
}
System.out.println();}
public static void main(String[] args) {all_subset("all");
}
} 5、算法心得
回溯法是一种简直万能的算法，无论面对规模大还是规模小的问题都有妙用，在此次求子集问题中，回溯法的妙用我认为有两点，一是它采纳深度优先遍历算法，能够从根节点拜访到所有子节点，也就有了剪枝的妙用，在进有行奇偶限度，求和限度时，能够很好的做到把这些“越界”的没必要的子节点及子节点后的孙子节点去掉，大大减少了工夫的节约性。二是，算法框架的简洁性，使使用者能十分清晰的明确代码进行的形式。
算法五：分支限界法
一、根本形容
相似于回溯法，也是一种在问题的解空间树 T 上搜寻问题解的算法。但在个别状况下，分支限界法与回溯法的求解指标不同。回溯法的求解指标是找出 T 中满足约束条件的所有解，而分支限界法的求解指标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一指标函数值达到极大或极小的解，即在某种意义下的最优解。
（1）分支搜索算法
所谓“分支”就是采纳广度优先的策略，顺次搜寻 E - 结点的所有分支，也就是所有相邻结点，摈弃不满足约束条件的结点，其余结点退出活结点表。而后从表中抉择一个结点作为下一个 E - 结点，持续搜寻。
抉择下一个 E - 结点的形式不同，则会有几种不同的分支搜寻形式。
1）FIFO 搜寻
2）LIFO 搜寻
3）优先队列式搜寻
（2）分支限界搜索算法
二、分支限界法的个别过程
因为求解指标不同，导致分支限界法与回溯法在解空间树 T 上的搜寻形式也不雷同。回溯法以深度优先的形式搜寻解空间树 T，而分支限界法令以广度优先或以最小消耗优先的形式搜寻解空间树 T。
分支限界法的搜寻策略是：在扩大结点处，学生成其所有的儿子结点（分支），而后再从以后的活结点表中抉择下一个扩大对点。为了无效地抉择下一扩大结点，以减速搜寻的过程，在每一活结点处，计算一个函数值（限界），并依据这些已计算出的函数值，java 培训从以后活结点表中抉择一个最无利的结点作为扩大结点，使搜寻朝着解空间树上有最优解的分支推动，以便尽快地找出一个最优解。
分支限界法常以广度优先或以最小消耗（最大效益）优先的形式搜寻问题的解空间树。问题的解空间树是示意问题解空间的一棵有序树，常见的有子集树和排列树。在搜寻问题的解空间树时，分支限界法与回溯法对以后扩大结点所应用的扩大形式不同。在分支限界法中，每一个活结点只有一次机会成为扩大结点。活结点一旦成为扩大结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子退出活结点表中。尔后，从活结点表中取下一结点成为以后扩大结点，并反复上述结点扩大过程。这个过程始终继续到找到所求的解或活结点表为空时为止。
三、回溯法和分支限界法的一些区别
有一些问题其实无论用回溯法还是分支限界法都能够失去很好的解决，然而另外一些则不然。兴许咱们须要具体一些的剖析——到底何时应用分支限界而何时应用回溯呢？
回溯法和分支限界法的一些区别：
办法对解空间树的搜寻形式 存储结点的罕用数据结构结点存储个性罕用利用
回溯法深度优先搜寻堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解
分支限界法广度优先或最小耗费优先搜寻队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解
import java.util.Collections;
import java.util.LinkedList;
public class 分支界线法_求最大承重问题 {
LinkedList<HeapNode> heap;
public static class BBnode{
BBnode parent;// 父结点
boolean leftChild;// 左儿子结点标记
// 构造方法
public BBnode(BBnode par,boolean ch){
parent=par;
leftChild=ch;
}
}
/**
* 输入函数，做调试用
* @param list
*/
public static void printReverse(LinkedList<HeapNode> list){for (int i=0;i<list.size();i++) {HeapNode aBnode=list.get(i);
System.out.print("#"+aBnode.uweight+"#"+aBnode.level+" ");
}
}
/*
* 最大优先队列中存储的活结点类型为 HeapNode
*/
public static class HeapNode implements Comparable{
BBnode liveNode;
int uweight;// 活结点优先级（上界）int level;// 活结点在子集树种所处的层序号
// 构造函数
public HeapNode(BBnode node,int up,int lev){
liveNode=node;
uweight=up;
level=lev;
}
@Override
public int compareTo(Object x) {// 升序排列
int xu=((HeapNode)x).uweight;
if(uweight<xu) return -1;
if(uweight==xu) return 0;
return 1;
}
public boolean equals(Object x){return uweight==((HeapNode)x).uweight;
}
}
public void addLiveNode(int up,int lev,BBnode par,boolean ch){
// 将活结点退出到示意活结点优先队列的最大堆 H 中
BBnode b=new BBnode(par,ch);
HeapNode node=new HeapNode(b,up,lev);
heap.add(node);
Collections.sort(heap);
}
public int maxLoading(int[] w,int c,int[] bestx){
int count=0;
// 优先队列式分支限界法，返回最优分量，bestx 返回最优解
heap=new LinkedList<HeapNode>();
int n=w.length-1;
BBnode e=null;// 以后扩大结点
int i=1;// 以后扩大结点所处的层
int ew=0;// 扩大结点所对应的载重量
// 定义残余分量数组 r
int[] r=new int[n+1];
for(int j=n-1;j>0;j--) {r[j]=r[j+1]+w[j+1];
}
// 搜寻子集空间树
while(i!=n+1){
// 非叶结点
// 查看以后扩大结点的儿子结点
if(ew+w[i]<=c){
// 左儿子结点为可行结点
addLiveNode(ew+w[i]+r[i],i+1,e,true);
}
// 右儿子结点总为可行结点
addLiveNode(ew+r[i],i+1,e,false);
//printReverse(heap);
// 取下一个结点
HeapNode node=heap.pollLast();
i=node.level;
e=node.liveNode;
ew=node.uweight-r[i-1];
}
// 输入
for(int j=0;j<n;j++){bestx[j]=(e.leftChild)?1:0;
e=e.parent;
}
for(int j=n-1;j>=0;j--){System.out.print(bestx[j]+" ");
}
System.out.println();
return ew;
}
public static void main(String[] args) {
int n=4;
int c=70;
int w[]={0,26,60,22,18};// 下标从 1 开始
int[] bestx=new int[n+1];
分支界线法_求最大承重问题 b=new 分支界线法_求最大承重问题();
System.out.println("最优装载程序为（1 示意装入，0 示意未装入）：");
int ew=b.maxLoading(w, c, bestx);
System.out.println("最优装载重量为："+ew);
}
}