江苏龙网

  1. 主页 > 生活百科 > >

java五大常用算法，早看早知道( 三 )

算法


//加入该点后 ， 更新其它点到集合的距离
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算法中 ， 认识到 ， 贪婪策略是在做当先选择的情况下 ， 先行囊括所有的选择储存好 ， 在根据贪婪策略 ， 选出最符合的步骤进行下去 。虽然贪婪策略比较迅捷 ， 应为它不需要预算所有情况（类似回溯） ， 但应为每次所求只是局部最优解 ， 所以结果不一定是最优解 ， 算法准确性在与贪婪策略的选取好坏 ， 所以也具有一定的局限性！
算法三：动态规划算法
一、基本概念
动态规划过程是：每次决策依赖于当前状态 ， 又随即引起状态的转移 。一个决策序列就是在变化的状态中产生出来的 ， 所以 ， 这种多阶段最优化决策解决问题的过程就称为动态规划 。
二、基本思想与策略
基本思想与分治法类似 ， 也是将待求解的问题分解为若干个子问题（阶段） ， 按顺序求解子阶段 ， 前一子问题的解 ， 为后一子问题的求解提供了有用的信息 。在求解任一子问题时 ， 列出各种可能的局部解 ， 通过决策保留那些有可能达到最优的局部解 ， 丢弃其他局部解 。依次解决各子问题 ， 最后一个子问题就是初始问题的解 。
由于动态规划解决的问题多数有重叠子问题这个特点 ， 为减少重复计算 ， 对每一个子问题只解一次 ， 将其不同阶段的不同状态保存在一个二维数组中 。
与分治法最大的差别是：适合于用动态规划法求解的问题 ， 经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上 ， 进行进一步的求解） 。

java五大常用算法，早看早知道

文章插图
 
三、适用的情况
能采用动态规划求解的问题的一般要具有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);
}
}
四、算法心得
在此次编程中 ， 运用动态内存算法解决背包问题 ， 发先所需分配空间量比较大 ， 在做背包容量小 ， 物平少时还好 。如果涉及数量打一是内存占用会比较严重 ， 计算量也会大大提高 。动态分配内存类似分治法 ， 把问题分成多个子问题 ， 一步步求解 ， 且前面求出的子问题会对后面所求子问题有影响 ， 不像是分治法的子问题都是独立的 。并且时刻给与一个状态值 ， 记录最优解 ， 当所有子问题都解决完时 ， 最优解也就会成为了问题的解了 。重点主要在于对内存的分配 ， 和子问题的计算 。
java五大常用算法，早看早知道


推荐阅读


上一篇：中国茶企核心竞争力缺失缘由何在

下一篇：茶经立顿并用 整合资源做强中国茶