贪心算法讲解（集合覆盖问题，旅行商问题求解）

小灰灰 2023-01-04 10:22 165阅读 0赞

## 教室调度问题 ##

假设有如下课程表，你希望将尽可能多的课程安排在某间教室上。  
![20210109132903209.png_pic_center][]

你没法让这些课都在这间教室上，因为有些课的上课时间有冲突。  
![20210109133049278.png_pic_center][]

你希望在这间教室上尽可能多的课。如何选出尽可能多且时间不冲突的课程呢?  
这个问题好像很难，不是吗?实际上，算法可能简单得让你大吃-一惊。具体做法如下。

1.  选出结束最早的课，它就是要在这间教室上的第一-堂课。
2.  接下来，必须选择第一-堂 课结束后才开始的课。同样，你选择结束最早的课，这将是要在这间教室上的第二堂课。
3.  重复这样做就能找出答案!下面来试- -试。 美术课的结束时间最早，为10:00 a.m,因此它就是第一堂课。接下来的课必须在10:00 a.m.后开始，且结束得最早。英语课不行，因为它的时间与美术课冲突，但数学课满足条件。最后，计算机课与数学课的时间是冲突的，但音乐课可以。

![20210109133521527.png_pic_center][]

很多人都跟我说，这个算法太容易、太显而易见，肯定不对。但这正是贪婪算法的优点一简单易行! 贪婪算法很简单:每步都采取最优的做法。在这个示例中，你每次都选择结束最早的课。用专业术语说，就是你每步都选择局部最优解，最终得到的就是;全局最优解。信不信由你，对于这个调度问题，上述简单算法找到的就是最优解!

贪心算法可能找到的不是最优解，但接近最优解啦。

## 集合覆盖问题 ##

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

每个广播台都覆盖特定的区域，不同广播台的覆盖区域可能重叠。  
![20210109140103202.png_pic_center][]

我们用贪心算法求解

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

1.  选出这样-一个广 播台，即它覆盖了最多的未覆盖州。即便这个广播台覆盖了一些已覆盖的州，也没有关系。
2.  重复第-步，直到覆盖了所有的州。

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

**全部代码**  
语言：python

#创建一个列表，其中包含要覆盖的州
    states_needed = set(["mt" ,"wa", "or", "id", "nv", "ut","ca", "az"])
    #还需要有可供选择的广播台清单，我选择使用散列表来表示它
    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'])
    
    #最后，需要使用一个集合来存储最终选择的广播台。
    finnal_stations=set()
    #计算答案
    
    while len(states_needed)>0:#直到所有州都覆盖完，剩余列表的州为空
        best_stations = None
        state_covered = set()  # states_ covered是-一个集合， 包含该广播台覆盖的所有未覆盖的州。
        for station, states in stations.items():#for循环迭代每个广播台，并确定它是否是最佳的广播台。
            covered=states_needed & states #剩余列表中的州 and 电视台覆盖的州 （取交集）
            if len(covered)>len(state_covered): #取交集最大的电视台
                best_stations=station
                state_covered=covered
        states_needed -=state_covered#剩余列表里州
        finnal_stations.add(best_stations)
    
    print(finnal_stations)
    print('结束')

![20210109145624716.png_pic_center][]

## 旅行商问题 ##

旅行商问题(TravelingSalesmanProblem，TSP)一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要遍历所有城市一次且只能一次，回到出发地。应如何选择行进路线，以使总的行程最短。目前解决TSP问题的方法有许多种，比如：贪心算法、动态规划算法、分支限界法；也有智能算法。本文先介绍贪心算法：  
![20210109145948821.png_pic_center][]

数据 如下图，第一列城市名。第二列坐标x，第三列坐标y  
![20210109151013345.png_pic_center][]

语言：python  
贪心算法思路：随便选择出发城市，然后每次选择要去的下一个城市时，都选择还没去的最近的城市。

第一步：读取数据

import pandas as pd
    import numpy as np
    import math
    import time
    
    dataframe = pd.read_csv("TSP.csv", sep=",", header=None)
    v = dataframe.iloc[:, 1:3]#去除第一列12345678910,只保留x,y
    print(v)

![20210109151754273.png_pic_center][]

