简介:算法一：分治法基本概念1.把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。2.分治策略是对于一个规模为n的 ...
算法一：分治法
基本概念
1.把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
2.分治策略是对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
适用情况
1)该问题的规模缩小到一定的程度就可以容易地解决
2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3)利用该问题分解出的子问题的解可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
分治法的复杂性分析
一个分治法将规模为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
分治法例题：合并排序和快速排序
class 分治_合并排序 {
/**
* 函数说明：在数组被拆分以后进行合并
*/
void Merge(int a[], int left, int , int rigth) {
//定义左端数组大小
int n1 = - left+1;
int n2 = rigth - ;
//初始化数组，分配内存
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[+1+i];
//用key做原数组索引，没调用一次函数重新给原数组付一次值
int i = 0, j = 0, key;
for(key = left; key i&&n2>j&&i < n1 && bejin[i] 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++];
}
}
/**
* 差分数组区间，不断分支
*/
void (int a[],int left,int rigth) {
int =0;
if(left
=(rigth+left)/2;
(a, left, );
(a, +1, rigth);
Merge(a, left, , rigth);
}
}
void main([] args) {
int a[]= {85,3,52,9,7,1,5,4};
(a, 0,7);
for(int i=0;i
.out.print(" "+a[i]);
}
}
}
class 分治_快速排序 {
/**
*交换函数，i，j为数组索引
*/
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的位置即可。
* @
*/
int (int[] array,int left,int right)
{
int key = array[right];//定义基准
int count=right;//保存rigth值
while(left < right)//防止数组越界
{
while(left < right && array[left] = key)
{
--right;
}
swap(array,left,right);
}
swap(array,right,count);
right;
}
/**
*分治思想，递归调用
*/
void (int array[],int left,int right)
{
if(left >= right)//表示已经完成一个组
{
;
}
int index = (array,left,right);//枢轴的位置
(array,left,index - 1);
(array,index + 1,right);
}
void main([] args) {
int a[]= {1,5,-5,54,15,67,16,23};
(a,0,7);
for(int i=0;i
.out.print(" "+a[i]);
}
.out.print("\n");
}
}
算法心得
作为分治法里很典型的一种算法，合并排序和快速排序充分展现了分治法的思想，分而治之，在此次编程使用此方法中，给我的体会是程序简单分为两部分，第一部分，不断“拆”，缩小子问题规模，达到最优子结构。然后合并，在合并过程中，应为子问题足够小，容易计算，再者不断合并子问题答案，最终求出问题解。
算法二：贪心算法
一、基本概念：
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
二、贪心算法的基本思路：
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
三、贪心算法适用的问题
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。
四、贪心算法的实现框架
从问题的某一初始解出发；
while （能朝给定总目标前进一步）
{
利用可行的决策，求出可行解的一个解元素；
}
由所有解元素组合成问题的一个可行解；
五、贪心策略的选择
因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。
贪心策略例题：prim算法
java.util.*;
class 贪心算法_prim算法 {
int MAX = .;
void main([] args) {
//定义无向图矩阵
int[][] map = new int[][] {
{ 0, 1, 6, 2},
{ 1, 0, 3, 2},
{ 6, 3, 0, 1},
{ 2, 2, 1, 0}
};
prim(map, map.);
}
void prim(int[][] graph, int n){
//定义节点名字
char[] c = new char[]{'A','B','C','D'};
int[] = new int[n]; //到新集合的最小权
int[] mid= new int[n];//存取前驱结点
List list=new ();//用来存储加入结点的顺序
int i, j, min, minid , sum = 0;
//初始化辅助数组
for(i=1;i
{
[i]=graph0;
mid[i]=0;
}
list.add(c[0]);
//一共需要加入n-1个点
for(i=1;i
{
min=MAX;
minid=0;
//每次找到距离集合最近的点
for(j=1;j
{
if([j]!=0&&[j]
{
min=[j];
minid=j;
}
}
if(minid==0) ;
list.add(c[minid]);
[minid]=0;
sum+=min;
.out.(c[mid[minid]] + "到" + c[minid] + " 权值：" + min);
//加入该点后，更新其它点到集合的距离
for(j=1;j
{
if([j]!=0&&[j]>graphminid)
{
[j]=graphminid;
mid[j]=minid;
}
}
.out.print("\n");
}
.out.("sum:" + sum);
}
}
算法心得
Prim算法是贪婪策略的一种很好的体现，在实现prim算法中，认识到java排课算法 java五大常用算法，早看早知道，贪婪策略是在做当先选择的情况下，先行囊括所有的选择储存好，在根据贪婪策略，选出最符合的步骤进行下去。虽然贪婪策略比较迅捷，应为它不需要预算所有情况（类似回溯），但应为每次所求只是局部最优解，所以结果不一定是最优解，算法准确性在与贪婪策略的选取好坏，所以也具有一定的局限性！
算法三：动态规划算法
一、基本概念
动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
二、基本思想与策略
基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解java排课算法，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。
三、适用的情况
能采用动态规划求解的问题的一般要具有3个性质：
(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的java排课算法，就称该问题具有最优子结构，即满足最优化原理。
(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
三、算法实例：背包问题
class 动态规划_背包问题 {
void main([] 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 intv.;
for (int i = 1; i
for (int j = 1; j =w[i])
mi=mi-1]+v[i]>mi-1?mi-1]+v[i]:mi-1;
else
mi=mi-1;
}
}
int max=0;
for (int i = 0; i
for (int j = 0; j max)
max=mi;
}
}
.out.(max);
}
}
四、算法心得
在此次编程中，运用动态内存算法解决背包问题，发先所需分配空间量比较大，在做背包容量小，物平少时还好。如果涉及数量打一是内存占用会比较严重，计算量也会大大提高。动态分配内存类似分治法，把问题分成多个子问题，一步步求解，且前面求出的子问题会对后面所求子问题有影响，不像是分治法的子问题都是独立的。并且时刻给与一个状态值，记录最优解，当所有子问题都解决完时，最优解也就会成为了问题的解了。重点主要在于对内存的分配，和子问题的计算。
算法四：回溯法
1、概念
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
2、基本思想
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。
若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。
而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
3、用回溯法解题的一般步骤：
（1）针对所给问题，确定问题的解空间：
首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。
（2）确定结点的扩展搜索规则
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
4、算法实例：求子集问题
class 回溯法_求子集问题 {
int[] s = {2,2,3};
int n = s.;
int[] x = new int[n];
/**
* 输出集合的子集
* @param limit 决定选出特定条件的子集
* 注：all为所有子集,num为限定元素数量的子集,
* sp为限定元素奇偶性相同，且和小于8。
*/
void ( limit){
(limit){
case "all":(0);break;
case "num":(0);break;
case "sp":(0);break;
}
}
/**
* 回溯法求集合的所有子集，依次递归
* 注：是否回溯的条件为精髓
* @param t
*/
void (int t){
if(t >= n)
(x);
else
for (int i = 0; i = n)
(x);
else
for (int i = 0; i