第3章 蛮力法

第三章 蛮力法

蛮力算法是一种简单直接地解决问题的方法

• 优点：
  1.应用范围广；
  2.不受实例规模的限制；
  3.当要解决的问题低频率出现，并且高效算法很难设计时可选蛮力法；
  4.对解决一些小规模问题实例仍然有效；
  5.可作为衡量其他算法的参照物。

• 主要内容：
  1.选择排序和冒泡排序
  2.顺序查找和蛮力字符串匹配
  3.最近对和凸包问题的蛮力算法
  4.穷举查找

选择排序和冒泡排序

• 选择排序原理：扫描整个列表，找出最小元素，然后将最小元素与第一个元素交换位置。从第二个元素开始扫描列表，找出n-1个元素中的最小元素，将最小元素与第二个元素交换位置，如此类推，做n-1遍后排序结束。

• 冒泡排序原理：比较相邻的元素，将大的元素交换到右边的位置，重复多次后，最大元素就“沉淀”到列表的最后一个位置。第二遍将第二大元素沉下去，n-1遍后结束。

• 时间效率函数均属于 Θ(n²) 。

顺序查找和蛮力字符串匹配

• 顺序查找：已知有n个元素的数组A[0...n]. 给定元素K,要求找出一个下标i,使得A[i]=K.输出第一个值等于K的元素的位置，找不到返回-1.
  算法改进：在表尾n添加K元素查找键（就不用每次循环都检查是否到达或超过了表尾），如果查到的元素位置小于n就返回i，否则返回-1；而对于有序数组而言，只要遇到了一个大于或等于查找键的元素，查找就可以停止了。
  线性算法

• 蛮力法字符串比较问题：从文本中寻找匹配模式的子串，即求出第一个匹配模式的子串在文本中的开始位置（子串最左元素的下标），将模式对准文本的前m个字符从左往右进行比对，如果其中有一个字符不匹配，模式往右移动一位继续下一个m个字符的比对。
  文本：给定的由n个字符组成的串
  模式：指定的由m个字符组成的串
  最坏情形：模式须移动n-m+1次，每次移动模式之前，做足m次比对才发现不匹配(即第i+m位不匹配)，因此在最坏情况下算法属于Θ(nm)，平均效率可达到 Θ(n+m) = Θ(n)

最近对和凸包问题的蛮力算法

• 最近对问题：
  给定平面S上n个点，找其中的一对点，使得在n(n-1)/2个点对中，该点对的距离最小。
  对于给定的n个点，找出其中两个距离最小的点的问题直观的想法很简单，只要把所有的点两两组合，比较它们之间的距离即可以得到距离最小的一对。
  基本操作：平方运算
  执行次数：n(n-1)
  效率：Θ(n²)

• 凸包问题：
  凸集：对于平面上的一个点集合（有限的或者无限的），如果以集合中任意两点p和q为端点的线段都属于该集合，则这个集合是凸的。
  凸包：一个点集合S的凸包是包含S的最小凸集。显然，如果S是凸的，则S的凸包就是S本身。
  定理：任意包含n>2个点的集合S的凸包，是以S中的某些点位顶点的凸多边形。特别，如果所有点共线，则多边形退化为一条直线，它的两个端点仍在S中。
  极点：凸集的极点是指不会出现在集合中任何线段的中间的点。凸多边形的顶点是极点。
  凸包问题的解法：设点集大小为n，首先将其中的点两两配对，得到直线段条；然后对每一条直线段检查其余的n-2个点的相对于该直线段的正负性，如果它们都有相同的正负性，那么这条直线段属于凸多边形的边，其顶点是极点。
  ax+by=c这样一根直线把平面分成两个半平面，一个半平面中的点都满足ax+by>c，另一个半平面中的点都满足ax+by<c，对于不同点的每一个n(n-1)/2来说，都需要其他n-2个点求出ax+by-c的符号。
  效率：O(n³)

穷举法

生成所有可能的可行解，再从中选择最优解。

• 旅行商问题：
  TSP问题：给定n个城市相互之间的距离，求一条能走遍n个城市的最短路径，使我们能从任一城市开始，访问每个城市只一次后回到起点。
  等价于 “Hamilton回路问题” -- (无权图)。
• 背包问题：
  给定n 个重量为w1、w2、…、wn，价值为v1、v2、…、vn的物品和一个承重为W的背包，要求将物品装入背包使背包的价值最大。
  因为n个元素集合的子集数量是2ⁿ，穷举法是Ω(2ⁿ)。

上面两个问题是NP困难问题（目前没有已知的效率可以用多项式来表示的算法）的著名例子。

• 分配问题：
  有n个任务需要分配给n个人执行，一人一个任务。将第j个任务分配给第i个人的成本是C[i,j],求总成本最小的分配方案。
• 深度优先查找 广度优先查找
  两种查找 对邻接矩阵表示的图，效率为：Θ（|V|²）；对邻接链表表示的图，效率为：Θ（|V|+|E|）。
  DFS和BFS比较.PNG
  总结.PNG