深入浅出讲算法思想--蛮力法思想分析及应用
**蛮力法（brute force method，也称为穷举法或枚举法）**是一种简单直接地解决问题的方法，常常直接基于问题的描述，所以，蛮力法也是最容易应用的方法。虽然，用蛮力法设计的算法时间特性往往也是最低的，但是许多问题我们一开始并没有很优化的算法，而蛮力法则可以帮助我们从低效的算法结构中剖析低效的缘由，进而提炼出更为优化的算法。
- 蛮力法在排序算法中的应用--选择排序、冒泡排序
- 蛮力法在查找算法中的应用
- 蛮力法在字符串匹配问题中的应用
- 蛮力法在求解“最近对”问题中的应用
- 蛮力法在求解凸包问题中的应用
- 蛮力法在求解最优解问题中的应用--TSP，背包问题，配对问题
一、蛮力法在排序算法中的应用--选择排序、冒泡排序
对于一个排序问题，我们能想到的最简单的排序方法就是选择和冒泡
**1、选择排序：**时间复杂度O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public class Main {
public static void main(String[] args) {
int[] a = {89, 45, 68, 90, 29, 34, 17};
int min;
for (int i = 0; i < a.length-1; i++) {
min = i;
for (int j = i+1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j;
}
}
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}
选择排序的思路就是如此，虽也有优化思路，例如每次迭代出最大值和最小值，放在开头和结尾。但是选择排序必然要编译算真整个数组，所以最好的优化结果也是O(n^2)。
**2、冒泡排序：**时间复杂度O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public class Main {
public static void main(String[] args) {
int[] a = {89, 45, 68, 90, 29, 34, 17};
int min;
for (int i = 0; i < a.length-1; i++) {
for (int j = 0; j < a.length-1-i; j++) {
if (a[j+1] < a[j]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}
发现问题：对于冒泡排序我们都知道，即使已经排好顺序，循环还是会继续进行，即使只比较不交换。 优化思路：当判断到数组已经不再发生改变之后就终止循环。
当然，这就是蛮力法的一个应用，通过蛮力的解法来找到优化的思路
二、蛮力法在查找算法中的应用
对于查找算法来说，最简单的一个思路就是逐个匹配，直到找到目标元素
顺序查找：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public class Main {
public static void main(String[] args) {
int[] a = {89, 45, 68, 90, 29, 34, 17, 0};
int k = 45;
int i = 0;
a[a.length-1] = k;
while (a[i] != k) {
i++;
}
if (i < a.length-1) {
System.out.println(i);
} else {
System.out.println("no find");
}
}
}
上面的算法不同于大家常见的算法，这是在顺序查找时常用的一个小技巧：将查找建添加到列表末尾（也称限位器），那么查找必定会成功，这样就不比在每次循环都检查是否达到的末尾，只需再循环外面做一次即可。 发现问题：如果未定的数组是有序的，即使后面的元素都不可能等于查找建，但是算法不会停止
优化思路：当我们当查到一个比查找键还大的元素，仍未找到，那么就可以终止循环了。
三、蛮力法在字符串匹配问题中的应用
字符串匹配问题通常是给定一个n个字符组成的串（称为文本），一个m（m<=n）个字符的串（称为模式），从文本中寻找匹配模式的子串。显然我们需要逐个匹配，这是蛮力算法的典型特点。
**蛮力匹配：**时间复杂度O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public class Main {
public static void main(String[] args) {
String[] a = {"a","b","c","d","e","f","g","h"};
String[] b = {"e","f"};
int flag = 0;
for (int i = 0; i < a.length-b.length; i++) {
int j = 0;
while (j < b.length && b[j] == a[i+j]) {
j = j+1;
if (j == b.length-1) {
flag = 1;
System.out.println(i);
}
}
}
if (flag == 0) {
System.out.println("no find");
}
}
}
发现问题：这样的蛮力方法对于文本中的每个字母都会进行匹配，而这无疑增加了许多冗余的比较 优化思路：KMP算法
四、蛮力法在求解“最近对”问题中的应用
最近对问题是在计算几何问题中最简单的，是指在一个包含n个点的集合中，找到距离最近的两个点，我们这里只研究二维空间中的版本，高维计算基本类似，区别只在于计算两点之间距离的公式略有不同，下面是标准的欧几里得距离公式：
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
26class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
public static void main(String[] args) {
Point[] points = new Point[5];
points[0] = new Point(1,3);
points[1] = new Point(2,1);
points[2] = new Point(3,5);
points[3] = new Point(4,4);
points[4] = new Point(5,2);
double d = 99999999;
for (int i = 0; i < points.length-1; i++) {
for (int j = i+1; j < points.length; j++) {
d = Math.min(d, Math.sqrt(Math.pow(points[i].x-points[j].x, 2)+Math.pow(points[i].y-points[j].y, 2)));
}
}
System.out.println(d);
}
}
由图可知，最近的两个点就是（3，5）和（4，4）
发现问题：开方计算实际上结果大多是无理数，计算机计算整数的平方根并不是一件轻松的事情，所以应该尽量在高效的算法中避免开方计算。
优化思路：全都比较未开方之前的数即可
五、蛮力法在求解凸包问题中的应用
凸包问题向来是计算几何中最重要的问题之一，许多各式各样的应用大多要么本身就是图凸包问题要么其中一部分需要按照凸包问题解决。
凸集合定义：对于平面上一个点集合，如果集合中的任意两点p和q为端点的线段都属于该集合，那么称这个集合为凸集合。
凸包定义：一个点集合S的凸包是包含S的最小凸集合。我们可以假设有一块板子，板子上面有许多钉子，用一根橡皮筋将所有的钉子都围住，凸包就是以橡皮筋圈为边界的区域。
在坐标平面上穿过两个点（x1, x2），（x2, y2）的直线方程为 ax+by = c （其中a = y2- y1, b = x1 - x2, c = x1y2 - y1x2）
上述方程基于两点式直线方程
由两个点连起来的直线会将平面分成两部分，其中半个平面的点都满足ax+by>c ，另一半平面中的点都满足ax+by<c ，对于线上的点来说满足ax+by=c。因此，算法的思路就是对于每个点带入ax+by-c，判断表达式结果的符号是否相同即可。
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81import java.util.*;
class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "Point{" +
"x=" + x +
", y=" + y +
'}';
}
}
public class Main {
public static void main(String[] args) {
Point[] points = new Point[6];
List arr = new ArrayList();
points[0] = new Point(1,3);
points[1] = new Point(2,1);
points[2] = new Point(3,5);
points[3] = new Point(4,4);
points[4] = new Point(5,2);
points[5] = new Point(3,2);
arr = outerTrees(points);
Iterator it = arr.iterator();
while (it.hasNext()) {
System.out.println(it.next().toString() + " ");
}
}
private static List<Point> outerTrees(Point[] points) {
Set<Point> ans = new HashSet<>();
/**
* 只有一个点
* */
if (points.length == 1){
ans.add(points[0]);
return new ArrayList<>(ans);
}
for (int i = 0; i < points.length-1; i++){
for (int j = i + 1; j < points.length; j++){
int oneSide = 0;
for (int k = 0; k < points.length; k++){
if (k == i || k == j) {
continue;
}
if (calcuTriangle(points[i], points[j], points[k]) > 0){
oneSide++;
}
}
if (oneSide == points.length-2 || oneSide == 0){
ans.add(points[i]);
ans.add(points[j]);
}
int otherSide = 0;
for (int k = 0; k < points.length; k++){
if (k == i || k == j) continue;
if (calcuTriangle(points[i], points[j], points[k]) < 0){
otherSide++;
}
}
if (otherSide == points.length-2 || otherSide == 0){
ans.add(points[i]);
ans.add(points[j]);
}
}
}
return new ArrayList<>(ans);
}
private static int calcuTriangle(Point a1, Point a2, Point a3) {
return a1.x * a2.y + a3.x * a1.y + a2.x * a3.y - a3.x * a2.y - a2.x * a1.y - a1.x * a3.y;
}
}
六、蛮力法在求解最优解问题中的应用--TSP，背包问题，配对问题
**1、TSP（旅行商问题）**要求我们找出一条n个给定城市之间的最短路径，使我们再回到出发的城市之前，对欧每个城市都只访问一次。我们可以用赋权图来描述这个问题，那么算法的目的就是求解一个图的最短哈密顿回路问题。
哈密顿回路同样可以定义为
其中第一个顶点和最后一个顶点相同，其他n-1个顶点互不相同。那么我们就可以通过生成n-1个中间城市的组合来的到所哟逇旅行线路，来出最短的线路。
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
51import java.util.Scanner;
public class Main {
static int[][] a = new int[5][5];
static int[] bestWay = new int[6];
static int min = 99999999;
static int sum = 0;
static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
/**
* 假设a为1号点，b为2号点,c为3号点，d为4号点
* 1 2 2
* 1 3 5
* 1 4 7
* 2 3 8
* 2 4 3
* 3 4 1
* */
for (int i = 1; i < 7; i++) {
int x = in.nextInt();
int y = in.nextInt();
int z = in.nextInt();
a[x][y] = z;
a[y][x] = z;
}
for (int i = 2; i < a.length; i++) {
for (int j = 2; j < a.length; j++) {
if (j != i) {
for (int k = 2; k < a.length; k++) {
if (k != i && k != j) {
sum = a[1][i] + a[i][j] + a[j][k] + a[k][1];
if (min > sum) {
min = sum;
bestWay[1] = 1;
bestWay[2] = i;
bestWay[3] = j;
bestWay[4] = k;
bestWay[5] = 1;
}
}
}
}
}
}
for (int i = 1; i < bestWay.length-1; i++) {
System.out.print(bestWay[i] + "-->");
}
System.out.println(bestWay[bestWay.length-1]);
System.out.println(min);
}
}
发现问题：我们可以发现这有3对不同的线路，而对于每队线路中，不同的只是线路的方向。 优化思路：固定住每条线路的方向，将顶点排列数目减半。
实际上用蛮力方法来解决这种问题是极为不明智的，这里只是给出一个思路，当顶点数目过多时还是要采用诸如动态规划，贪心等方法来优化的。
2、背包问题给定n个重量为w1，w2，w3...wn, 价值为v1，v2，v3...vn的物品和一个称重为C的背包，求这些物品中一个最有价值的子集。
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
import java.util.Scanner;
public class Main {
static int n, c;
static int max = 0;
static int[] w, v;
static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
n = in.nextInt();
c = in.nextInt();
w = new int[n+1];
v = new int[n+1];
for (int i = 1; i <= n; i++) {
w[i] = in.nextInt();
v[i] = in.nextInt();
}
/**
* 对于n个物品，会存在2^n个中组合方式
* 采用二进制的1,0来表示物品是否被选择，比采用数组要方便，数组每次都要遍历一遍
* */
for (int i = 0; i <= Math.pow(2, n); i++) {
int k = i;
int tempw = 0;
int tempv = 0;
for (int j = 1; j <= n; j++) {
/**
* 二进制位对应w[],v[]
* 每次检查末位数字是否为1，之后数去除末位数字
* */
if (k % 2 == 1) {
tempw += w[j];
tempv += v[j];
}
k /= 2;
}
if (tempw <= c) {
if (tempv > max) {
max = tempv;
}
}
}
System.out.println(max);
}
}
发现问题：显然2^n次的迭代始终效率都是低下的 优化思路：背包问题最好的解决方法自然是用动态规划来解决，当然也可以用回溯或者分支界限法。
3、分配问题可以理解为有n个任务需要分配给n个人执行，一个任务对应一个人。对于每一对i,j=1,2,3,...,n来说，将第j个任务分配给第i个人的成本是c[i,j]，求出总成本最小的方案。我们当然不能从每一行中选出最小的元素，因为这写最小的元素可能在同一列。这个问题和旅行商问题有相似之处，基本思路也是将数据放到一个成本矩阵C中，枚举出每种情况，找出成本最小值
代码基本和TSP一样，略。
发现问题：同样是大数据量处理起来的效率问题
优化思路：匈牙利算法