贪心算法与近似算法

2018/09/01 22:36
阅读数 218

1 贪心算法

1.1 教室调度问题

  假设有如下课程表,你希望将尽可能多的课程安排在某间教室上。

  你没法让这些课都在这间教室上,因为有些课的上课时间有冲突。

  你希望在这间教室上尽可能多的课。如何选出尽可能多且时间不冲突的课程呢?这个问题好像很难,不是吗?实际上,算法可能简单得让你大吃一惊。具体做法如下。
  (1) 选出结束最早的课,它就是要在这间教室上的第一堂课。
  (2) 接下来,必须选择第一堂课结束后才开始的课。同样,你选择结束最早的课,这将是要在这间教室上的第二堂课。重复这样做就能找出答案!下面来试一试。美术课的结束时间最早,为10:00 a.m.,因此它就是第一堂课。

  接下来的课必须在10:00 a.m.后开始,且结束得最早。

  英语课不行,因为它的时间与美术课冲突,但数学课满足条件。最后,计算机课与数学课的时间是冲突的,但音乐课可以。

  因此将在这间教室上如下三堂课。

  很多人都跟我说,这个算法太容易、太显而易见,肯定不对。但这正是贪婪算法的优点——简单易行!贪婪算法很简单:每步都采取最优的做法。在这个示例中,你每次都选择结束最早的课。用专业术语说,就是你每步都选择局部最优解,最终得到的就是全局最优解。信不信由你,对于这个调度问题,上述简单算法找到的就是最优解!显然,贪婪算法并非在任何情况下都行之有效,但它易于实现!下面再来看一个例子。

1.2 背包问题

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

  你力图往背包中装入价值最高的商品,你会使用哪种算法呢?

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

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

  只是这次这种贪婪策略不好使了!例如,你可盗窃的商品有下面三种。

  你的背包可装35磅的东西。音响最贵,你把它给偷了,但背包没有空间装其他东西了。

  你偷到了价值3000美元的东西。且慢!如果不是偷音响,而是偷笔记本电脑和吉他,总价将为3500美元!

  在这里,贪婪策略显然不能获得最优解,但非常接近。动态规划将介绍如何找出最优解。不过小偷去购物中心行窃时,不会强求所偷东西的总价最高,只要差不多就行了。

  从这个示例你得到了如下启示:在有些情况下,完美是优秀的敌人。有时候,你只需找到一个能够大致解决问题的算法,此时贪婪算法正好可派上用场,因为它们实现起来很容易,得到的结果又与正确结果相当接近。

练习:

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

  答:种贪婪策略是,选择可装入卡车剩余空间内的最大箱子,并重复这个过程,直到不能再装入箱子为止。使用这种算法不能得到最优解。

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

  答:不断地挑选可在余下的时间内完成的价值最大的活动,直到余下的时间不够完成任何活动为止。使用这种算法不能得到最优解。

1.3集合覆盖问题

  假设你办了个广播节目,要让全美50个州的听众都收听得到。为此,你需要决定在哪些广播台播出。在每个广播台播出都需要支付费用,因此你力图在尽可能少的广播台播出。现有广播台名单如下。

  每个广播台都覆盖特定的区域,不同广播台的覆盖区域可能重叠。

  如何找出覆盖全美50个州的最小广播台集合呢?听起来很容易,但其实非常难。具体方法如下。

  (1) 列出每个可能的广播台集合,这被称为幂集(power set)。可能的子集有2n个。

  (2) 在这些集合中,选出覆盖全美50个州的最小集合。

  问题是计算每个可能的广播台子集需要很长时间。由于可能的集合有2n个,因此运行时间为O(2n)。如果广播台不多,只有5~10个,这是可行的。但如果广播台很多,结果将如何呢?随着广播台的增多,需要的时间将激增。假设你每秒可计算10个子集,所需的时间将如下。

  没有任何算法可以足够快地解决这个问题!怎么办呢?

2 近似算法

  贪婪算法可化解危机!使用下面的贪婪算法可得到非常接近的解。

  (1) 选出这样一个广播台,即它覆盖了最多的未覆盖州。即便这个广播台覆盖了一些已覆盖的州,也没有关系。

  (2) 重复第一步,直到覆盖了所有的州。

  这是一种近似算法(approximation algorithm)。在获得精确解需要的时间太长时,可使用近似算法。判断近似算法优劣的标准如下:

  • 速度有多快;
  • 得到的近似解与最优解的接近程度。

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

  下面来看看解决这个问题的代码。

1. 准备工作

  出于简化考虑,这里假设要覆盖的州没有那么多,广播台也没有那么多。

  首先,创建一个列表,其中包含要覆盖的州。