第二步：计算城市之间的距离

train_v= np.array(v)
    train_d=train_v
    #初始化距离 为10*10的全0矩阵
    dist = np.zeros((train_v.shape[0],train_d.shape[0]))
    #print(dist.shape)#(10,10)
    
    #计算距离矩阵
    for i in range(train_v.shape[0]):
        for j in range(train_d.shape[0]):
            dist[i,j] = math.sqrt(np.sum((train_v[i,:]-train_d[j,:])**2))
    print(dist)

![20210109151914927.png_pic_center][]

第三步：计算距离和路径

""" s:已经遍历过的城市 dist：城市间距离矩阵 sumpath:目前的最小路径总长度 Dtemp：当前最小距离 flag：访问标记 """
    
    i=1
    n=train_v.shape[0]#城市个数
    j=0
    sumpath=0#目前的最小路径总长度
    s=[]#已经遍历过的城市
    s.append(0)#从城市0开始
    start = time.clock()
    while True:
        k=1#从1开始,因为人在城市0，所以我们设定先从城市1开始选择
        Detemp=float('inf')#当前最小距离
        while True:
            flag=0#访问标记，否0
            if k in s:#是否访问，如果访问过，flag设为1
                flag = 1
            if (flag==0) and (dist[k][s[i-1]] < Detemp):#如果未访问过，并且距离小于最小距离
                j = k;
                Detemp=dist[k][s[i - 1]];#当前两做城市相邻距离
            k+=1#遍历下一城市
            if k>=n:
                break;
        s.append(j)
        i+=1;
        sumpath+=Detemp
        if i>=n:
            break;
    
    sumpath+=dist[0][j]#加上dist[0][j] 表示最后又回到起点
    end = time.clock()
    print("结果：")
    print(sumpath)
    for m in range(n):
        print("%s-> "%(s[m]),end='')
    print()
    print("程序的运行时间是：%s"%(end-start))

![20210109153449994.png_pic_center][]

该段代码借鉴 他人

代码解析：数字k表示当前我们选择前往下一个城市时，我们需要计算所有未访问过的城市和当前城市距离。  
数字i 用于控制访问过的城市，我们需要到达每一个城市。

代码中有两个while  
里面那个while表示选择下一城市时，需要遍历所有未访问过的城市，然后选择距离当前城市最近的城市，赋值给j  
外面while，表示我们的每一步，我们需要去每个城市。

![在这里插入图片描述][2021010915454422.jpg_pic_center]  
作者：电气-余登武  
![在这里插入图片描述][20210109154621809.gif_pic_center]

[20210109132903209.png_pic_center]: /images/20221119/233a36824ff144d18f1e62448c43a7a7.png
[20210109133049278.png_pic_center]: /images/20221119/b093f5a0b921480389a9719b9cfb5450.png
[20210109133521527.png_pic_center]: /images/20221119/1bc1b2b78e294841a48a81af728ffdb4.png
[20210109134830646.png_pic_center]: https://img-blog.csdnimg.cn/20210109134830646.png#pic_center
[20210109135956292.png_pic_center]: /images/20221119/47d4a7499e294afbbf1d37f269a1cc21.png
[20210109140103202.png_pic_center]: /images/20221119/cba0d8f9fef4439099bf1349f00db998.png
[20210109145624716.png_pic_center]: /images/20221119/43e6800e41c74a73a599d02e590658b7.png
[20210109145948821.png_pic_center]: /images/20221119/9427cd36b5db4a588688c05199b8ed93.png
[20210109151013345.png_pic_center]: /images/20221119/a946900268d14b97856a5ec5f9b87289.png
[20210109151754273.png_pic_center]: /images/20221119/cbcd38db7ad940dc8dac9cd23c788b4d.png
[20210109151914927.png_pic_center]: /images/20221119/4a8161fb9f714a48bd9f35bc3bf65d5a.png
[20210109153449994.png_pic_center]: https://img-blog.csdnimg.cn/20210109153449994.png#pic_center
[2021010915454422.jpg_pic_center]: https://img-blog.csdnimg.cn/2021010915454422.jpg#pic_center
[20210109154621809.gif_pic_center]: https://img-blog.csdnimg.cn/20210109154621809.gif#pic_center