贪婪算法研究论文怎么写的

贪婪算法(Greedy Algorithm)也叫算贪心法,贪婪法.它是一个遵循启发式解决问题的算法范式.它的核心思想就是通过在每一步的选择中都选用当前步骤下最优的选择,期望结果是最优的算法.如 旅行推销员问题 . 贪婪算法尤其适用于有最优子结构的问题中,最优子结构的意思是局部的最优解可以导出全局的最优解.贪婪算法与 动态规划 的不同在于贪婪算法对每一个子问题都作出选择,不能回退;动态规划则会保存以前的运算结果,根据以前的结果对当前进行选择,可以回退. 贪婪算法可以解决一些 最优化 (如最大值最小值等)问题,比如求图中的 最小生成树 、求 哈夫曼编码 …其他大多数的情况都不适用贪婪算法,一旦一个问题可以使用贪婪算法来解决,那么贪婪算法一般是解决这个问题的最好办法.由于贪婪算法的高效性以及其答案比较接近最有结果,也可以作为辅助算法或直接解决一些结果要求不那么精确的问题. 原文首发于 贪婪算法适用于一些数学问题等,大部分适用的问题都有两个特点: 我们可以在每个子问题找出最好的选择然后进行总结.贪婪算法可能会根据迄今为止已经做的选择进行计算,但是却不会考虑之后子问题的选择.它将一个大的问题分解成小的问题并一个一个进行迭代计算.换句话说,贪婪算法不会重新考虑它已经得出的选择.这是它和 dynamic programming 的主要区别,动态规划会详尽的计算并确保得到最优解,在一步之后,动态规划会根据之前所有得到的选择进行下一个选择,并可能会重新对之前步骤的算法路径进行修改. 这个问题要包含 optimal substructure (即这个问题的最优解包含了它的子问题的最优解) 如以下几种类型的问题 原文首发于 matroid (拟阵) 是一个数学上的结构,它将 linear independence (线性无关)的概念从 vector spaces (向量空间)推广到了任意的集合.如果一个最优解问题有一个拟阵结构,那么贪婪算法是最佳的解决办法. 一个函数 定义了当集合 的所有子集合 都满足 的情况即为子模块. 假设有人想要找到一个集合 使得函数 最大.贪婪算法将会通过逐个添加在每一步中使得 增加最多的元素,产生一个结果至少是 ??todo. 所以,贪婪算法至少得出最优解的 倍的解. 这些问题也可以使用贪婪算法,但不是最好的解法,他们在最差的情况下,可能会得到很差的结果. 原文首发于 在很多其他问题上,贪婪算法无法产生最优解,甚至可能产生一个最坏的解决方案.比如之前提到的 traveling salesman problem :对每一个城市都要计算一个最近的邻居,这种方式可能会产生一个最坏的路程. 比如下图,贪婪算法只考虑到下一步的最优解,但是却没有考虑到之后的解决方案,导致实际上得出的不是一个最优解. 贪婪法基本上（但并不是一定）不适用于求全局最优解，因为他通常没有遍历所有的数据。他们太早给出了肯定的选择使得他们无法从所有的解法中找到最优解。比如，使用 greedy coloring 算法来解决 graph coloring problem 以及所有的 NP-complete 问题。尽管如此，贪婪法还是很有用的，因为他们容易被考虑到并且通常情况下会给出一个比较好的解法。 如果一个贪婪算法可以被证明是某个问题的全局最优解法，他通常情况下就会成为优先选择的方法，因为它比其他的最优解方法如 dynamic programming 要快。这种例子有使用 Kruskal's algorithm 和 Prim's algorithm 找到 minimum spanning trees ,还有找到最优 Huffman trees . 贪心法也使用于 网络 路由 中。使用贪心路由，消息会被发送到距离目标节点“最近”的相邻节点。一个节点位置的定义（还有“最近”的含义）也许会取决于它的物理位置，如同在 ad hoc networks 中使用 geographic routing . 位置也可能会使一个人造的结构如同在 small world routing 和 distributed hash table 中. 我的博客 我的 GitHub 微信公众号 [图片上传失败...(image-ee4c03-68)]

