了解贪心、分治、回溯算法和动态规划的算法思想

王铮老师《算法》系列文章之37-。

提纲:

贪心算法 greedy algorithm

  • 贪心算法并不能总是给出最优解:有权图中找最短路径;
  • 分糖果:
  • 钱币找零
  • 区间覆盖

Huffman Coding:

文本中不同字符个数 + 字符出现频率

编码方式:

字符看作结点并带有频率,所有节点在优先级队列中,每次选择最小的结点组成新的父结点,再放入队列中。

https://static001.geekbang.org/resource/image/7b/7a/7b6a08e7df45eac66820b959c64f877a.jpg

分治算法

divide and conquer:将原问题划分为n个小规模问题,且结构相似。可递归解决这些子问题,然后合并结果。

  • 分治 思想

  • 递归 编程

  • 逆序度、有序度

在归并排序中,合并两个有序的数组过程中,就可以计算两个数组的逆序对个数。如图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 此处难以下笔,归并都忘得差不多了!
private int num = 0; //全局变量or成员变量

public int count(int[] a, int n){
num = 0;
mergeSortCounting(a, 0, n-1);
return num;
}

private void mergeSortCounting(int[] a, int p, int r){

}

private void merge(int[] a, int p, int q, int r){ // low middle high

}

二维平面上有 n 个点,如何快速计算出两个距离最近的点对?

有两个 n*n 的矩阵 A,B,如何快速求解两个矩阵的乘积 C=A*B?

在海量数据处理中

扫描10GB的订单,划分金额区间,存储文件。单独加载小文件到内存中排序。最终合并即可。

MapReduce

MapReduce框架是一个任务调度器,本质为分治思想,底层使用GFS存储数据,使用Borg管理机器。

回溯算法

八皇后问题

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
59
60
61
62
63
package com.youdef.DataStructureAndAlgo;

/*
八皇后问题:
递归
*/

public class EightQueens {
public static void main(String[] args){
call8queens(0);
}


static int[] result = new int[8]; //全局变量or成员变量,这里下标表示行,值表示queen存储的列
static int ccc = 1; //统计打印次数

public static void call8queens(int row){
if (row == 8){ //8行棋子都放好了,结束
printQueens(result);
return;
}
for (int column=0; column<8; ++column){ //每一行中有8个格子,依次检查放法
if (isOk(row, column)){
result[row] = column; //若放法满足要求, 第row行棋子放到column列
call8queens(row+1); //考察下一行
}
}

}

public static boolean isOk(int row, int column){//判断row行column列 放置是否合适
int leftup = column-1, rightup = column+1; //这里是怎样安排的??
for (int i=row-1; i>=0; --i){ //逐行检查 每一行
//第i行 第column列 是否有棋子
if (result[i] == column) return false;
//左上角对角线:第i行leftup列有棋子吗
if (leftup >= 0){
if (result[i] == leftup) return false;
}
//考察右上角对角线,第i行rightup列有棋子吗
if (rightup < 8){
if (result[i] == rightup) return false;
}
--leftup; ++rightup;
}
return true;
}

public static void printQueens(int[] result){ //打印二维矩阵
System.out.println("第 "+ccc+" 种:");
ccc++;

for (int row=0; row<8; ++row){
for (int column=0; column<8; ++column){
if (result[row]== column) System.out.print("Q ");
else System.out.print("* ");
}
System.out.println();
}
System.out.println();
}
}

0-1背包问题

这里的背包问题中物体是不可分割的,要么装要么不装。这里使用回溯算法解决:

1
2
//见程序

正则表达式

动态规划


了解贪心、分治、回溯算法和动态规划的算法思想
https://youdef.com/posts/46/
作者
阿成
发布于
2020年9月27日
许可协议