* 暴力破解(brute force)
暴力破解, 就是穷举. 穷举的方式一般用递归, O(n^2). 优化的思路是减少递归步骤:
1. 更加严格的静态递归条件
2. 增加 close_list, 动态地判断是否需要进行递归, close_list 根据执行情况动态变化
另外的一种优化方向是消除递归. 因为递归是可以通过递归栈 open_list 来消除的. 可以对栈进行动态排序, 优先进行最可能成功的下一个步骤(A*). 这种排序优化, 导致可以使用不同的数据结构来存储递归栈: stack, queue, priority_queue.
有序性, 有序子集: 有一种非常常用的优化思路是利用输入条件的局部有序性(存在有序的子集), 不再穷举这些有序的子集. 在处理这些有序子集时, 采用 O(n) 或者 O(K) 算法, 最差也能采用二分法 O(logN), 而且其它元素与这些有序子集结合时, 也不再需要穷举.
A* 算法: open_list 根据沉没成本G和未来成本(H)之和来决定下一个处理步骤, 达成即最优.
* 动态规划(dynamic programming)
动态规划与暴力破解类似, 都是分而治之的思路, 但又不相同. 动态规划的下一个处理步骤是唯一的, 而且 open_list 初始可以确定, 后续单调递减. 下一个步骤的处理除了依赖自身的静态条件, 还依赖之前的处理结果集, 并维护这个结果集. 有点像消除了递归之后的暴力破解, 但暴力破解的 open_list 不是初始固定的.
* 直观解法(coding)
这类问题的解法非常直观, 一般没有算法上的优化空间, 也不需要技巧, 纯粹是为了训练编程能力. 考察做题者对变量的状态判断是否完备充分, 判断路径是否最简, if 分支是否可以合并等等. 所以, 就是考察边界条件的判断, 还有逻辑条件精减, 要求有非常强的逻辑思维能力.
一般这类题就是链表翻转, 有序链表合并, 删除重复元素, 数组遍历(螺旋向内, 螺旋向外, 蛇形, 等等), partition 等.
要点是: 边界判断, 分支合并, 简化重合边界的处理, 增加虚拟节点进行辅助.
Loading ...