1. 1. 贪心算法
  2. 2. 相关应用
    1. 2.1. 活动安排问题
    2. 2.2. 背包问题
    3. 2.3. 最优装载
    4. 2.4. 哈夫曼树与哈夫曼编码
    5. 2.5. 单源最短路径（Dijkstra）
    6. 2.6. 最小生成树
    7. 2.7. 多机调度问题
【算法】贪心算法
算法

贪心算法

贪心算法，是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法。它不从整体最优上加以考虑，所做出的仅是某种意义上的局部最优解。

贪心算法的基本思路：

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

贪心算法的基本要素：

  • 具有最优子结构性质，即一个问题的最优解包含其子问题的最优解

相关应用

活动安排问题

设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求，使用该资源的起始时间si和一个结束时间fi,且si < fi，如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si >= fj或sj >= fi时，活动i与活动j相容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function greedySelector (s, f, a = []) {
  let j = 0
  let count = 1
  a[0] = true
  for (let i = 1; i < s.length; i ++) {
    if (s[i] >= f[j]) {
      a[i] = true
      j = i
      count ++
    } else {
      a[i] = false
    }
  }
  return count
}


const res = greedySelector([1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12], [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]) // 4

// a = [ true, false, false, true, false, false, false, true, false, false, true ]

由于输入的活动为其完成时间的非减序排列，所以greedySelector每次总是选择具有最早完成时间的相容活动加入集合a中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。

对于活动安排问题，贪心算法总能求得整体的最优解。

背包问题

给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品， 使得装入背包中物品的总价值最大?

0-1 背包问题：在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包和不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。

部分背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包。

这两类问题都具有最优子结构性质，极为相似，但部分背包问题可以用贪心算法求解，而0-1背包问题却不能。

1
2
3
4
5
6
7
8
9
10
objects[] = [
  {weight: 35, value: 10},
  {weight: 30, value: 40},
  {weight: 60, value: 30},
  {weight: 50, value: 50},
  {weight: 40, value: 35},
  {weight: 10, value: 40},
  {weight: 25, value: 30}
]
c = 150

部分背包问题求解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function knapsack (c, objects) {
  let totalValue = 0
  let i = 0
  objects.sort((a, b) => {
    // 将各物品依其单位重量的价值从大到小排序
    return (a.value / a.weight) < (b.value / b.weight)
  })
  for (; i < objects.length; i ++) {
    const obj = objects[i]
    if (obj.weight > c) break
    // 当物品重量小于背包容量时，物品放入一件
    totalValue += obj.value
    c -= obj.weight
  }
  if (i < objects.length) { // 当无法放入一整个物品时，选取物品一部分放入
    const obj = objects[i]
    totalValue += c / obj.weight * obj.value
  }
  return totalValue
}

对于0-1背包问题，贪心算法之所以不能得到最优解是因为它无法保证最终能将背包装满，部分背包空间的闲置使每单位重量的背包空间所具有价值降低了。事实上，在考虑0-1背包问题的物品选择时，应比较选择该物品和不选择该物品所导致的最终结果，然后再作出最好的选择。由此就导出许多互相重叠的子问题，而这个问题则需要用动态规划算法来解决。

最优装载

有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

1
2
3
4
5
6
7
8
9
function loading (c, w) {
  let res = []
  w.sort((a, b) => b - a)
  for (let i = 0; i < w.length && w[i] <= c; i ++) {
    c -= w[i]
    res.push(w[i])
  }
  return res
}

哈夫曼树与哈夫曼编码

从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称作路径长度。树的路径长度就是从树根到每一个结点的路径长度之和。

考虑到带权的结点，结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。其中带权路径长度WPL最小的二叉树称作哈夫曼树。

哈夫曼树的构造过程：

  1. 先把有权值的叶子结点按照从小到大的顺序排列成一个有序序列，即：A5，E10，B15，D30，C40。
  2. 取头两个最小权值的结点作为一个新结点N1的两个子结点，相对小的为左孩子，大的为右孩子。
  3. 将N1替换A、E，插入有序序列中，保持从大到小排列。即N1 15，B15，D30，C40。
  4. 重复上述步骤知道排完所有结点。由此构造出来的二叉树即为哈夫曼树。

