• 高调网友路过
    了解作者
  • matlab
    开发工具
  • 2KB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 1
    下载次数
  • 2019-04-11 19:43
    上传日期
——从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。 该算法存在问题: 1. 不能保证求得的最后解是最佳的; 2. 不能用来求最大或最小解问题; 3. 只能求满足某些约束条件的可行解的范围。
greedy algorithm.zip
  • greedy algorithm.txt
    3.3KB
内容介绍
贪心算法一、算法思想 贪心法的基本思路: ——从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。 该算法存在问题: 1. 不能保证求得的最后解是最佳的; 2. 不能用来求最大或最小解问题; 3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程: 从问题的某一初始解出发; while 能朝给定总目标前进一步 do    求出可行解的一个解元素; 由所有解元素组合成问题的一个可行解; 二、例题分析 1、[背包问题]有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 分析: 目标函数: ∑pi最大 约束条件是装入的物品总重量不超过背包容量:∑wi<=M( M=150) (1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优? (2)每次挑选所占空间最小的物品装入是否能得到最优解? (3)每次选取单位容量价值最大的物品,成为解本题的策略。 ? 2、[单源最短路径]一个有向图G,它的每条边都有一个非负的权值c[i,j],“路径长度”就是所经过的所有边的权值之和。对于源点需要找出从源点出发到达其他所有结点的最短路径。   E.Dijkstra发明的贪婪算法可以解决最短路径问题。算法的主要思想是:分步求出最短路径,每一步产生一个到达新目的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取:在未产生最短路径的顶点中,选择路径最短的目的顶点。    设置顶点集合S并不断作贪心选择来扩充这个集合。当且仅当顶点到该顶点的最短路径已知时该顶点属于集合S。初始时S中只含源。    设u为G中一顶点,我们把从源点到u且中间仅经过集合S中的顶点的路称为从源到u特殊路径,并把这个特殊路径记录下来(例如程序中的dist[i,j])。    每次从V-S选出具有最短特殊路径长度的顶点u,将u添加到S中,同时对特殊路径长度进行必要的修改。一旦V=S,就得到从源到其他所有顶点的最短路径,也就得到问题的解 。 stra.pas 3、[机器调度]现有N项任务和无限多台机器。任务可以在机器上处理。每件任务开始时间和完成时间有下表: 任务 a b c d e f g 开始(si) 0 3 4 9 7 1 6 完成(fi) 2 7 7 11 10 5 8   在可行分配中每台机器在任何时刻最多处理一个任务。最优分配是指使用的机器最少的可行分配方案。请就本题给出的条件,求出最优分配。 ?三、练习题: 已知5个城市之间有班机传递邮件,目的是为了寻找一条耗油量较少的飞行路线。5个城市的联系网络如图所示。图中编号的结点表示城市,两个城市之间的连线上的值表示班机沿该航线已行的耗油量,并假定从城市i到j和城市j到i之间的耗油量是相同的。 分析: 1. 运用贪心思想: 在每一步前进的选择上,选取相对当前城市耗油量最小的航线; 2. 图解:若从1出发,有图: 总耗油量=14 1-2-5-3-4-1 但若路线改为:1-5-3-4-2-1,则总耗油量=13 所以,这样的贪心法并不能得出最佳解。 3. 改善方案: 从所有城市出发的信心过程,求最优的。 编程: 1. 数据结构: 城市联系网络图的描述(图的邻接矩阵的描述): const c=array[1..5,1..5] of integer=((0,1,2,7,5), (1,0,4,4,3), (2,4,0,1,2), (7,4,1,0,3)); 2. 贪心过程: begin 初始化所有城市的算途径标志; 设置出发城市V; for i:=1 to n-1 do {n-1个城市} begin s:=从V至所有未曾到过的城市的边集中耗油量最少的那个城市; 累加耗油量; V:=s; 设V城市的访问标志; end; 最后一个城市返回第一个城市,累加耗油量; end; 3. 主过程:实现改善方案 begin for i:=1 to n do begin cost1:=maxint; {初始化} 调用贪心过程,返回本次搜索耗油量cost; if cost<cost1 then 替换; end; 输出;
评论
    相关推荐
    • Greedy-algorithm.rar
      贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。
    • Greedy-algorithm.rar
      贪心算法,具体的讲解了贪心算法,代码非常规范,是学习数据结构和算法难得的资料
    • greedy algorithm.rar
      介绍了贪心算法的基本理论和有关实例的程序,内容比较全面.
    • Algorithm:算法
      算法 版本:Python 3.7.3 IDE :VSCODE作者:崔泰tus描述:这是用于编码测试的算法文件。习题集:BOJ( ),codeup( ),Programmers( )顺序:排序-> DFS / BFS(进行中)->贪婪->蛮力->哈希->堆栈/队列->堆-> DP
    • Greedy-Algorithm
      贪婪算法是一种建立一个解决方案的范例,总是选择提供最明显和最直接利益的解决方案。 因此,选择局部最优也会导致整体解决方案的问题最适合贪婪 贪婪最适合用于优化问题。 如果存在以下问题,则可以使用Greedy解决...
    • gasstationleetcode-Algorithm:算法
      贪婪算法中每一步的最好是整体最好的 DP(Dynamic Programming):将大问题分解为小问题的算法 深度优先搜索 (DFS) 和广度优先搜索 (BFS) 堆栈(LIFO) & 队列(FIFO) & DEQUE & HEAP 回溯 分裂与征服 字符串处理 ...
    • 10- Armed Bandit Test bed using greedy algorithm:这是一个使用贪婪算法创建10个
      这是一组 2000 个随机生成的 k 臂老虎机k = 10 的问题。对于每个强盗问题,动作值, q*(a), a = 1,2 .... 10, 是根据均值为 0 的正态(高斯)分布选择的,并且方差 1.... 也可以针对非贪婪算法修改代码。
    • greedy_algorithm.rar
      利用贪婪算法求得系统内最大连接的节点数目
    • greedy algorithm - 副本.zip
      详细讲解贪婪算法,从入门到精通,包括例题以及练习题,以及程序
    • matlabcnhelp.rar
      matlab中文帮助很难找的,快速下载