算法学习笔记（一）——贪心算法（先发回校改（如果不忘，标记下））

Natalie ·

更新时间:2024-11-10

· 979 次阅读

贪心算法：在对问题求解时，总是做出在当前看来是最好的选择，即不从整体最优上考虑问题，而是从局部做出最优解

因此，贪心算法不能够对所有问题得到最优解，选择的贪心策略必须具备无后效性，即某个状态之后的过程不会影响到以前的状态，而只与当前的状态有关

基本思路：1、建立数学模型描述问题；

2、把求解的问题分成若干子问题

3、把对每一个子问题求解，得到子问题的局部最优解

4、把子问题的局部最优解合成为原来问题的一个解

例子，最短路径问题

从 u 到 v 的最短路径权值，小于等于从 u 到 x 的最短路径权值加上从 x 到 v 的最短路径权值，即


# 图解算法——dijkstra算法
def find_lowest_cost_node(costs):
    lowest_cost = float('inf')
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost  new_cost:        # 如果经当前节点前往该邻居更近，则更新
            costs[n] = new_cost
            parents[n] = node          # 同时更新父节点
    processed.append(node)             # 将当前节点标记为处理过
    node = find_lowest_cost_node(costs)  # 寻找下一个要处理的节点
print(costs)

例子，集合覆盖问题，这个例子来自《算法图解》一书

其背景是，不同的广播台可以在不同的州广播，如何选择最优或者次优的广播台集合使得可以覆盖所有的州


# 算法图解——集合覆盖问题
arr = ['mt','wa','or','id','nv','ut','ca','az']
states_needed = set(arr)
# 集合类似列表，但是同样的元素只能出现一次
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'])
final_stations = set()
while states_needed:           # 不断循环，直到states_needed为空
    best_station = None        # 选择的广播台
    states_covered = set()     # 广播台覆盖的州
    for station, states_for_station in stations.items():
        covered = states_needed & states_for_station  # 交集
        if len(covered) > len(states_covered):
            best_station = station
            states_covered = covered
    states_needed -= states_covered      # 因为不需要重复覆盖，所以要更新
    final_stations.add(best_station)
print(final_stations)

作者：timedecdec

学习笔记标记学习如果贪心算法算法

1024 个赞