文章目录
  1. 1. 暴力求解(brute force)
    1. 1.1. 排序问题的应用
    2. 1.2. 搜索问题的应用
    3. 1.3. 几何问题
    4. 1.4. 穷举搜索
    5. 1.5. 总结

暴力求解(brute force)

Brute force is a straightforward approach to solving a problem, usually directly based on the problem statement and definitions of the concepts involved.

暴力求解即根据问题的描述和定义直接求解,不使用一些特殊的算法.

排序问题的应用

  • 选择排序
    选择排序将数组分为排序与未排序两个部分,每次将从未排序部分取出最小的值,插入排序部分的最后,最终未排序部分消失,排序完成.

  • 冒泡排序
    冒泡排序也是将数组分为排序与未排序两个部分,每次从未排序部分的第一个数开始,与后一个比较,如果大于它两两交换,否则从第二个开始继续与后一个比较.最终未排序部分的最后一个数即最大的数.循环n次即完成排序.

搜索问题的应用

  • 线性搜索
    简单粗暴,一个个比较.

  • 字符串匹配
    同样道理,逐个比较.

几何问题

  • 最近点问题
    把所有两点距离求出来,然后选择最小值.

  • 凸包问题
    用循序渐进的方式求取给定点集的凸包,首先把最初输入的3个不共线(Non-collinear)的点按 逆时针方向构成一个三角形,这就是这3点的凸包。接着便会考察第4点,看看这个点是否位于前述三 角形之内或三角形的边上。若是,则这第4点并非凸包上的点,前述三角形保持不变。若否,则把这前述的三角 形扩大为一个四边形,并把不适用的边擦去。这个四边形便是这首4点的凸包。接着程序又会考察第5点,如此 类推,直至所有点均已被考察为止.由于每次都要检查所有之前的点,时间复杂度为O(n^2).

穷举搜索

以下3个问题都可以用穷举的方法暴力求解,把所有可能都试一遍.然而实际上由于可能情况太多,一般不会使用穷举的方法.数据量小的情况可以考虑使用.每个问题都有不少更优的算法.

  • 旅行推销员问题(Travelling Salesman Problem) 有n个城市,一个推销员要从其中某一个城市出发,唯一走遍所有的城市,再回到他出发的城市,求最短的路线。也即求一个最短的哈密顿回路。

  • 背包问题(knapsack problem)
    给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。

  • 任务分配问题(assignment problem)
    线性任务分配问题:P是二元组(a, b)的集合,其中a和b分别是集合A和B中的元素。C是某一函数,并满足特定约束条件,例如:A的每一个元素必须在P中出现一次,或者B的每一个元素必须在P中出现一次,或者以上二者都必须满足。线性任务分配问题的目标就是最大化或者最小化C(a, b)之和。

总结

暴力求解法可以说毫无技巧,但是简单容易实现.一般情况是不会用到的,但是在特定情况下有奇效.可以说当人们解决某个问题的时候用暴力求解应该是第一直觉,然而这太简单并不能体现自己的能力,就会开始寻找更快的方法.我的理解是更优的算法应该是基于暴力求解法之上的.例如说背包问题,同样样遍历所有情况,动态规划巧妙的利用前面的尝试过的数据,减少了工作量.但本质上还是要试遍所有可能,只是试的少了.
文章目录
  1. 1. 暴力求解(brute force)
    1. 1.1. 排序问题的应用
    2. 1.2. 搜索问题的应用
    3. 1.3. 几何问题
    4. 1.4. 穷举搜索
    5. 1.5. 总结