大道至简,知行合一。

动态规划面试宝典

最近面试发现八股文和刷题怪才是跳槽的法宝,作为一线工程师,每天忙着项目开发,平时不注重这些内容的训练,就被‘歧视’,知耻而后勇吧,以后不仅要做好系统和架构,还要练好基本功!

温故而知新。

动态规划题集:https://shimo.im/sheets/hrHvGxvRD3xxvvGD/SZhqW

常说人工智能是人工智障,其实并不过分,计算机唯一能解决的问题就是穷举。

常见面试题目中最难的一般就是动态规划问题,学好动态规划不仅是面试,也是平常编程中优化代码的基础。动态规划的思想也是从一系列算法中演化而来,其思路的真正源头来自贪心算法,所有最优化问题的基础都是贪心算法,考虑穷举的问题,最终通过优化形成一个完美的总结,即动态规划。

解决“动态规划”问题必须找到一些规律:寻找子问题、递归求解、重叠子问题与无后效性、状态存储。

动态规划问题一定具备以下三个特征:

  • 重叠子问题:在穷举的过程中(比如通过递归),存在重复计算的现象;
  • 无后效性:子问题之间的依赖是单向性的,某阶段状态一旦确定,就不受后续决策的影响;
  • 最优子结构:子问题之间必须相互独立,或者说后续的计算可以通过前面的状态推导出来。

每种算法都有局限性,要分清楚其能够解决哪些问题,不适用哪些问题。

面试中,一般来说穷举从来都不是一个好办法,除非问题是不同的组合,而不是最值,即使是求所有不同的组合,计算过程中也会出现重复计算的问题,这种现象就是“重叠子问题”。

贪心算法:每一步计算都是当前看起来最优的选择,即某种意义上的局部最优解,而非从整体最优考虑。这两种思路分别为局部最优解整体最优解。其基本思路:

  • 根据问题来建立数学模型,一般面试题会定义一个简单模型;
  • 把待求解问题划分成若干个子问题,对每个子问题进行求解,得到子问题的局部最优解;
  • 把子问题的局部最优解进行合并,得到最后基于局部最优解的一个解,即原问题的答案。

贪心算法的局限性:只考虑局部最优解,因此绝大多数情况下,不能得到整体最优解,一般会采用回溯进行优化。

如何从整体最优解层面解决,首先最优化问题的本质是指在某些约束条件下,决定可选择的变量应该取何值,使所选定的目标函数达到最优的问题。从数学意义上说,最优化方法是一种求极值的方法,即在一组约束为等式或不等式的条件下,使系统的目标函数达到极值,即最大值或最小值。

如果想得到最优组合,最简单直接的方法是枚举,枚举本身很简单,即把所有组合都遍历一遍,但如何通过一些策略生成所有满足条件的组合呢,这就需要递归。递归是搜索组合的一种非常直观的思路。

但递归问题一般会随着求解值的增加呈现指数形式的增长,因此,递归只是让问题可以求解,但是如果数据规模过大的时候暴力递归会引发极大的性能问题。解决的办法就是优化暴力递归:剪枝和优化,思路就是减少搜索的分支数量。

  • 思路一:参考贪心算法,从整个搜索策略上调整,在遍历时尽量考虑局部最优解,减少递归组合;
  • 思路二:从解空间的树图中,可以发现会出现大量相同的子树,其后面的搜索路径是完全一致的,即重叠子问题,应该避免重叠子问题的计算,可以使用“备忘录”,(空间换时间,弊端就是需要使用内存空间),一般考虑使用以下两种数据结构:
    • 数组(Array):简单的问题通常使用一维数组即可,更为复杂的状态存储过程可以使用更高维度(二维甚至三维)的数组来存储;
    • 哈希表(Hash Table):如果存储的状态不能直接通过索引找到需要的值,(如斐波那契数列问题,可以直接通过数组的索引确定其对应子问题的解是否存在,如果存在就取出直接使用),比如使用了更高级的数据结构而非简单的数字索引,则可以考虑使用哈希表,即字典来存储中间状态,避免重复计算问题;

重叠子问题的处理模式:定义求解最优解的F(x),根据当前问题拆分一系列子问题,假定当前子问题的参数为c,后续子问题的函数为S(x,c),接着继续求解F(S(x,c)),然后需要再定义函数V(x)聚合当前参数c和当前子问题的结果,最后还要定义每一步如何和子问题进行叠加,定义叠加函数H(x),最终得到求解公式:

F(x) = H(G(V(F(S(x,c)),c))

类似问题套用该公式(框架)就可以用一个递归函数来描述所有问题。但是该公式不包含边界值的处理,边界值是无法再分解为子问题的问题。

计算机中不存在“银弹”,也就是说没有任何一种方法能够解决世界上的所有问题。通过备忘录的思想来处理重叠子问题的方法亦是如此。这种使用缓存处理重叠子问题的方法存在以下限制:

  • 部分问题不存在重叠子问题:如八皇后问题,无重叠子问题则无法使用备忘录来优化;
  • 有些问题看起来像包含“重叠子问题”的子问题,但是这类子问题可能存在后效性,而我们需要无后效性,即通过A阶段的子问题推导B阶段的子问题时,不需要回过头去再根据B阶段的子问题重新推导A阶段的子问题,也就是子问题之间的依赖是单向性的;

总结:如果一个问题可以通过重叠子问题缓存进行优化,那它一定可以被画成一棵树。

赞(1)
未经允许不得转载:北凉柿子 » 动态规划面试宝典
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址