states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])

  我使用集合来表示要覆盖的州。集合类似于列表,只是同样的元素只能出现一次,即集合不能包含重复的元素。例如,假设你有如下列表。
  >>> arr = [1, 2, 2, 3, 3, 3]

  并且你将其转换为集合。
  >>> set(arr)
  set([1, 2, 3])

  在这个集合中,1、2和3都只出现一次。

  还需要有可供选择的广播台清单,我选择使用散列表来表示它。

stations = {} 
stations["kone"] = set(["id", "nv", "ut"]) 
stations["ktwo"] = set(["wa", "id", "mt"]) 
stations["kthree"] = set(["or", "nv", "ca"]) 
stations["kfour"] = set(["nv", "ut"]) 
stations["kfive"] = set(["ca", "az"])

   其中的键为广播台的名称,值为广播台覆盖的州。在该示例中,广播台kone覆盖了爱达荷州、内达华州和犹他州。所有的值都是集合。你马上将看到,使用集合来表示一切可以简化工作。

  最后,需要使用一个集合来存储最终选择的广播台。

final_stations = set()

2. 计算答案

  接下来需要计算要使用哪些广播台。根据下边的示意图,你能确定应使用哪些广播台吗?

  正确的解可能有多个。你需要遍历所有的广播台,从中选择覆盖了最多的未覆盖州的广播台。我将这个广播台存储在best_station中。

best_station = None 
states_covered = set() 
for station, states_for_station in stations.items():

   states_covered是一个集合,包含该广播台覆盖的所有未覆盖的州。for循环迭代每个广播台,并确定它是否是最佳的广播台。下面来看看这个for循环的循环体。

covered = states_needed & states_for_station #它计算交集
if len(covered) > len(states_covered):
    best_station = station 
    states_covered = covered

  下面的代码计算交集。
  covered = states_needed & states_for_station

  covered是一个集合,包含同时出现在states_needed和states_for_station中的州;换言之,它包含当前广播台覆盖的一系列还未覆盖的州!接下来,你检查该广播台覆盖的州是否比best_station多。

if len(covered) > len(states_covered): 
    best_station = station 
    states_covered = covered

   如果是这样的,就将best_station设置为当前广播台。最后,你在for循环结束后将best_station添加到最终的广播台列表中。

  final_stations.add(best_station)
  你还需更新states_needed。由于该广播台覆盖了一些州,因此不用再覆盖这些州。
  states_needed -= states_covered
  你不断地循环,直到states_needed为空。这个循环的完整代码如下。 

while states_needed: 
    best_station = None 
    states_covered = set() 
    for station, states in stations.items(): 
        covered = states_needed & states 
        if len(covered) > len(states_covered): 
            best_station = station 
            states_covered = covered   

states_needed -= states_covered 
finalstations.add(beststation)

   最后,你打印final_stations,结果类似于下面这样。
  >>> print final_stations
  set(['ktwo', 'kthree', 'kone', 'kfive'])
  结果符合你的预期吗?选择的广播台可能是2、3、4和5,而不是预期的1、2、3和5。下面来比较一下贪婪算法和精确算法的运行时间。

 注:快速排序属于分治算法,广度优先搜索和狄克斯特拉算法属于贪婪算法。

2.1 NP 完全问题

  为解决集合覆盖问题,你必须计算每个可能的集合。

  这可能让你想起了旅行商问题。在这个问题中,旅行商需要前往5个不同的城市。

  他需要找出前往这5个城市的最短路径,为此,必须计算每条可能的路径。

  前往5个城市时,可能的路径有多少条呢?

