算法》Chapter 5 回溯法"/>
《趣学算法》Chapter 5 回溯法
Chapter 5 回溯法
5.1 回溯法基础
5.2 大卖场购物车2——0-1背包问题
5.3 部落护卫队——最大团
5.4 地图调色板——地图着色
5.5 一山不容二虎——n皇后问题
5.6 机器零件加工——最优加工顺序
5.7 奇妙之旅——旅行商问题
5.8 回溯法算法秘籍
“不进则退,不喜则忧,不得则亡,此世人之常。”
——《邓析子•无后篇》
从小到大,我们听了很多“不进则退”的故事,这些故事告诫人们如果不进步,就会倒退。但在这里,我们却采用了“不进则退”的另一层积极含义——“退一步海阔天空”“不必在一棵树上吊死”。如果一条路无法走下去,退回去,换条路走也不失一个很好的办法,这正是回溯法的初衷。
5.1 回溯法基础
回溯法是一种选优搜索法,按照选优条件深度优先搜索,以达到目标。当搜索到某一步时,发现原先选择并不是最优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术称为回溯法,而满足回溯条件的某个状态称为“回溯点”。
5.1.1 算法思想
回溯法是从初始状态出发,按照深度优先搜索的方式,根据产生子结点的条件约束,搜索问题的解。当发现当前结点不满足求解条件时,就回溯ÿ
更多推荐
《趣学算法》Chapter 5 回溯法
发布评论