Greedy Algorithm

定义

贪心算法,是指在对问题求解时,总是做出再当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是某种意义上的局部最优解。贪心算法没有固定算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。

基本思路

  1. 建立数学模型来描述问题
  2. 把求解的问题分成若干个子问题
  3. 对每一子问题求解,得到子问题的局部最优解
  4. 把子问题的解局部最优解合成原来解问题的一个解

适用的问题

局部最优策略能导致产生全局最优解

最小生成树问题

给定一个无向联通带权图G(V,E). G中的每一条边$E_i$权值为$w_i$。如果G的子图G’是一个包含G中所有顶点的子图,那么G’称为G的最小生成树,如果G’的边的权值最小.

Kruskal算法

Kruskal算法是基于贪心的思想得到的。首先我们把所有的边按照权值先从小到大排列,接着按照顺序选取每条边,如果这条边的两个端点不属于同一集合,那么就将它们合并,直到所有的点都属于同一个集合为止。至于怎么合并到一个集合,那么这里我们就可以用到一个工具——-并查集。换而言之,Kruskal算法就是基于并查集的贪心算法。

  1. 将图G看做一个森林,每个顶点为一棵独立的树
  2. 将所有的边加入集合S,即一开始S = E
  3. 从S中拿出一条最短的边(u,v),如果(u,v)不在同一棵树内,则连接u,v合并这两棵树,同时将(u,v)加入生成树的边集E’
  4. 重复(3)直到所有点属于同一棵树,边集E’就是一棵最小生成树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class UnionFind():
def __init__(self,items):
self.parent = {item:item for item in items}

def get_root(self, i):
while i != self.parent[i]:
i = self.parent[i]
return i

def is_connected(self, i, j):
return self.get_root(i) == self.get_root(j)

def union(self, i, j):
i_root = self.get_root(i)
j_root = self.get_root(j)
self.parent[i_root] = j_root


def kruskal(G):
nodes = list(G.keys())
uf = UnionFind(nodes)

res_deges = set()
res_weight = 0

edges = set()
for node_1 in G:
for node_2 in G[node_1]:
if node_1 < node_2:
edges.add((node_1,node_2, G[node_1][node_2]))
else:
edges.add((node_2,node_1, G[node_1][node_2]))
edges = list(edges)
edges.sort(key = lambda edge: edge[-1])

for edge in edges:
node_1,node_2,weight = edge
if not uf.is_connected(node_1,node_2):
uf.union(node_1,node_2)
res_deges.add(edge)
res_weight += weight

return res_deges,res_weight



if __name__ == '__main__':
graph = {'A':{'B':7,'D':5},
'B':{'A':7,'C':8,'D':9,'E':7},
'C':{'B':8,'E':5},
'D':{'A':5,'B':9,'E':15,'F':6},
'E':{'B':7,'C':5,'D':15,'F':8,'G':9},
'F':{'D':6,'E':8,'G':11},
'G':{'E':9,'F':11}
}
edges, weight = kruskal(graph)
print(edges)
print(weight)

Prim算法

  1. 以某一个点开始,寻找当前该点可以访问的所有的边;
  2. 在已经寻找的边中发现最小边,这个边必须有一个点还没有访问过,将还没有访问的点加入我们的集合,记录添加的边;
  3. 寻找当前集合可以访问的所有边,重复2的过程,直到没有新的点可以加入;
  4. 此时由所有边构成的树即为最小生成树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def prim(graph, root):

nodes = list(graph)
nodes.remove(root)
visited = [root]
edges = set()
weight = 0

while nodes:
distance = float('inf')
for s in visited:
for d in graph[s]:
if d in visited or s == d:
continue
if graph[s][d] < distance:
distance = graph[s][d]
node_1 = s
node_2 = d
edges.add((node_1,node_2,graph[node_1][node_2]))
weight += graph[node_1][node_2]
visited.append(node_2)
nodes.remove(node_2)

return edges,weight



if __name__ == '__main__':
graph = {'A':{'B':7,'D':5},
'B':{'A':7,'C':8,'D':9,'E':7},
'C':{'B':8,'E':5},
'D':{'A':5,'B':9,'E':15,'F':6},
'E':{'B':7,'C':5,'D':15,'F':8,'G':9},
'F':{'D':6,'E':8,'G':11},
'G':{'E':9,'F':11}
}

edges, weight = prim(graph,'A')
print(edges)
print(weight)

leetcode 455 Assign Cookies

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:
You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.

Example 1:

Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Example 2:

Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

因为最小的孩子最容易得到满足,因此先满足最小孩子。给一个孩子的饼干应当尽量小又能满足该孩子,这样大饼干就能拿来给满足度比较大的孩子。
假设在某次选择中,贪心策略选择给第 i 个孩子分配第 m 个饼干,并且第 i 个孩子满足度最小,第 m 个饼干为可以满足第 i 个孩子的最小饼干,利用贪心策略最终可以满足 k 个孩子。假设最优策略在这次选择中给 i 个孩子分配第 n 个饼干,并且这个饼干大于第 m 个饼干。我们发现使用第 m 个饼干去替代第 n 个饼干完全不影响后续的结果,因此不存在比贪心策略更优的策略,即贪心策略就是最优策略。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
res = 0; i = 0; j = 0
g.sort()
s.sort()

while i < len(g) and j < len(s):
if g[i] <= s[j]:
res += 1
i+=1
j+=1

return res
Donate article here