贪心算法
概述
贪心算法每步都采取当前最优(局部最优),最终得到一个全局最优的方案;
教室调度问题:
注:
- 上述中选择最早结束的课程的策略可以找到教室调度问题最优解;
- 选择最小占用时间的课程得不到最优解;
- 选择最早开始的课程得不到最优解;
- 贪心算法不是任何情况下都有效,但容易实现;
Prim
基本概念:生成树、最小生成树
算法核心:从连通$$V_T$$和$$V-V_T$$的边中挑选一条权重最小的边。
- 任意选一点$$v_0$$,集合V被分割成两个集合$$V_T={v_0}$$和$$V-V_T$$;
- 从连通$$V_T$$和$$V-V_T$$的边中挑选一条权重最小的边$$e^=(v^,u^),v^ \in V_T,u^* \in V-V_T$$,将$$u^$$加入$$V_T$$中,从$$V - V_T$$删除$$u^$$;
- 重复步骤2,直到集合$$V-V_T$$为空;
python
def cmp(key1, key2):
return (key1, key2) if key1 < key2 else (key2, key1)
def prim(graph, init_node):
visited = {init_node}
candidate = set(graph.keys())
candidate.remove(init_node) # 添加所有除开始定点的其他顶点
tree = []
while len(candidate) > 0:
edge_dict = dict()
for node in visited: # 找到所有已访问的节点
for connected_node, weight in graph[node].items(): # 拿到与该节点相连的节点
if connected_node in candidate: # 没访问过就加入待选集
edge_dict[cmp(connected_node, node)] = weight
edge, cost = sorted(edge_dict.items(), key=lambda kv: kv[1])[0] # 从待选集找到最小的权重路径
tree.append(edge)
visited.add(edge[0]) # 把选中的加入已访问集合
visited.add(edge[1])
candidate.discard(edge[0]) # 把选中的移除已访问集合
candidate.discard(edge[1])
return tree
Kruskal
算法贪婪地选择最小权重的边,扩展无环的子图构造最小生成树。
- 按照权重非递减顺序对途中的边E进行排序;
- 烧苗已排序的列表,如果下一条边加入当前的子图中不导致一个回路,则加入该边到子图中,否则跳过该边;
- 重复步骤2,直到子图中有$$|V|-1$$条边;
python
def cmp(key1, key2):
return (key1, key2) if key1 < key2 else (key2, key1)
def find_parent(record, node):
if record[node] != node:
record[node] = find_parent(record, record[node])
return record[node]
def naive_union(record, edge):
u, v = find_parent(record, edge[0]), find_parent(record, edge[1])
record[u] = v
def kruskal(graph):
edge_dict = {}
for node in graph.keys():
# cmp把字母的顺序交换,update去除相同的键从而去重
edge_dict.update({cmp(node, k): v for k, v in graph[node].items()})
# 按权重排序的边集合
sorted_edge = list(sorted(edge_dict.items(), key=lambda kv: kv[1]))
tree = []
connected_records = {key: key for key in graph.keys()}
for edge_pair, _ in sorted_edge:
if find_parent(connected_records, edge_pair[0]) != \
find_parent(connected_records, edge_pair[1]):
tree.append(edge_pair)
naive_union(connected_records, edge_pair)
return tree
难点:判断新加入的边是否构成回路
并查集的思想
基本
- connected_records:生成一个单元素集合;
- find_parent(x):返回一个包含x的子集;
- union(x, y):构造分别包含x和y的不相交子集的并集;
要点
- 按照权重$$w(e_1) \leq ... \leq w(e_{|E|})$$的非递增顺序对集合E排序;
- 判断$$find(a)$$是否等于$$find(b)$$,如果不相等,union(a,b);
算法效率分析
- 第一步的时间复杂度为$$O(|E|log|E|)$$(快速排序);
- 第二步$$find(x)$$和$$union(a, b)$$的复杂度取决于实现方式;
- 快速查找:$$T(find) \in O(1),T(union) \in O(nlogn)$$(所有合并);
- 快速求并:$$T(find) \in O(logn),T(union) \in O(1)$$;
- 快速查找下总的效率为$$O(|E|log|E|)+O(m+|V|log|V|)$$;
- 快速求并下总的效率为$$O(|E|log|E| + O(mlog|V|+|V|))$$;
Dijkstra
和Prim类似,不过选择下一条路径时并不是判断的是当前权重,而是整条路径的权重作比较