算法分析——蛮力法

没简介多简洁😴

概述

定义:从问题的描述和定义中直接得出解的方法

eg. 冒泡排序

1
2
3
4
5
6
7
8
9
10
BubbleSort(A[0, ..., n-1])

// 该算法用冒泡排序对给定数组排序
// 输入:一个可排序的数组 A[0, ..., n-1]
// 输出:非降序排列的数组 A[0, ..., n-1]

for i⬅0 to n-2 do
for j⬅0 to n-2-i do
if A[j+1] < A[j]
swap A[j] and A[j+1]

一般用来解决一些比较广阔的领域问题,并不是针对某一特定领域的问题,也能够用于产生问题的一些合理方法

通常当问题的实例规模比较小,或者说问题的数据量比较小的时候,蛮力法的代价比较小,可以选择它来解决问题

蛮力法的结果可以被用作其他高效算法的衡量标准,来比较这些高效算法的效率和正确性

最近对和凸包问题

最近对问题:在包含 N 个点的集合中找出距离最近的两个点

蛮力法:

$$d(P_{i}, P_{j}) = \sqrt{(x_{i} - x_{j})^2 + (y_{i} - y_{j})^2}$$

分别计算每两个点之间的距离,找出其中距离最小的两个点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
BruteForceClosestPoints(P)

// 输入:一个包好 n(n >= 2) 个点坐标的列表 P
// 输出:两个距离最近的点的坐标

dmin ⬅ ∞
for i⬅1 to n-1 do
for j⬅i+1 to n do
d ⬅ sqrt((xi - xj)^2 + (yi -yj)^2)
if d < dmin
dmin ⬅ d;
index1 ⬅ i;
index2 ⬅ j
return index1, index2

时间复杂度:$n^2$

凸包:给定点集中的一个近似

一个点集合 S 的凸包是包含点集合 S 的最小的凸集合,我们说一个点集合是凸起的,就是说以集合中任意两点 P 和 Q 为端点的线段都属于这个集合

00.png

如图,凸包就是边界点连接围成的区域,也就是以点集合中某些点为顶点的一个凸多边形,这些顶点被称为极点

思路:任意选择点集合中的两个点 $P_{i}$ 和 $P_{j}$,如果发现点集合中其他的点都位于穿过连接这两个点的直线的同侧,那么这两个点的连线 $P_{i}P_{j}$ 就是凸包边界的一部分,找出所有满足条件的点

$P_{i}$ 和 $P_{j}$ 的直线方程:$ax + by = c$

如果把点集合中的其他点的坐标代入式子:$ax + by - c$,如果结果符号相同,就表示其他点都位于 $P_{i}$ 和 $P_{j}$ 的同侧,那么这两个点 $P_{i}$ 和 P_{j} 就是凸包的一部分

由于对于 N 个点的集合来说,不同点的选择有 $\frac{n(n-1)}{2}$ 个,每次选择需要对其他 $n-2$ 个点做测试,因此这种算法的时间复杂度为:$n^3$

穷举问题

eg. 旅行商问题

一个旅行商,从一个城市出发,经过城市与城市之间的道路,将所有的城市访问一次来推销自己的商品,然后回到最初出发的城市,问:如何制定一个距离最短的访问顺序来节约旅行成本?

思路(穷举查找):把所有访问城市可能的顺序列举出来,计算每一个顺序的距离,最后选择距离最短的一条

01.png

对于要经过 n 个城市的旅行商问题,路径的可能性是 $(n-1)!$

eg. 背包问题

有 N 个物品,每个物品都有重量和价值,重量:$w_{1}, w_{2}, …, w_{n}$,价值:$v_{1}, v_{2}, …, v_{n}$,有一个容量为 W 的背包,这个背包的承重不能超过 W,求:如何装入物品才能使背包不超重且价值最大?

02.png

如果物品的数量是 n 个,穷举的数量是 $2^n-1$

通过问题的描述或者问题的概念,制定出一种简单而直接的解决问题的方案

但是:这只能针对规模很小的问题才具有适用性和简单性

通常来说蛮力法的效率都不够高