算法设计基础

㈠ 算法设计的5种基本方法

步骤/方式1
一、【分治法】
分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
步骤/方式2
二、【动态规划法】
最优化原理是动态规划的基础，任何一个问题，如果失去了这个最优化原理的支持，就不可能用动态规划方法计算。
使用动态规划求解问题，最重要的就是确定动态规划三要素：问题的阶段，每个阶段的状态以及从前一个阶段转化到后一个阶段之间的递推关系。
步骤/方式3
三、【贪心算法】所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。贪心算法的基本思路如下：
1. 建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
步骤/方式4
四、【回溯法】
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
用回溯法解题的一般步骤：
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
步骤/方式5
五、【分支限界法】
基本思想 ：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
常见的两种分支限界法：
（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

㈡ 学习算法分析与设计需要那些基础(是否需要学习离散数学和线性代数)

算法分析与设计，目前国内本科生和硕士生的教材好像都是从国外翻译过来的。听起来挺复杂的样子，如果简单地掌握和运用还是不难的，大部分内容在数据结构中都涉及过，实际编程中也运用比较多，难的在于算法的理论研究，如21世纪的七大难题之一的NP问题就是算法问题（涉及逻辑可满足性问题）。

简单地讲需要的基础有以下几类：
1、基础类（相对一般本科生而言）：（1）把数据结构学好了算法就不难的，而数据结构其实就是图论的运用，如果是非数学专业的学生可以看离散数学中的图论部分。（2）算法分析设计时间和空间复杂度的计算，常用的还是毛泽东的战略思想——以空间换取时间。所以要学会简单的数量级运算，涉及部分代数式和数论的知识。只要简单掌握运算就可以了，不必深究。
2、提高型（研究生水平）：图论、组合数学、数理逻辑学要专门学习，可以采用数学系本科生的图论、组合数学、数理逻辑学等专业课的教材。其中组合数学中的组合设计在一定程度上和算法设计有异曲同工之处。
3、研究型（专业研究）：这主要看自己的研究方向了，如果研究能力强的话可以在很短时间内可以把需要遇到的数学知识搞懂，没有现成的固定模式。其中如研究NP问题，需要非常精深的逻辑学知识和数论基础。但不管哪个研究方向，数学的缜密思维和推理能力都是必备的，这不是一朝一夕可以练就的，需要长时间的锻炼。

以上仅个人一点点体会，仅供参考。