巴尔加瓦算法图解——第八章 贪婪算法(上)

2023-12-30 21:33:18

对不住,虽然我知道没有人看,那就说对不住作为观众的自己吧。这段时间精神状态非常不好,学习的东西没有以前多了。不过我还是要继续更新。只要我还更新着,说明人还有点生气。我自己会原谅自己的。

目录

第八章?贪婪算法

8.1 教室调度问题

8.2背包问题

8.3 集合覆盖问题


第八章?贪婪算法

本章内容

??学习如何处理不可能完成的任务:没有快速算法的问题(NP完全问题)。

??学习识别NP完全问题,以免浪费时间去寻找解决它们的快速算法。

??学习近似算法,使用它们可快速找到NP完全问题的近似解。

??学习贪婪策略——一种非常简单的问题解决策略。

8.1 教室调度问题

希望在这间教室上尽可能多的课。如何选出尽可能多且时间不冲突的课程呢?这个问题好像很难,不是吗?

实际上,算法可能简单得让你大吃一惊。具体做法如下。

(1)选出结束最早的课,它就是要在这间教室上的第一堂课。

(2)接下来,必须选择第一堂课结束后才开始的课。同样,你选择结束最早的课,这将是要在这间教室上的第二堂课。

美术

9

10

??

英语

9

10:30

数学

10

11

??

计算机

10:30

11:30

音乐

11

12

??

用专业术语说,就是你每步都选择局部最优解,最终得到的就是全局最优解。

8.2背包问题

假设你是个贪婪的小偷,背着可装35磅(1磅≈0.45千克)重东西的背包,在商场伺机盗窃各种可装入背包的商品。

音响:3000/30磅

笔记本电脑:2000/20磅

吉他:1500/15磅

同样,你采取贪婪策略,这非常简单。

(1)盗窃可装入背包的最贵商品。

(2)再盗窃还可装入背包的最贵商品,以此类推。

贪婪策略选了音响,获得3000元。实际上可以装笔记本+吉他=3500元。

在这里,贪婪策略显然不能获得最优解,但非常接近。

根本原因:背包问题有两个衡量标准——重量和价值;而课程安排只有“时间”。

你只需找到一个能够大致解决问题的算法,此时贪婪算法正好可派上用场,因为它们实现起来很容易,得到的结果又与正确结果相当接近。

8.1 你在一家家具公司工作,需要将家具发往全国各地,为此你需要将箱子装上卡车。每个箱子的尺寸各不相同,你需要尽可能利用每辆卡车的空间,为此你将如何选择要装上卡车的箱子呢?请设计一种贪婪算法。使用这种算法能得到最优解吗?

选择能装的最大空间的箱子,不断重复。

不能得到最优解。

8.2 你要去欧洲旅行,总行程为7天。对于每个旅游胜地,你都给它分配一个价值——表示你有多想去那里看看,并估算出需要多长时间。你如何将这次旅行的价值最大化?请设计一种贪婪算法。使用这种算法能得到最优解吗?

不断地挑选可在余下的时间内完成的价值最大的活动,直到余下的时间不够完成任何活动为止。不能得到。

得到的办法:想去程度从高到低排序,花费时间从高到低排序,在限制的时间内遍历。

8.3 集合覆盖问题

如何找出覆盖全美50个州的最小广播台集合?

(1)列出集合

每个位置都有“选”或者“不选”两个选择,总共有2^n种方案。

运行时间O(2^n),运行时间很慢。

(2)找最小。

近似算法:

(1)首先选择覆盖最多州的广播电台,然后进行循环,选出去除已覆盖州后,覆盖最多未覆盖州的广播台。

(2)重复(1)

这是一种近似算法(approximation algorithm)。在获得精确解需要的时间太长时,可使用近似算法。

判断近似算法优劣的标准如下:??速度有多快;??得到的近似解与最优解的接近程度。

贪婪算法是不错的选择,它们不仅简单,而且通常运行速度很快。在这个例子中,贪婪算法的运行时间为O(n^2),其中n为广播台数量。

最好的情况:一个电台覆盖50个州,搜索一次。

最坏的情况:每个电台之间覆盖没有交集。第一次搜索规模是n,搜索N次,n^2。

文章来源:https://blog.csdn.net/2301_80205209/article/details/135309618
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。