算法设计与分析
借着算法设计与分析这门课的考试临近，好好的翻了翻这本书，总结了一下基本的算法基础知识，还有几个基本的算法的基本内容，以及一些问题的实现算法，时间复杂度等信息。 算法之间有着异同点，掌握这些对理解算法有着很大的帮助。
算法设计与分析基础
- 算法概述 算法的定义： 算法是解题方案的准确而完整的描述，也就是解题的方法和步骤。 对算法一次给出精确的定义是很难的。算法是计算机解决某一类特定问题的一组规则的有穷集合，或者说是对特定问题求解步骤的一种描述，他是指令的有限序列。 简而言之，算法就是有效求出问题的解，对问题的求解过程进行精确的描述。
- 算法的特征 算法有以下几个特征：输入，输出，确定性，可行性，有穷性。
- 算法的基本要素 一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，而是算法的控制结构。
- 描述算法的工具 自然语言，流程图，N-S流程图，伪代码。
- 算法与程序和数据结构的关系 （1）算法代表了对特定问题的求解，算法是行为的说明，是一组逻辑步骤。而计算机程序则是算法用某种程序设计语言的表述，是算法在计算机上的具体实现。一个算法可以用不同的编程语言编写出不同的程序，程序并不都满足算法所要求的特征。 （2）算法是数据结构的灵魂，数据结构则是算法的基础。算法 + 数据结构 = 程序。
- 算法评价的基本原则 正确性，可读性，健壮性，可靠性，效率，简明性，最优性，算法的复杂度。
- 算法复杂度 算法的复杂度主要包括时间复杂度，空间复杂度
- 渐进表示法（略）
递归算法
- 递归算法的思想 递归算法是哟中通过自身调用自身或间接调用自身来达到问题解决的算法。递归的基本思想就是把一个要求解问题划分为一个或多个规模更小的子问题，这些规模更小的子问题应该同原问题保持同一类型，然后用同样的方法求解规模更小的子问题。
- 递归算法的特性
(1)求解规模为n的问题可以转化为一个或多个结构相同，规模较小的子问题然后从这些小问题中能够方便的构造出大问题的解。 (2)递归调用的次数必须是有限的。 (3)必须有结束递归的条件
- 递推关系 递推关系常用来分析递归算法的时间和空间代价，计算递推式通常有三种方法：替换方法，迭代方法，公式法。
- 递归算法的执行过程 递归算法的计算过程是由复杂到简单再到复杂，迭代算法的计算过程是由简单到复杂。
- 递归法应用 罗汉塔问题$\omicron(2^n)$，斐波那契数列$\omicron(2^n)$,八皇后问题$\omicron(n^3)$
分治算法
- 分治算法的思想 对一个规模为n的大问题可以通过分解为k个规模较小的相互独立且与原问题结构相同的子问题进行求解。首先通过递归来求解这些子问题，然后对个子问题的解进行合并得到原问题的解。
- 分治算法的特征
(1)原问题的规模缩小到一定程度可以很容易被求解。 (2)原问题可以分解为若干个规模较小的同构子问题。 (3)各子问题的解可以合并为原问题的解。 (4)原问题所分解出的个个字问题之间是相互独立的，即子问题之间不包含公共的子问题。
- 利用分治算法求解问题的三个步骤 (1)分解，将原问题分解为若干个相互独立，规模较小的子问题。 (2)解决，如果子问题规模小到可以直接求解，否则需要递归求解各个子问题。 (3)合并将各个子问题的结果合并成原问题的解。
- 分治法应用 归并排序$\omicron(n\log_2n)$，快速排序$\omicron(n\log_2n)$，最大子段和$\omicron(n\log_2n)$，棋盘覆盖问题$\omicron(k^4)$，
贪心算法
- 贪心算法的思想 贪心算法是通过分步决策，每步都能形成局部解，利用这些局部解来构成问题的最终解；如果想要求最终的解是最优解，每步的解必须是当前步骤的最优解。
- 贪心算法的基本要素 最优度量标准，最优子结构性质
- 贪心算法的求解过程 候选解集C，解集S，解决函数solution，选择函数select，可行函数feasible 利用贪心算法求解问题一般分为以下三个步骤：分解，求解，合并。
- 贪心算法的优点是求解速度快时间复杂度低，其缺点是需要证明要求解的问题是最优解。
- 贪心算法的应用 背包问题$\omicron(n\log_2n)$，多机调度问题$\omicron(nm)$,Dijkstra $\omicron(n^2)$,采用贪心策略求解最小生成树的主要方法Prim$\omicron(n^2)$和Kruskal$\omicron(e\log_2e)$
动态规划算法
- 动态规划的基本思想 动态规划算法处理的对象是多阶段复杂决策问题。动态规划算法与分治法类似，其基本思想是将带求解的问题分解为若干个子问题（阶段），然后分别求解各个子问题（阶段），最后将子问题组合起来得到原来问题的解。但是经动态规划算法分解得到的子问题不同于分治法的是，子问题往往不是相互独立的，而是相互联系又相互区别的。
- 动态规划算法的特点（求解步骤）
(1)所求解的问题满足最优性原理，具有最优子结构性质。 (2)递归定义最优解决方案。 (3)自底向上的方式计算出最优解的值 (4)构造最优解
- 贪心算法与动态规划算法的比较 贪心算法要求针对问题设计最优度量标准，但这在很多情况下并不容易做到，动态规划算法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，可以处理不具备贪心准则的问题。
- 是否采用动态规划算法 一般依赖于两个重要的特性：最优子结构性质，重叠子问题性质。
- 动态规划算法的应用 最优二叉搜索树$\omicron(n^3)$，近似串匹配问题$\omicron(mn)$，多段图问题$\omicron(n+e)$，Floyd $\omicron(n^2)$，0/1背包问题$\omicron(2^n)$(最坏的情况下)，最长公共子序列$\omicron(min(m,n))$，流水调度问题$\omicron(n\log_2n)$
回溯算法
- 回溯算法的思想 回溯算法是一种在接空间搜索可行解或最优解的方法。该方法通常将解空间看作树形结构，及状态空间树。搜索过程中以深度优先队状态空间书进行遍历以避免遗漏可行解。另外该过程以跳跃式搜索改善算法的运行效率，既不满足于约束条件的内节点子树将会被剪枝，此时搜说过程将会回溯到该节点的父节点进行后续的深度遍历。
- 回溯算法的基本概念
状态空间树和显式约束，解空间通常会被描述为树状结构，及状态空间。显式约束通常可以从问题描述中直接获得，规定了带求解问题的所有可能的候选解，显式约束决定了状态空间树的规模。 隐式约束，隐式约束用来判断一个候选解是否为可行解。 最优解和目标函数，目标函数也称为代价函数，用来衡量每个可行解的优劣，最优解使得目标函数取得极值的一个或多个可行解。 部分向量，每个节点对应了一个部分向量。 搜索策略和剪枝函数，DFS，BFS，函数优先深广结合，剪枝函数有两类：约束函数，限界函数
- 使用回溯算法的基本步骤 （1）针对给定的问题，定义解空间。 （2）确定易于搜索的解空间结构（找出适当剪枝函数）。 （3）以深度优先方式搜索解空间树，并在搜索过程中使用剪枝函数避免无效搜索。
- 回溯算法的使用条件 是否满足多米诺性质
- 回溯算法的应用 装载问题$\omicron(2^n)$，0/1背包问题$\omicron(2^n * 2)$,n皇后问题$\omicron(n!)$最坏情况下，m图着色问题$\omicron(nm^n)$,子集和数问题$\omega(2^n)$
- 影响算法效率的因素 （1）分支情况，即分支是否均匀。 （2）树的深度，深度越深，通常效率越低下。 （3）对称程度，具有高度对称性的状态空间树适合裁剪。
- 回溯算法的改进途径 （1）节点少的分支优先，解多的分支优先。 （2）利用状态空间树的对称性裁剪空间。 （3）分解为子问题。
分支限界算法
分支限界算法常以广度优先或最小耗费有限的方式搜索问题的解空间树。解空间树表示问题解空间的一颗有序树，常见的有子集树和排序树。在搜索问题的解空间树时和回溯算法的主要区别在于他们对当前节点的采用的扩展方式不同。分支限界算法中，每一个活节点只有一次机会成为扩展节点，一旦成为扩展节点，就一次性产生其所有儿子节点。这些儿子节点中导致不可行解或者导致非最优解的儿子节点被舍弃，其余儿子节点被加入到活节点表中。此后从活节点中取下一个节点成为当前扩展节点，并重复上述节点扩展过程，直到找到所求解，活着活节点表为空为止。