而哈夫曼编码，其实就是构造一棵哈夫曼树的过程。将左分支视为0，右分支视为1，则以上的ABCDE可以分别表示为：

字母 A B C D E
二进制编码 1000 101 0 11 1001

单源最短路径（Dijkstra）

给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称 为单源最短路径问题。

Dijkstra算法的基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。

初始时，S中仅含有源。设u是G的某个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路径长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中的顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。

1
2
3
4
5
6
7
8
// 输入的路径矩阵，Infinity表示不通
matrix = [
  [Infinity, 10, Infinity, 30, 100],
  [Infinity, Infinity, 50, Infinity, Infinity],
  [Infinity, Infinity, Infinity, Infinity, 10],
  [Infinity, Infinity, 20, Infinity, 60],
  [Infinity, Infinity, Infinity, Infinity, Infinity]
]

Dijkstra算法的迭代过程：

迭代 S u dist[2] dist[3] dist[4] dist[5]
初始 {1} - 10 maxint 30 100
1 {1, 2} 2 10 60 30 100
2 {1, 2, 4} 4 10 50 30 90
3 {1, 2, 4, 3} 3 10 50 30 60
4 {1, 2, 4, 3, 5} 5 10 50 30 60 
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
function dijkstra (matrix, start) {
  const rows = matrix.length
  const cols = matrix[0].length

  let dist = new Array(rows).fill(Infinity)
  let visited = new Array(rows).fill(false)
  
  dist[start] = 0

  while (visited.some(item => !item)) {
    // 更新节点访问
    visited[start] = true
    // 达到不了的顶点不能作为中转跳点
    if (dist[start] < Infinity) {
      for (let i = 0; i < cols; i ++) {
        // 更新dist[i]
        if (matrix[start][i] + dist[start] < dist[i]) {
          dist[i] = matrix[start][i] + dist[start]
        }
      }
    }
    // 找到当前最短路径顶点作为中转
    let minIndex = -1
    let min = Infinity
    for (let k = 0; k < rows; k ++) {
      if (!visited[k] && dist[k] < min) {
        min = dist[k]
        minIndex = k
      }
    }
    start = minIndex
  }
  return dist
}

对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O(n)时间。这个循环需要执行n-1次，所以完成循环需要O(n²)时间。算法的其余部分所需要时间不超过O(n²)。

最小生成树

