《算法图解》读书笔记三

第8章 贪婪算法

一、贪婪算法（近似算法）

贪婪算法（近似算法）：每步都选择局部最优解，最终得到的就是全局最优解。

贪婪算法并非在任何情况下都行之有效，但它易于实现，得到最优解可能要花费很长的时间！贪婪策略不能获得最优解，但得到的结果又与正确结果相当接近。

近似算法优劣的标准如下：

1. 速度有多快；
2. 得到的近似解与最优解的接近程度。

第一个例子：

问题：

假设你办了个广播节目，要让全部州的的听众都收听得到。为此，你需要决定在哪些广播台播出并力图在尽可能少的广播台播出。

算法思路：

1. 选出这样一个广播台，即它覆盖了最多的未覆盖州。即便这个广播台覆盖了一些已覆盖的州，也没有关系。

2. 重复第一步，直到覆盖了所有的州。

代码：

states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"]) #states_needed为需要覆盖的州——集合
stations = {}  #可供选择的广播台清单——散列表
stations["kone"] = set(["id", "nv", "ut"]) 
stations["ktwo"] = set(["wa", "id", "mt"]) 
stations["kthree"] = set(["or", "nv", "ca"]) 
stations["kfour"] = set(["nv", "ut"]) 
stations["kfive"] = set(["ca", "az"])

while states_needed: #不断地循环，直到states_needed为空
    best_station = None #当前最佳的广播台
    states_covered = set() #当前最佳的广播台覆盖的州
    for station, states in stations.items(): 
        covered = states_needed & states #当前广播台覆盖到的未覆盖的州
        if len(covered) > len(states_covered): #当找到更优选择时，替换
            best_station = station 
            states_covered = covered 

    states_needed -= states_covered #需要覆盖的州减少
    final_stations.add(best_station) #添加最终选择的广播台

运行时间：

第二个例子：

问题：

旅行商问题：需要获得前往N个城市的最短距离，找出最佳路线。此问题为阶乘函数，可能的路线数增加得非常快！因此，如果涉及的城市很多，根本就无法找出旅行商问题的正确解。

算法思路：

采用近似算法：随便选择出发城市，然后每次选择要去的下一个城市时，都选择还没去的最近的城市。

总结：

旅行商问题和集合覆盖问题有一些共同之处：你需要计算所有的解，并从中选出最小/最短的那个。这两个问题都属于NP完全问题。

NP完全问题的简单定义是，以难解著称的问题，根本不可能编写出可快速解决这些问题的算法。

二、如何识别 NP 完全问题

• 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
• 涉及“所有组合”的问题通常是NP完全问题。
• 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。
• 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。
• 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。
• 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。

三、小结

• 贪婪算法寻找局部最优解，企图以这种方式获得全局最优解。
• 对于NP完全问题，还没有找到快速解决方案。
• 面临NP完全问题时，最佳的做法是使用近似算法。
• 贪婪算法易于实现、运行速度快，是不错的近似算法。

第9章 动态规划

一、动态规划

一种解决棘手问题的方法，它将问题分成小问题，并先着手解决这些小问题，再逐步解决大问题。

第一个例子：

问题：

背包问题：假设你是个小偷，背着一个可装4磅东西的背包，当前不同商品具有不同价值，为了让盗窃的商品价值最高，你该选择哪些商品？

算法思路：

先解决小背包（子背包）问题，再逐步解决大背包问题。

第二个例子：

问题：

最长公共子串：用户输入单词时，你需要给出其定义。但如果用户拼错了，你必须猜测他原本要输入的是什么单词。例如，Alex想查单词fish，但不小心输入了hish。在你的字典中，根本就没有这样的单词，但有几个类似的单词。

算法思路：

找出类似单词的最长公共子串。

代码：

    if(word_a[i] == word_b[j]){ // 两个字母相同
        cell[i][j] = cell[i-1][j-1] + 1
    }else{// 两个字母不同
        cell[i][j] = 0
    }

第二个例子延展思考：

例如Alex不小心输入了fosh，他原本想输入的是fish还是fort呢？最长公共子串的长度相同，都包含两个字母！但fosh与fish更像。

实际上，这里比较的是最长公共子串，但其实应比较最长公共子序列：两个单词中都有的序列包含的字母数。

最长公共子序列计算方法：

    if(word_a[i] == word_b[j]){ // 两个字母相同
        cell[i][j] = cell[i-1][j-1] + 1
    }else{// 两个字母不同
        cell[i][j] = max(cell[i-1][j], cell[i][j-1])
    }

三、小结

• 动态规划可帮助你在给定约束条件下找到最优解。
• 在问题可分解为彼此独立且离散的子问题时，就可使用动态规划来解决。
• 每种动态规划解决方案都涉及网格，单元格中的值通常就是你要优化的值。每个单元格都是一个子问题，因此应考虑如何将问题分成子问题。