最新公告
  • 欢迎您光临起源地模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • 《算法图解》读书笔记三

    正文概述 掘金(程序媛练习生)   2021-05-13   47

    第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])
        }
    

    三、小结

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

    起源地 » 《算法图解》读书笔记三

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元