最近在刷算法题目,突然重新思考一下大二时学习的算法分析与设计课程,发现当时没有学习明白,只是记住了几个特定的几个题型;现在重新回归的时候,上升到了方法学上了;感觉到了温故知新的感觉;以下总结自童咏昕老师的算法设计与分析课程和韩军老师的算法分析与设计课程;当我们遇到一个问题的时候,我们先想出一个简单的方法,可以之后再在这个方法的基础上进行优化;
分而治之思路:(存在独立子问题,三个步骤都很重要)
动态规划思路:(存在重叠子问题)
贪心策略思路:(存在单一子问题,需要证明贪心策略正确性)
求解思路:
经典问题:
回溯法:一种优先搜索法,试探法;总体思想就是,在搜索空间树中,按照选择条件向前搜索(深度优先搜索),以达到目标(找到解空间树中满足约束条件的所有解);当搜索到某一步时,发现搜索选择并不优或达不到目标,就回退一步,重新选择(常常使用递归实现);递归实现有三个核心要点:递归出口,函数参数,处理过程。回溯法在求解0/1背包问题的时候,虽然回溯过程中的剪枝,减少了搜索空间;但是整个搜索按深度优先机械进行,是盲目搜索(不可预测本节点以下的节点如何进行);
分支限界法:即在搜索空间树中进行搜索(广度优先,最小耗费优先,最大效益优先方式搜索),以达到求解目标(在满足约束条件的解中,找出在某种意义下的最优解或者找出满足约束条件的解,剪枝的原因)。分支限界算法,首先是确定一个合理的限界函数,然后根据函数确定目标函数的上下界(该届在最优解情况下可更新);然后按照广度优先的策略遍历问题的解空间树,在某一分支上,依次搜索该结点的所有孩子结点,分别估算这些孩子结点的目标函数的可能取值(对于最小化问题估算结点的下界,对于最大化问题,估算该结点的上界);如果某个孩子结点的目标函数值超出了目标函数的界,则将其丢弃(限界),否则加入队列中;
其他算法思想:近似算法,随机算法和启发式算法;
保持更新,转载请注明出处;更多内容请关注cnblogs.com/xuyaowen;