设G =(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。

网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权c[v][w]表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。

最小生成树的性质：

设G=(V,E)是连通带权图，U是V的真子集。如果 (u,v)∈E，且u∈U，v∈V-U，且在所有这样的边中， (u,v)的权c[u][v]最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为 MST性质。最小生成树的算法Prim算法和Kruskal算法都利用了这个性质。

1
2
3
4
5
6
7
8
matrix = [
  [Infinity, 6, 1, 5, Infinity, Infinity],
  [6, Infinity, 5, Infinity, 3, Infinity],
  [1, 5, Infinity, 5, 6, 4],
  [5, Infinity, 5, Infinity, Infinity, 2],
  [Infinity, 3, 6, Infinity, Infinity, 6],
  [Infinity, Infinity, 4, 2, 6, Infinity]
]

边的表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Edge {
  constructor (begin, end, weight) {
    this.begin = begin
    this.end = end
    this.weight = weight
  }

  getBegin () {
    return this.begin
  }

  getEnd () {
    return this.end
  }

  getWeight () {
    return this.weight
  }
}

Prim算法:

设G=(V,E)是连通带权图，V={1,2,…,n}。构造G的最小生成树的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件i∈S，j∈V-S，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。

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
function prim (matrix) {
  const len = matrix.length
  let result = [],
      adjVex = new Array(len).fill(0), // 保存相关顶点下标
      lowCost = matrix[0] // 保存相关顶点间边的权值
  // 两层循环，时间复杂度O(n²)
  for (let i = 1; i < len; i ++) {
    let minWeight = Infinity, // 初始化最小权值为无限大
        minVex = -1
    for (let j = 1; j < len; j ++) {
      if (lowCost[j] !== 0 && lowCost[j] < minWeight) {
        minWeight = lowCost[j]
        minVex = j
      }
    }
    result.push(new Edge(adjVex[minVex], minVex, minWeight))
    lowCost[minVex] = 0 // 将当前顶点的权值置为0，说明此顶点已完成任务
    for (let j = 1; j < len; j ++) { // 循环所有顶点
      if (lowCost[j] !== 0 && matrix[minVex][j] < lowCost[j]) {
        lowCost[j] = matrix[minVex][j] // 找出较小权值存入lowCost
        adjVex[j] = minVex // 记录下标
      }
    }
  }
  return result
}

// [ 
//   Edge { begin: 0, end: 2, weight: 1 },
//   Edge { begin: 2, end: 5, weight: 4 },
//   Edge { begin: 5, end: 3, weight: 2 },
//   Edge { begin: 2, end: 1, weight: 5 },
//   Edge { begin: 1, end: 4, weight: 3 } 
// ]

Kruskal算法:

Kruskal算法构造G的最小生成树的基本思想是， 首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时， 就用边(v,w)将T1和T2连接成一个连通分支，然后继续 查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。

与Prim算法不同，Kruskal算法是从最小权值的边开始的，所以使用边集数组更方便。所以需要将邻接矩阵转成边集数组，并且按照边的权重从小到大排序。

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
// 邻接矩阵转成边集数组
function changeMatrixToEdgeArray (matrix) {
  const len = matrix.length
  let result = []
  for (let i = 0; i < len; i ++) {
    const row = matrix[i]
    for (let j = 0; j < len; j ++) {
      if (row[j] !== 0 && row[j] !== Infinity) {
        result.push(new Edge(i, j, row[j]))
        // 已加入的边做标记不再重复加入
        matrix[i][j] = Infinity
        matrix[j][i] = Infinity
      }
    }
  }
  // 将边权数组按从小到大排序
  result.sort((a, b) => a.getWeight() - b.getWeight())
  return result
}

function kruskal (matrix) {
  const edgeArray = changeMatrixToEdgeArray(matrix),
        len = edgeArray.length
  let result = [],
      parent = new Array(len).fill(0) // 判断边与边是否形成环路
  for (let i = 0; i < len; i ++) {
    const edge = edgeArray[i]
    const n = findEnd(parent, edge.getBegin())
    const m = findEnd(parent, edge.getEnd())
    if (n !== m) { // 不相等说明此边没有与现有生成树形成环路
      // 将此边的结尾顶点放入parent，表示此顶点已经在生成树集合中
      parent[n] = m
      result.push(edge)
    }
  }
  return result
}

function findEnd(arr, start) {
  //就是一直循环，直到找到终点，如果没有连线，就返回0
  while (arr[start] > 0) {
    start = arr[start]
  }
  return start
}

// [ 
//   Edge { begin: 0, end: 2, weight: 1 },
//   Edge { begin: 3, end: 5, weight: 2 },
//   Edge { begin: 1, end: 4, weight: 3 },
//   Edge { begin: 2, end: 5, weight: 4 },
//   Edge { begin: 1, end: 2, weight: 5 } 
// ]

多机调度问题

多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。（条件：每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。）

这个问题是NP完全问题，到目前为止还没有有效的解法。对于这类问题，用贪心选择策略有时可以设计出较好的近似算法。

采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。按此策略，当n<=m时，只要将机器i的[0, ti]时间区间分配给作业i即可，算法只需要O(1)时间。 当n>m时，首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(nlogn)。

例如，设7个独立作业{1,2,3,4,5,6,7}由3台机器 M1，M2和M3加工处理。各作业所需的处理时间分别为 {2,14,4,16,6,5,3}。按算法greedy产生的作业调度如下图所示，所需的加工时间为17。

Previous post
Next post