概述

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

eg. 冒泡排序

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}$

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

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 为端点的线段都属于这个集合

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

思路：任意选择点集合中的两个点 $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. 旅行商问题

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

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

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

eg. 背包问题

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

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

结

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

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

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

TUFZ's Blog

算法分析——蛮力法

概述

最近对和凸包问题

穷举问题

结