算法：常用设计思想

Posted on 2018-04-29 In 数据结构与算法

前面几篇文章大概介绍了几个常用的数据结构。

根据我的理解，数据结构帮助我们对需要解决的问题进行描述，而算法就是我们解决问题方案的具体描述。它包括对问题的分析及研究（建立描述问题的数学模型），然后根据一些策略和思想制定出解决问题的方案。

这篇文章讲述了四个算法设计时的常用思想并给出了相应的例子：

解空间内的穷举
贪婪法
分治法
动态规划

解空间内的穷举

这个名字是来自于《算法的乐趣》，其实就是穷举法。这里的解空间是所有可能的解的集合。加上解空间就是为了说明：穷举是在可能的解的集合中查找的，并不是漫步目的的乱找。

步骤：

确定问题的解空间的范围以及正确解的判定条件
根据解空间的特点选取搜索策略。一一检验解空间中的候选解是否正确，必要时可辅助一些剪枝算法。

穷举法可以说是解决很多问题的 “通用算法” 了，但是穷举法最大的问题就是问题的规模。所以，我们需要一些策略来进行我们的穷举。

策略：

盲目搜索：在给定的解空间，按顺序依次搜索所有的候选解。
启发式搜索：在搜索过程中，依据一些状态评估的函数，优先对有可能演化出解的节点进行搜索。
剪枝策略：如果一些节点可以根据提供的信息明确地被判定为不可能演化出解，那么就可以跳过此状态节点。

举例：
在一个笼子里关着若干只鸡和若干只兔，从上面数共有35个头；从下面数共有94只脚。问笼中鸡和兔的数量各是多少？

// head = 35,  foot = 94
func getNumberBy(head: Int, foot: Int) -> (Int, Int)? {
    var numOfRabbit: Int = 1
    var numOfChicken: Int = head - numOfRabbit
    
    while (numOfRabbit*4 + numOfChicken*2) != foot {
        numOfRabbit += 1
        numOfChicken = head - numOfRabbit
        
        if numOfRabbit > head {
            return nil
        }
    }
    
    return (numOfRabbit, numOfChicken)
}

贪婪法

又称贪心算法（greedy algorithm），是寻找最优解问题的常用方法。这种方法模式一般将求解过程分为若干个步骤，在每个步骤都应用贪心原则，选取当前状态下最好的或最优的选择（局部最有利的选择），并以此希望最后堆叠的结果也是最好或最优的解。

大多数情况下，由于贪婪法在选择策略上的“短视”，会错过真正的最优解，但是贪婪法简单高效，省去了为了寻找最优解可能需要的穷举操作，可以得到与最优解比较接近的近似最优解。

基本思想：

建立对问题精确描述的数学模型，包括定义最优解的模型。
将问题分解为一系列子问题，同时定义子问题的最优解结构。
应用贪心原则确定每个子问题的局部最优解，并根据最优解的模型，用子问题的局部最优解堆叠出全局最优解。

举例：
现在我们有一个背包，里面可以装下 150 单位重量的物体，现在我们有一系列重量的东西，怎么样的组合让背包装下最多的东西？

let weight = [35, 30, 60, 50, 40, 10, 25] // 重量

// total = 150
func greedy(total: Int) -> [Int] {
    var result: [Int] = []
    
    let tempArr = weight.sorted()
    
    var temp = 0
    for index in 0..<weight.count {
        temp = temp + tempArr[index]
        if temp < total {
            result.append(tempArr[index])
        }
    }
    
    return result
}

分治法

分治法的设计思想是将无法着手解决的大问题分解成一系列规模较小的相同问题。然后逐个解决小问题，即分而治之。分治法产生的子问题与原始问题相同，只是规模减小，反复使用分治方法，可以使得子问题的规模不断减小，直到能够被直接求解为止。

基本思想：

分解：将问题分解为若干个规模较小，相互独立且与原问题形式相同的子问题，确保各个子问题的解具有相同的结构。
解决：如果上一步分解得到的子问题可以解决，则直接解决，否则，对每个子问题使用和上一步相同的方法再次分解，然后求解分解后的子问题，这个过程可能是个递归的过程。
合并：将上一步解决的各个子问题的解通过某种规则合并起来，得到原问题的解。

举例：
一个人在 1~100 中随机选取一个数，如何才能以最少的次数猜到这个数字？每次猜测后，都会得知猜测结果小了、大了或正确。

// 一个典型的二分搜索
// source = [1, 2, 3, ... 100], target 为需要猜测的数字
func binarySearch(source: [Int], target: Int) -> Int? {
    guard source.count != 0 else {
        return nil
    }
    
    var low: Int = 0
    var high: Int = source.count - 1
    var mid: Int = 0
    
    var count = 0
    
    while low <= high {
        count += 1;
        
        mid = low + (high - low) / 2 
        
        if target < source[mid] {
            high = mid - 1
        } else if target > source[mid] {
            low = mid + 1
        } else {
            return mid
        }
    }
    return nil
}

动态规划

解决多阶段决策问题常用的最优化理论。原理是把多阶段决策过程转化为一系列的单阶段决策问题，利用各个阶段之间的递推关系，逐个确定每个阶段的最优化决策，最终堆叠出多阶段决策的最优化决策结果。

需要满足的条件：

最优化原理：

不管之前决策是否是最优决策，都必须保证从现在开始决策是在之前决策基础上的最优决策。
无后向性：

当各个阶段的子问题确定以后，对于某个特定阶段的子问题来说，它之前的各个阶段的子问题的决策只影响该阶段的决策，对该阶段之后的决策不产生影响。也就是说，每个阶段的决策仅受之前决策的影响，但是不影响之后各阶段的决策。
有重叠子问题：

即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

动态规划算法与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。

基本思想：

定义最优子问题：

确定问题的优化目标以及决策最优解，并对决策过程划分阶段。
定义状态：

对起始状态施加决策，使得状态发生改变，得到决策的结果状态。状态的定义是建立在子问题定义的基础上的，因此状态必须满足 “无后效性”。
定义决策和状态转换方程：

决策就是能使状态发生转变的选择动作。状态转换方程是根据上一阶段的状态和决策来导出本阶段的状态的方程。
确定边界条件：

边界条件其实就是状态转移方程的终止条件。

举例：

有n级台阶，一个人每次上一级或者两级，问有多少种走完n级台阶的方法？

分析：

动态规划的实现的关键在于能不能准确合理的用动态规划表来抽象出实际问题。在这个问题上，我们让f(n)表示走上n级台阶的方法数。

那么当 n 为 1 时，f(n) = 1,n 为 2 时，f(n) = 2,就是说当台阶只有一级的时候，方法数是一种，台阶有两级的时候，方法数为 2。那么当我们要走上 n 级台阶，必然是从 n-1 级台阶迈一步或者是从 n-2 级台阶迈两步，所以到达 n 级台阶的方法数必然是到达 n-1 级台阶的方法数加上到达 n-2 级台阶的方法数之和。即 f(n) = f(n-1) + f(n-2)。

// n 为需要走的台阶总数
func calculateStep(n: Int) -> Int {
    //如果为第一级台阶或者第二级台阶 则直接返回n
    if n < 1 {
        return 0
    }
    
    if n == 1 || n ==  2 {
        return n
    }
    
    var a = 1
    var b = 2
    var temp = 0
    
    for _ in 3..<n+1 {
        temp = a + b
        a = b
        b = temp
    }
    return temp
}