做了这10道题，其实发现贪心算法没有什么规律，要说有什么共同特点就是都是由局部最优从而推出全局最优，每个题基本上都要考虑其局部最优是什么，其全局最优是什么，所以虽然都用到了贪心算法的思想，但是题与题之间又没有什么规律可言。 现在把这10道题的思路总结一下（总结主要以我的主观看法在写，可能别人看会不知道我在说什么） 1.分发饼干： 思路：想要完成最多的小孩满足，那么就得最小的饼干给胃口最小的小孩 这里的贪心思想， 局部最优就是尽可能让一个饼干喂饱一个 全局最优就是最多的小孩满足 2.摆动序列： 思路：这里要找到最长的摆动序列，那么其实就是找那些波峰波谷，如图所示 可以看出来，在到达波峰波谷的路上有几个数字不会影响什么，可以直接去掉。 那么这里的局部最优就是把单调坡上的点删掉，保留最多的波峰波谷 全局最优就是得到对多的波峰波谷，即最长的摆动序列 3.最大子序和 这道题显然可以暴力解出来，即列出所有子序和，找出最大的，不过计算量会比贪心大很多。 这里主要介绍贪心解的思想： 想要得到最大子序和，就得保证每次相加时，相加后不能为负数，因为负数继续往下加一定是拉低总和的，那么我们当加成到负数时就重新从下个数开始加，并实时记录最大的子序和，这样一遍循环就能得出最大子序和。 局部最优：加成负数就立刻停止，并从下个元素重新开始 全局最优：得到最大子序和 4.买卖股票的最佳时机II 思路：想要得到最大利润，那就要低价买入高价卖出，那么怎样的买卖才能得到最大利润呢。 这里就体现出贪心算法的“贪”字（我猜的），这道题贪在哪呢，贪在只要有利可图就去做，即只要今天买入的价钱比明天卖出的价钱底，即有利可图，那么我就去做，做就是在今天买入，在明天卖出。 局部最优：得到每天的最大正利润 全局最优：得到最大利润 5.跳跃游戏 思路：每个数组的元素代表的是可以跳的最远下标，那么我们只要使那个最远下标包含最后一个下标就是可以跳到，那么我们每跳到一个位置就要更新那个可以跳的范围，即可以跳到的最远下标。 局部最优：每次跳跃都得出最远的跳跃范围 全局最优：最后能跳到的最大范围 6.跳跃游戏II 思路：这道题要得到最小的跳跃数，其实只要保证跳的是位置是可以跳范围内更新最远范围的位置就可以了。 为什么这么说呢？以题例来说： 我们刚开始在‘0’的位置，我们能跳到‘1’和‘2’的位置，那么我们怎么跳呢？可以看到跳到‘1’之后更新的最大范围是‘4’，跳到‘2’之后更新的最大范围是‘3’，所以我们就跳‘2’了，因为跳‘1’之后更新的最大可跳范围更大包含了跳‘2’的最大可跳范围，那么肯定是跳‘3’最优呀，这里就体现了局部最优的思想。 局部最优：每次跳后，更新的最大可调范围最大 全局最优：跳跃次数最少 次取反后最大化的数组和 思路：想要得到最大数组和，我们就可以想到怎样做呢？ 一，尽可能保证负数最少 二，负数绝对值大的优先变正 三，正数绝对值小的优先变负，有零变零 本着这三条原则做，就能做出来。 那么这道题体现了什么贪心思想呢？ 我感觉，前面那三条都是贪心中‘贪’的体现 在负数中，局部最优就是：绝对值大的负数优先变正 在正数中，局部最优就是：绝对值小的正数变负，有零变零 得到的全局最优：数组和最大 8.加油站 思路：首先可以想到这道题是可以暴力解出来了，即分别以每个加油站为起点，得出可以跑一圈的加油站 那么贪心思想做，该怎么做呢，首先可以想到，如果以一个1点为起点当跑着跑着跑到3，油变为负数时，那么说明以这个起点是不行的，但是以2或3为起点行不行呢？答案肯定是不行的，因为1跑到3，油变为负，说明1~3的gas=0的，所以可以得出，如果1~3油数变为负数，那么由2~3油数肯定也为负数。 所以这里就可以得出，如果经过几个加油站油数变为负了，那么起点就更新为这一段路的下个加油站跑 局部最优：油量一旦为负，就从下个加油站重新跑 全局最优：得出可以跑一圈的加油站起点 9.分发糖果 思路：每个孩子至少一个，如果一个孩子比他旁边的孩子优秀，就要比他旁边的糖果多，这道题一旦两边都考虑很容易顾此失彼，所以我们就定义两个循环，分别从左到右，从右到左去考虑，只要更优秀则比他旁边的多1，如果已经多了就不用变了。 局部最优：保证优秀的孩子比他旁边的孩子糖果多 全局最优：满足题中条件，至少要发的糖果 10.柠檬水找零 思路：我们在找零时要遵守的规则一定是： 5 得5 10 得10减5 15 得15，优先减一个10减一个5  如果10块没有则减三个5 局部最优：以最少用的5块的方式找零 全局最优：得到找零能否进行下去