旅行商问题详解:

  我们从城市数较少的情况着手。假设只涉及两个城市,因此可供选择的路线有两条。

  这两条路线相同还是不同?

  你可能认为这两条路线相同,难道从旧金山到马林的距离与从马林到旧金山的距离不同吗?不一定。有些城市(如旧金山)有很多单行线,因此你无法按原路返回。你可能需要离开原路行驶一两英里才能找到上高速的匝道。因此,这两条路线不一定相同。

  你可能心存疑惑:在旅行商问题中,必须从特定的城市出发吗?例如,假设我是旅行商。我居住在旧金山,需要前往其他4个城市,因此我将从旧金山出发。

  但有时候,不确定要从哪个城市出发。假设联邦快递将包裹从芝加哥发往湾区,包裹将通过航运发送到联邦快递在湾区的50个集散点之一,再装上经过不同配送点的卡车。该通过航运发送到哪个集散点呢?在这个例子中,起点就是未知的。因此,你需要通过计算为旅行商找出起点和最佳路线。

  在这两种情况下,运行时间是相同的。但出发城市未定时更容易处理,因此这里以这种情况为例。

  涉及两个城市时,可能的路线有两条。

 

  现在假设再增加一个城市,可能的路线有多少条呢?如果从伯克利出发,就需前往另外两个城市。

  从每个城市出发时,都有两条不同的路线,因此总共有6条路线。

  因此涉及3个城市时,可能的路线有6条。

 

  我们再增加一个城市——弗里蒙特。现在假设从弗里蒙特出发。

  从弗里蒙特出发时,有6条可能的路线。这些路线与前面只有3个城市时计算的6条路线很像,只是现在所有的路线都多了一个城市——弗里蒙特!这里有一个规律。假设有4个城市,你选择一个出发城市——弗里蒙特后,还余下3个城市。而你知道,涉及3个城市时,可能的路线有6条。从弗里蒙特出发时,有6条可能的路线,但还可以从其他任何一个城市出发。

  可能的出发城市有4个,从每个城市出发时都有6条可能的路线,因此可能的路线有4 × 6 = 24条。你看出规律了吗?每增加一个城市,需要计算的路线数都将增加。

  涉及6个城市时,可能的路线有多少条呢?如果你说720条,那就对了。7个城市为5040条,8个城市为40320条。

  这被称为阶乘函数(factorial function),假设有10个城市,可能的路线有多少条呢?10! = 3 628 800。换句话说,涉及10个城市时,需要计算的可能路线超过300万条。正如你看到的,可能的路线数增加得非常快!因此,如果涉及的城市很多,根本就无法找出旅行商问题的正确解。

  旅行商问题和集合覆盖问题有一些共同之处:你需要计算所有的解,并从中选出最小/最短的那个。这两个问题都属于NP完全问题。

近似求解:

  对旅行商问题来说,什么样的近似算法不错呢?能找到较短路径的算法就算不错。在继续往下阅读前,看看你能设计出这样的算法吗?

  我会采取这样的做法:随便选择出发城市,然后每次选择要去的下一个城市时,都选择还没去的最近的城市。假设旅行商从马林出发。

  总旅程为71英里。这条路径可能不是最短的,但也相当短了。

  NP完全问题的简单定义是,以难解著称的问题,如旅行商问题和集合覆盖问题。很多非常聪明的人都认为,根本不可能编写出可快速解决这些问题的算法。

 

2.2 如何识别 NP 完全问题

  Jonah正为其虚构的橄榄球队挑选队员。他列了一个清单,指出了对球队的要求:优秀的四分卫,优秀的跑卫,擅长雨中作战,以及能承受压力等。他有一个候选球员名单,其中每个球员都满足某些要求。

  Jonah需要组建一个满足所有这些要求的球队,可名额有限。等等,Jonah突然间意识到,这不就是一个集合覆盖问题吗!

  Jonah可使用前面介绍的近似算法来组建球队。

  (1) 找出符合最多要求的球员。

  (2) 不断重复这个过程,直到球队满足要求(或球队名额已满)。

  NP完全问题无处不在!如果能够判断出要解决的问题属于NP完全问题就好了,这样就不用去寻找完美的解决方案,而是使用近似算法即可。但要判断问题是不是NP完全问题很难,易于解决的问题和NP完全问题的差别通常很小。例如,前一章深入讨论了最短路径,你知道如何找出从A点到B点的最短路径。

  但如果要找出经由指定几个点的的最短路径,就是旅行商问题——NP完全问题。简言之,没办法判断问题是不是NP完全问题,但还是有一些蛛丝马迹可循的。

  • 元素较少时算法的运行速度非常快,但随着元素数量的增加,速度会变得非常慢。
  • 涉及“所有组合”的问题通常是NP完全问题。
  • 不能将问题分成小问题,必须考虑各种可能的情况。这可能是NP完全问题。
  • 如果问题涉及序列(如旅行商问题中的城市序列)且难以解决,它可能就是NP完全问题。
  • 如果问题涉及集合(如广播台集合)且难以解决,它可能就是NP完全问题。
  • 如果问题可转换为集合覆盖问题或旅行商问题,那它肯定是NP完全问题。

练习:

1.有个邮递员负责给20个家庭送信,需要找出经过这20个家庭的最短路径。请问这是一个NP完全问题吗?是的
2.在一堆人中找出最大的朋友圈(即其中任何两个人都相识)是NP完全问题吗?是的
3.你要制作美国地图,需要用不同的颜色标出相邻的州。为此,你需要确定最少需要使用多少种颜色,才能确保任何两个相邻州的颜色都不同。请问这是NP完全问题吗?是的

小结

  • 贪婪算法寻找局部最优解,企图以这种方式获得全局最优解。
  • 对于NP完全问题,还没有找到快速解决方案。
  • 面临NP完全问题时,最佳的做法是使用近似算法。
  • 贪婪算法易于实现、运行速度快,是不错的近似算法。

 

 

 

 

 

 

 

 



 

 



 

 

 

 

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部