算法设计与分析基础 chap3 蛮力法

蛮力法（也叫穷举法），是一种直接解决问题的方法，常常直接基于问题的描述和所涉及的概念及定义。
显然蛮力法经常不是一个最好的算法选择，但当我们想不出别的更好的办法时，它也是一种有效的解决问题的方法。

优点：

逻辑清晰，相对于高效的、巧妙的算法，实现和构思简单。
同时蛮力法也是很多高效算法的基础。可以作为其他高效算法的衡量标准。
可以用来解决广阔领域的多种问题。
对于一些重要的问题，它可以产生一些合理的算法。
可以解决一些小规模的问题。它让你花费较少的代价。

算法介绍：

选择排序

基本思想：从初始位置开始，依次给每个位置选择当前最小的元素

特点： 已经排好序的元素位于数组开头

算法：

Algorithm SelectionSort(A[0..n-1])
for i<-0 to n-2 do
    min<-i
for j<-(i+1） to n-1 do
    if A[j]<A[min]
        min<-j
    swap A[i] and A[min]

复杂度分析：

冒泡排序

基本思想：依次比较相邻元素，利用相邻元素的交换，使得小的元素
不断往前换，并且大的元素不断往后换（冒泡）。

特点： 已经排好序的元素位于数组末尾

算法：

Algorithm BubbleSort (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]

复杂度分析：

该表达式与选择排序的表达式几乎相同。冒泡排序的键交换次数取决于特定的输入。最坏的情况下就是遇到降序的数组，这时的键交换次数和键比较次数是相同的。
$S_{worst}(n)=C(n)=\frac{(n-1)n}{2}\in\Theta(n^2)$

顺序查找(Sequential Search)

基本思想：
从第一个元素开始顺序扫描列表，逐个比较关键字与列表中元素的键值。若找到一个键值相等的元素，则查找成功；若扫描结束后，仍未找到，则查找失败。
算法：

顺序查找算法1：

Algorithm SequentialSearch1(A[0..n], K)
for i<-0 to n-1 do
    if A[i]==K
        return i
return -1

顺序查找算法2：

Algorithm SequentialSearch2 (A[0..n], K)
A[n]<-K
i<-0
while A[i] ≠ K do
    i <-i+1
if i<n return i
else return -1

复杂度分析：
最好情况:K排在A的第一位，复杂度:$\Theta(1)$
最坏情况：K不在A中，复杂度:$\Theta(n)$
平均情况：复杂度$\Theta(n)$

蛮力字符串匹配

字符串匹配问题：

给定一个n个字符组成的串，称为文本（text）。一个m个字符的串，称为模式（pattern ）。字符串匹配就是从文本中寻找匹配模式的
更精确地说，我们找的是文本中的第一个匹配子串的开始位置 i：使得

算法：

Algorithm BruteForceStringMatch (T[0..n-1], P[0..m-1])
for i<-0 to n-m do
    j<-0
    while j<m and P[j]=T[i+j] do
        j<-j+1
        if j=m return i
return -1

复杂度分析：
基本操作为j< m and P[j]=T[i+j],最坏情况下，比较次数为:

由于n>m，最差复杂度为：$\Theta(nm)$

凸包问题

凸集合： 对于平面上的一个点集合（有限或无限），如果以集合中任意两点P和Q为端点的线段都属于这个集合，则这个集合是凸集合（凸点集合）
凸包： 一个点集合S的凸包是包含S的最小凸集合。『最小』：S的凸包一定是所有包含S的凸集合的子集
凸包问题就是为一个n个点的集合构造凸包的问题
定理：任意包含n>2个点（不共线）的集合S的凸包是以S中的某些点为顶点的凸多边形。
极点：凸包（凸多边形）的顶点
极点的性质：对于任何以集合中的点为端点的线段来说，它们不是这种线段的中点。
算法思想：对于一个n个点集合中的两个点$p_i$和$p_j$，当且仅当该集合中的其他点都位于穿过这两点的直线的同一侧时，它们的连线是该集合凸包边界的一部分。
判断同一侧：$ax+by-c=0,a=y_2-y_1,b=x_1-x_2,c=x_1y_2-y_1x_2$,在同一侧时 ax+by-c的符号相同

Algorithm   BruteForceConvexHull(P)
PointPairs <- ∅
for i←1 to n-1 do
    for j<-i+1 to n do
        currSign <- 0; sameSide <- True
        a <- y j -y i ; b <- x i -x j ; c <- x i y j -y i x j
        for k<-1 to n do
            if k=i OR k=j continue
            sign k <-sign (ax k +by k -c)
            if currSign=0 currSign <- sign k ;
            else if currSign*sign k < 0
                sameSide <- False; break
        if sameSide =True Add <i, j> to PointPairs
return PointPairs

当k和i,j在同一直线时，$sign_k=0$,选取了多余的点对。
修正：

效率分析：i,j的组合有$n(n-1)/2个$，每个组合，最差需要再对n-2个k作判断，所以该算法的复杂度为$O(n^3)$

穷举查找

旅行商问题：一个售货员希望从一个城市出发访问 n 个城市,每个城市只访问一次，开始和结束于同一城市。问题：设计一个算法,找出售货员能采取的最短路径。问题模型：求一个赋权图中最短的哈密尔顿回路。
0-1背包问题
分配问题：
有 n 个任务需要分配给 n 个人执行，一个任务一个人。（每个任务只分配给一个人，每个人只分配一个任务）对于每一对i,j=1,…,n来说，将第j个任务分配给i个人的成本是C[i,j]。该问题要找出总成本最小的分配方案。

旅行商问题和背包问题是典型的NP难问题，目前还没有发现有效的多项式时间复杂度的算法

对于分配问题，有一个匈牙利算法（Hungarian Algorithm or Kuhn–Munkres Algorithm）。二部图（bipartitegraph），其时间复杂度为$O(n^4)$。经过改进后，该算法复杂度可提升为$O(n^3)$。

优点：