- 浏览: 328680 次
- 性别:
- 来自: 西宁
-
文章分类
- 全部博客 (120)
- Java Thought (29)
- Java Pattern (4)
- Data Base (7)
- Algorithm Design (33)
- Linux (0)
- Mysql (2)
- Oracle (0)
- ConstructionDesign-架构 (5)
- Spring Platform (0)
- Tomcat (1)
- JavaScript (7)
- Web System (3)
- MS SQLServer (1)
- 软件哲学 (6)
- View (3)
- Java GUI (4)
- CSSDIV (7)
- CloudComputing (0)
- WebService (0)
- SystemOrProject (2)
- SOA (0)
- 互转共享 (3)
- 偶尔java习题 (0)
- Thinks with does (1)
最新评论
-
sassds:
佩服啊 高手
分享一款js特效 -
bhjackson:
学习啦,能否详细介绍下回溯的过程?O(∩_∩)O谢谢
分享回溯法- 找n个数中r个数的组合 -
zk7019311:
了解了解。。。。。
业务层代码复用的一点建议 -
lijie1819:
看到LZ的设计思想,感觉和抽象工厂模式有点相像。
业务层代码复用的一点建议 -
wjjcml1982:
酷毙了!楼主太强悍了!
分享一款js特效
1. 贪婪算法描述
贪婪算法又叫登山法,它的根本思想是逐步到大山顶,即逐步获得最优解,是解决最优化问题时的一种简单但适用范围有限的策略。
"贪婪"可以理解为以逐步的局部最优,达到最终的全局最优。
贪婪算法没有固定的算法框架,算法设计的关键是贪婪策略的选择。一定要注意,选择的贪婪策略要具有无后向性。即某阶段状态一旦
确定后,不受这个状态以后的决策影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关,也称这种特性为无后效
性。因此,适应用贪婪策略解决的问题类型较少,对所采用的贪婪策略一定要仔细分析其是否满足无后效性。
2. 贪婪算法策略的一些应用
霍夫曼树,构造最小生成树的Prim算法和Kruskl算法等。
3. 贪婪策略算法设计框架
(1) 贪心法的基本思路
从问题的某一个初始解出发逐步逼近给定的目标,每一步都做一个不可回溯的决策,尽可能求得最好的解。
(2) 贪婪算法适用的问题
局部最优策略导致产生全局最优解。
利用数学方法证明"局部最优策略导致产生全局最优解。"
(3) 贪婪策略选择
通过局部最优达到全局最优,即在每个阶段选取一个最优决策,逐步构造最优解。
贪婪策略依靠经验或直觉来确定一个最优解得决策。
贪婪策略一定要精心确定,在使用之前最好对策略的可行性进行数学证明。
(4) 贪婪策略下的算法框架
从问题的某一初始解出发;
while(能朝给定总目标前进一步){
利用可行的局部最优决策逐步求解
}
最顶层便是一个全局最优解
因此,可以说贪婪策略没有一个固定的算法框架。
4. 我对贪婪策略的分类
(1) 绝对贪婪
举个例子:
1> 问题描述
最优服务次序问题。
设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti, 1<=i<=n。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?
平均等待时间是n个顾客等待服务时间的总和除以n。
input: 正整数n,表示n个顾客。 接下来一行输入n个正整数,表示n个顾客需要的服务时间。
output:最小的平均等待时间
例如:
input:
10
56 12 1 99 1000 234 33 55 99 812
output:
532.00
2> 贪婪策略选择
要计算平均等待时间: average = (w1 + w2 + ... + wn) / n 最小,则要使((w1 + w2 + ... + wn))最小.
题目中,每个顾客i需要的时间为ti,当ti进行服务时,其余n-1个顾客在等待,因此为使每次等待时间最少,必须优先选取
ti最小的顾客去服务。因此可对t1,t2,...,tn进行排序,优先选取最小的数去为顾客服务。
贪婪策略选择:最短服务时间优先,可绝对使得平均等待时间最小。
(2) 相对贪婪
举个简单例子:
1> 问题描述:
有两个人轮流取2n个数中的n个数,所取数之和大者为胜。请编写算法,让先取数的人胜利。
游戏规则:假设取数者只能看到2n个数中两边的数,并轮流取数。当两者所取数之和相同时,先取者胜。
2> 贪婪策略选择:
这个问题有很强的随机性。
但有一种策略虽不能保证所取数的和是最大的,却是一个先取者必胜的全局策略。
N个数排成一行,从左到右依次编号,1,2,...,N.
因为N是偶数,又因为是我们先取数,计算机后取数,所以一开始我们既可以从最左边取1的数(奇编号),又可以从最右边取的数(偶编号)
如果我们第一次取奇编号(编号为1)的数,则计算机只能取到偶编号(2或N)的数;如果我们第一次取偶编号的数(编号为N),则接着计算机只能
取到奇编号的数(1或N-1);所以我们能够控制让计算机自始之终只取奇或偶一种编号的数。这样,只要比较奇编号数之和与偶编号数之和谁大,
就可以决定最开始是取奇编号数还是偶编号数了。
因此,算法只需要分别计算一组数的奇位数和偶位数之和,然后就有了先取数者必胜的取数方案了。
如果有兴趣,可在<<是否很久没抽象和逻辑了呢? DODO它吧(很基础)一 ~ 四>>系列可以看看
贪婪算法又叫登山法,它的根本思想是逐步到大山顶,即逐步获得最优解,是解决最优化问题时的一种简单但适用范围有限的策略。
"贪婪"可以理解为以逐步的局部最优,达到最终的全局最优。
贪婪算法没有固定的算法框架,算法设计的关键是贪婪策略的选择。一定要注意,选择的贪婪策略要具有无后向性。即某阶段状态一旦
确定后,不受这个状态以后的决策影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关,也称这种特性为无后效
性。因此,适应用贪婪策略解决的问题类型较少,对所采用的贪婪策略一定要仔细分析其是否满足无后效性。
2. 贪婪算法策略的一些应用
霍夫曼树,构造最小生成树的Prim算法和Kruskl算法等。
3. 贪婪策略算法设计框架
(1) 贪心法的基本思路
从问题的某一个初始解出发逐步逼近给定的目标,每一步都做一个不可回溯的决策,尽可能求得最好的解。
(2) 贪婪算法适用的问题
局部最优策略导致产生全局最优解。
利用数学方法证明"局部最优策略导致产生全局最优解。"
(3) 贪婪策略选择
通过局部最优达到全局最优,即在每个阶段选取一个最优决策,逐步构造最优解。
贪婪策略依靠经验或直觉来确定一个最优解得决策。
贪婪策略一定要精心确定,在使用之前最好对策略的可行性进行数学证明。
(4) 贪婪策略下的算法框架
从问题的某一初始解出发;
while(能朝给定总目标前进一步){
利用可行的局部最优决策逐步求解
}
最顶层便是一个全局最优解
因此,可以说贪婪策略没有一个固定的算法框架。
4. 我对贪婪策略的分类
(1) 绝对贪婪
举个例子:
1> 问题描述
最优服务次序问题。
设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti, 1<=i<=n。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?
平均等待时间是n个顾客等待服务时间的总和除以n。
input: 正整数n,表示n个顾客。 接下来一行输入n个正整数,表示n个顾客需要的服务时间。
output:最小的平均等待时间
例如:
input:
10
56 12 1 99 1000 234 33 55 99 812
output:
532.00
2> 贪婪策略选择
要计算平均等待时间: average = (w1 + w2 + ... + wn) / n 最小,则要使((w1 + w2 + ... + wn))最小.
题目中,每个顾客i需要的时间为ti,当ti进行服务时,其余n-1个顾客在等待,因此为使每次等待时间最少,必须优先选取
ti最小的顾客去服务。因此可对t1,t2,...,tn进行排序,优先选取最小的数去为顾客服务。
贪婪策略选择:最短服务时间优先,可绝对使得平均等待时间最小。
(2) 相对贪婪
举个简单例子:
1> 问题描述:
有两个人轮流取2n个数中的n个数,所取数之和大者为胜。请编写算法,让先取数的人胜利。
游戏规则:假设取数者只能看到2n个数中两边的数,并轮流取数。当两者所取数之和相同时,先取者胜。
2> 贪婪策略选择:
这个问题有很强的随机性。
但有一种策略虽不能保证所取数的和是最大的,却是一个先取者必胜的全局策略。
N个数排成一行,从左到右依次编号,1,2,...,N.
因为N是偶数,又因为是我们先取数,计算机后取数,所以一开始我们既可以从最左边取1的数(奇编号),又可以从最右边取的数(偶编号)
如果我们第一次取奇编号(编号为1)的数,则计算机只能取到偶编号(2或N)的数;如果我们第一次取偶编号的数(编号为N),则接着计算机只能
取到奇编号的数(1或N-1);所以我们能够控制让计算机自始之终只取奇或偶一种编号的数。这样,只要比较奇编号数之和与偶编号数之和谁大,
就可以决定最开始是取奇编号数还是偶编号数了。
因此,算法只需要分别计算一组数的奇位数和偶位数之和,然后就有了先取数者必胜的取数方案了。
评论
5 楼
passionke
2010-06-12
局部最优 未必是全局最优
全局最优又往往是np 问题
所以很尴尬 很蛋疼
全局最优又往往是np 问题
所以很尴尬 很蛋疼
4 楼
sunson468
2010-06-12
真的好久不接触这些算法了~~
不过看起来这两个问题都只是排序的扩展,将排序的算放按照业务的需求放置在不同的位置。
1,从小到大排序就可以了吧~
2,从大到小排序,但是放置的位置是从两头开始,轮流放置[左右右左左右。。。]
贪婪算法应该在一个比较平坦的界面上执行的,比如如果用贪心算法来解决无阻挡点,无权重的图遍历会更好,局部的优化就能到总体的优化。但是限制太大了。
我记得以前有这么个问题,有个包能放N重量,若干M个重量分别为MW的物品,如何摆放才能使包的容量最大化,这个貌似用什么贪婪算法的,记不得,就是现在这个问题我也没办法给出一个觉的很高效的算法。
不过看起来这两个问题都只是排序的扩展,将排序的算放按照业务的需求放置在不同的位置。
1,从小到大排序就可以了吧~
2,从大到小排序,但是放置的位置是从两头开始,轮流放置[左右右左左右。。。]
贪婪算法应该在一个比较平坦的界面上执行的,比如如果用贪心算法来解决无阻挡点,无权重的图遍历会更好,局部的优化就能到总体的优化。但是限制太大了。
我记得以前有这么个问题,有个包能放N重量,若干M个重量分别为MW的物品,如何摆放才能使包的容量最大化,这个貌似用什么贪婪算法的,记不得,就是现在这个问题我也没办法给出一个觉的很高效的算法。
3 楼
coffeesweet
2010-06-12
实际中绝对贪婪的应用应该多些吧
2 楼
maozj
2010-06-11
peng3409 写道
总结的很全面,如果再有典型的示例就更完善
如果有兴趣,可在<<是否很久没抽象和逻辑了呢? DODO它吧(很基础)一 ~ 四>>系列可以看看
1 楼
peng3409
2010-06-11
总结的很全面,如果再有典型的示例就更完善
发表评论
-
开散列的简单模拟(一)
2010-06-28 08:33 18491. 散列 散列有两种 ... -
递归和动态规划构造两个字符序列的最长公共字符子序列
2010-06-28 08:28 4515应je朋友要求,所以翻开以前的算法题目,整理了以下,给 ... -
最大公约数的应用 - 分享
2010-06-25 08:08 18991.先看一家大公司笔试题 数组中有n个数据,要将它们顺 ... -
信息数字化解逻辑题分享
2010-06-21 08:09 12801. 前提条件: 将逻辑题目中的信息用数字化描述。 ... -
递归算法分析-分享
2010-06-19 16:09 16351. 深入认识递归 (1) 递 ... -
非递归算法分析实例分享
2010-06-18 15:47 10741 仅仅依赖于问题规模的时间复杂度 (1) 例1: 交换i和 ... -
NP完全性问题
2010-06-18 14:02 7057在学习算法设计与分析时,经常会提到NP完全性问题,到底 ... -
算法分析精述分享
2010-06-18 12:03 9011. 算法分析的评价体系 评价算法的三条主要标准是: ... -
带权有向图 - 边上权值非负情形的单源最短路径问题
2010-06-07 08:57 27141. 问题描述: 给定 ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)四
2010-06-07 08:54 139421. 工作分配问题。 ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)三
2010-06-07 08:53 113117. 字符统计问题。 编写一个算法,统计在一个输入 ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)二
2010-06-07 08:47 14068. 数字迷问题。 A B C ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)一
2010-06-07 08:38 12061. 线程问题。 设计4个线程,其中两个线程每次对j增加 ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)
2010-06-07 08:37 19171. 线程问题。 设计 ... -
Java快速排序算法整理(二)
2010-05-31 14:04 1052package boke.sort; /** * 快 ... -
Java快速排序算法整理(一)
2010-05-31 13:39 675package boke.sort; /** * 快 ... -
Java最小堆实现
2010-05-31 08:29 59181.堆结点 package boke.heap1; /* ... -
Java插入排序代码整理
2010-05-28 14:44 1282package boke.sort; /** * 插 ... -
Java选择排序代码整理
2010-05-28 14:37 1539package boke.sort; /** * 选 ... -
Java冒泡排序代码整理
2010-05-28 14:26 2010Java冒泡排序代码整理: package boke.sor ...
相关推荐
不同于贪婪下降搜索(Greedy descent with restart),局部束搜索在搜索过程中分享信息,提高了效率。局部束搜索的一个变种是随机束搜索(Stochastic Beam Search),它利用玻尔兹曼选择策略,根据候选解的适应度概率性...
总结来说,公平分享调度是操作系统中用于优化资源分配的重要算法,尤其对于嵌入式Linux和Unix系统而言。它通过权重分配和动态调度,确保所有进程都能公平地获取计算资源,从而提高系统整体的性能和用户体验。对于...
传统的影响力最大化算法往往基于模拟、贪婪方法或近似优化方法,这些方法要么计算成本过高,要么没有充分地利用社交网络数据。 为了验证算法的有效性,研究者将算法应用于这12个社交网络平台,并计算了各自的影响力...
总结来说,这个项目涉及到了利用启发式算法在Jupyter Notebook环境中对复杂网络进行社区检测的研究,其中可能包括多种策略的实现和比较,以及结果的可视化和分析。通过深入理解和实践,我们可以更好地理解网络结构,...
- **贪婪逐层预训练**:探讨了为何采用贪婪逐层预训练策略来训练深度信念网络。 - **实现细节**:详细描述了深度信念网络的实现步骤。 #### 混合蒙特卡罗采样(HMC) - **理论基础**:介绍了混合蒙特卡罗采样的基本...