巴尔加瓦算法图解——第八章 贪婪算法(全局最优)(下)

2024-01-07 19:10:06

前言

提前回来了,不过也是短暂地回来一下。之后更新的频率会慢一些,有毕业设计还有一些申请的事情要忙。

这五天拼尽全力了准备了某场考试。《请回答1988》这部剧赐予了我很多,狗焕形容自己失败的暗恋“搞怪的不是红绿灯,而是我数不清的犹豫”,宝拉说自己一心无法做两件事,在胶囊似的空间里学习熬过法考,在难受的时候想一下这些就更容易坚持下去。我并不是不知道怎样生活更享受更容易,只是一直以来的惯性让我什么都想拼到底。我也知道我的很多同学可以轻易地考到这个分数,甚至逼近满分,但我也知道对我而言Everything is set up for your next best season. 这就是我一直用尽全力的理由,每每想到这些真的不禁感叹自己是一个坚强又有恒心的人。

之后的日子里还是学着过轻松一点吧,感觉每天有哪个小时没学习,都好像有罪,这个心理状态其实不太健康。本来就在假期,为什么不能好好休息呢~

目录

8.3 集合覆盖问题

8.4 NP完全问题


8.3 集合覆盖问题

??集合类似于列表,只是不能包含重复的元素;

??你可执行一些有趣的集合运算,如并集、交集和差集。

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

(1)列出集合

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

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

(2)找最小。

近似算法:

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

(2)重复(1)

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

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

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

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

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

代码:

def greedy_algorithm(states, stations):

??? final_stations = set()



??? while states:

??????? best_station = None

??????? states_covered = set()



??????? for station, state_coverage in stations.items():

??????????? covered = states & state_coverage

??????????? if len(covered) > len(states_covered):

??????????????? best_station = station

??????????????? states_covered = covered



??????? final_stations.add(best_station)

??????? states -= states_covered



??? return final_stations



# 示例数据

states = {"state1", "state2", "state3", "state4", "state5"}

stations = {

??? "station1": {"state1", "state2", "state3"},

??? "station2": {"state2", "state4"},

??? "station3": {"state1", "state4", "state5"}

}



# 运行贪婪算法

result = greedy_algorithm(states, stations)



# 输出结果

print("选择的广播电台:", result)

贪婪算法时间vs精确算法时间比较:

广播台数量

精确算法时间(2^n)

贪婪算法时间(n^2)

5

3.2s

2.5s

10

102.4s

10s

32

13.6y

102.4s

100

4*10^21y

16.67min

下面各种算法是否是贪婪算法。

8.3 快速排序。否。(分治,不断将问题缩小规模)

8.4 广度优先搜索。是。(找最小路径)

8.5 狄克斯特拉算法。是。(找最优节点)

贪婪算法(Greedy Algorithm)是一种通过在每一步选择中都采取当前状态下最优(局部最优)的选择,从而希望最终能够达到全局最优解的算法。在每个步骤中,贪婪算法选择当前状态下的最佳解决方案,而不考虑整体的问题。

8.4 NP完全问题

Non-deterministic Polynomial??非确定性多样式

这被称为阶乘函数(factorial function),第3章介绍过。5!=120。假设有10个城市,可能的路线有多少条呢?10!=3628800。换句话说,涉及10个城市时,需要计算的可能路线超过300万条。正如你看到的,可能的路线数增加得非常快!因此,如果涉及的城市很多,根本就无法找出旅行商问题的正确解。旅行商问题和集合覆盖问题有一些共同之处:你需要计算所有的解,并从中选出最小/最短的那个。这两个问题都属于NP完全问题。

近似求解

??元素较少时算法的运行速度非常快,但随着元素数量的增加,速度会变得非常慢。??涉及“所有组合”的问题通常是NP完全问题。

??不能将问题分成小问题,必须考虑各种可能的情况。这可能是NP完全问题。

??如果问题涉及序列(如旅行商问题中的城市序列)且难以解决,它可能就是NP完全问题。

??如果问题涉及集合(如广播台集合)且难以解决,它可能就是NP完全问题。

??如果问题可转换为集合覆盖问题或旅行商问题,那它肯定是NP完全问题。

练习8.6 有个邮递员负责给20个家庭送信,需要找出经过这20个家庭的最短路径。请问这是一个NP完全问题吗??是

8.7 在一堆人中找出最大的朋友圈(即其中任何两个人都相识)是NP完全问题吗?是

8.8 你要制作美国地图,需要用不同的颜色标出相邻的州。为此,你需要确定最少需要使用多少种颜色,才能确保任何两个相邻州的颜色都不同。请问这是NP完全问题吗??是

Np-completeness basics (longest simple path)

Polynomial(多项式)-time algorithms

Worst case running time: O(n^k) for some constant(常数)

There are some problems that cannot be in O(n^k) time.

Loosely speaking, such problems are called “NP-complete” problems

Polynomial: class of problems that are solvable in polynomial time

Np- class of problems that are?“verifiable” in polynomial time

(verify the certificate is correct in polynomial time)

8.5 小结

??贪婪算法寻找局部最优解,企图以这种方式获得全局最优解。

??对于NP完全问题,还没有找到快速解决方案。

??面临NP完全问题时,最佳的做法是使用近似算法。

??贪婪算法易于实现、运行速度快,是不错的近似算法。

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