算法分析与设计总结
学习八个星期，经过八个星期的练习，发现算法是一系列解决问题的明确指令，体现了用系统的方法描述解决问题的策略机制。 不同的算法可能在不同的时间、空间或效率上执行相同的任务。 一种算法的优劣可以用空间的复杂性和时间的复杂性来衡量。 可以通过多种方式编写算法，包括自然语言、伪代码和流程图。 计算机系统中的操作系统、语言编译系统、数据库管理系统和各种计算机APP应用系统中的软件必须使用具体算法来实现。 算法的设计与分析是计算机科学和技术的核心问题。
在算法的情况下，他还必须具有以下特征。
1、具有穷举性：算法在执行有限行走后必须退出；
2、确定性：算法的每个步骤都需要准确的定义；
3、输入：一个算法有0个以上的输入，作为算法开始执行前的初始值或初始状态
4、输出项目：一个算法有一个或多个输出，反映输入数据加工的结果；
5、可行性：有限时间内完成计算过程。
在一个算法设计的整个过程中，它包括对问题的需求描述、数学模型的仿真、算法的细节
精细设计、算法正确性验证、算法实现、算法分析、程序测试和文档资料编写。 算法大致可分为基本算法、数据结构算法、数论和代数算法、计算几何算法、图解法算法、动态规划和数值分析、加密算法、排序算法、检索算法和并行算法大致分为以下三种。
1、有限确定性算法；
2、有限费用确定性算法；
3、无限算法。
在这篇文章中，主要写以下算法。
1、递归算法
递归算法是直接或间接调用自己的算法。
对于可递归描述的算法，通常为了解决规模为n的问题，设法分解为规模较小的问题，从该较小的问题的解出发可以容易地构筑大问题的解，另外，该规模较小的问题也使用同样的分解合并方法分解为规模较小的问题特别地，当规模n=0或1时，可以获得直接解。
递归算法解决问题的特点是： (1)递归是指在过程或函数中调用自己；(2)使用递归策略时需要明确的递归终止条件，称为递归出口；(3)虽然求解递归算法问题看起来很简单
递归算法一般用于解决三类问题。 (1)数据的定义是递归定义的。 )2)问题解法用递归算法实现。 )3)数据的结构形式是递归定义的。
递归算法的优点：结构清晰、可读性强，且数学归纳法易于证明算法的正确性，非常便于算法的设计、调试。
递归算法的缺点：递归算法的执行效率低，计算时间也比非递归算法消耗更多的存储空间。
2、分割统治算法
分割统治算法是原问题的解决即子问题的解的综合，将一个复杂问题分成两个以上的相同或相似的子问题，进而将子问题分成更小的子问题，使子问题可以简单地直接解决到最后。 如果元问题可以分割成k个问题，并且这些问题都可以解决，利用这些问题的解求出元问题的解，则这种分割统治法是可行的。 分治法产生的子问题往往是原始问题的小模式，便于使用递归技术。 在这种情况下，通过反复应用分割统治的方法，能够使原问题与子问题的类型一致，但是其规模持续缩小，最终能够使子问题缩小到容易直接求出其解的程度。 这自然会导致递归过程的发生。 分治和递归就像双胞胎兄弟一样，往往同时应用于算法的设计，从而产生很多高效的算法。
分布式算法的三个步骤：
)分解)将原问题分解为规模小、相互独立、形式与原问题相同的几个子问题。
)解决)递归求解各子问题。
(3)合并：将子问题的解合并为原问题的解。
适用条件：
1 )在一定程度上缩小这个问题的规模就很容易解决
2 )这个问题可以分解成几个规模小的同一个问题。 也就是说，这个问题具有最优子结构的性质。
3 )利用该问题分解的子问题的解可以合并为该问题的解；
4 )被这个问题分解的各个子问题是相互独立的。 也就是说，子问题之间不包含共同的子问题。
分布式策略的算法设计模型
是divide_and_conquer(p )
{
if(|p|<；=n0 ) ) ) ) ) ) ) ) ) ) ) ) )。
返回和共享(p；
divide P into smaller substancesP1，P2，…，Pk；
for(I=1； i<；=k； k () ) ) )
yi=divide-and-conquer(pi ) /递归解决
pireturnmerge(y1，y2，…，yk )//合并子问题
}
3、贪婪算法
贪婪算法也称为贪婪算法。 那个在解决问题的时候，总是现在最好的选择。 那不是从整体最优考虑，只是某种意义上的局部最优解。
贪婪
心算法的基本思路如下：（1）建立数学模型来描述问题（2）把求解的问题分成若干个子问题（3）对每一子问题求解，得到子问题的局部最优解（4）把子问题的局部最优解合成原来问题的一个解。贪心算法的求解过程：
（1）候选集合A：为了构造问题的解决方案，有一个候选集合A作为问题的可行解，即问题的最终解均取自候选集合A。
（2）解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成满足问题的完整解。
（3）解决函数solution：检查解集合S是否构成问题的完整解。
（4）选择函数select：即贪心策略，这是关键，指出哪个候选对象最有希望构成问题的解，通常和目标函数有关。
（5）可行函数feasible：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。
贪心算法的一般流程：
Greedy(A) {
S={ }; //初始解集合为空集
while (not solution(S)) //集合S没有构成问题的一个解
{ x= select(A); //在候选集合A中做贪心选择
if feasible(S, x) //判断集合S中加入x后的解是否可行
S = S+{x};
A = A-{x};
}
return S;
｝
4、回溯算法
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。当探索到某一步时，发现原先的选择并不优或达不到目标，就回退一步重新选择，这种走不通就退回再走的技术成为回溯法，满足回溯条件的某个状态的点称为“回溯点”。迷宫问题算法所采用的就是回溯算法。
回溯算法的基本思想：
约束函数：约束函数是根据题意定出的。通过描述合法解的一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分。因此，约束函数是对于任何状态空间树上的节点都有效、等价的。
状态空间树：状态空间树是一个对所有解的图形描述。树上的每个子节点的解都只有一个部分与父节点不同。
扩展节点、活结点、死结点：所谓扩展节点，就是当前正在求出它的子节点的节点，在深度优先搜索中，只允许有一个扩展节点。活结点就是通过与约束函数的对照，节点本身和其父节点均满足约束函数要求的节点；死结点反之。由此很容易知道死结点是不必求出其子节点的（没有意义）。
利用回溯法解题的具体步骤：
首先，要通过读题完成下面三个步骤：
(1)描述解的形式，定义一个解空间，它包含问题的所有解。
(2)构造状态空间树。
(3)构造约束函数（用于杀死节点）。
然后就要通过深度优先搜索思想完成回溯，完整过程如下：
(1)设置初始化的方案（给变量赋初值，读入已知数据等）。
(2)变换方式去试探，若全部试完则转(7)。
(3)判断此法是否成功（通过约束函数），不成功则转(2)。
(4)试探成功则前进一步再试探。
(5)正确方案还未找到则转(2)。
(6)已找到一种方案则记录并打印。
(7)退回一步（回溯），若未退到头则转(2)。
(8)已退到头则结束或打印无解
我们采用装载问题回溯算法数据结构
#define NUM 100
int n; //集装箱的数量
int c; //轮船的载重量
int w[NUM]; //集装箱的重量数组
int x[NUM]; //当前搜索的解向量
int r; //剩余集装箱的重量
int cw; //当前轮船的载重量
int bestw; //当前最优载重量
int bestx[NUM]; //当前最优解算法实现 //形参表示搜索第t层结点
void Backtrack(int t)
{
//到达叶子结点
if(t>n)
{
if(cw>bestw) //更新最优解
{
for(int i=1; i<=n; i++)
bestx[i] = x[i];
bestw = cw;
}
return;
}
//更新剩余集装箱的重量
r -= w[t]; //搜索左子树
if(cw+w[t]<=c)
{
x[t] = 1;
cw += w[t];
Backtrack(t+1);
cw -= w[t];
}
//搜索右子树
if(cw+r>bestw)
{
x[t]=0;
Backtrack(t+1);
}
r += w[t];
//恢复状态
}
5、分支限界算法
分支限界算法是一种在表示问题解空间的树上进行系统搜索的方法。该方法使用了广度
优先策略，同时采用最大收益（或最小损耗）策略来控制搜索的分支。
分支限界法的基本思想是对包含具有约束条件的最优化问题的所有可行解的解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集，并为每个子集内的解计算一个下界或上界。在每次分支后，对所有界限超出已知可行解的那些子集不再做进一步分支，解的许多子集可不予考虑，从而缩小了搜索的范围。这一过程一直进行到找出可行解的值不大于任何子集的界限为止。这种算法一般可以求得最优解。
分支结点的选择
从活结点表中选择下一个活结点作为新的扩展结点，分支限界算法通常可以分为两种形式：
（1）FIFO（First In First Out）分支限界算法
按照先进先出（FIFO）原则选择下一个活结点作为扩展结点，即从活结点表中取出结点的顺序与加入结点的顺序相同。
（2）最小耗费或最大收益分支限界算法
在这种情况下，每个结点都有一个耗费或收益。
根据问题的需要，可能是要查找一个具有最小耗费的解，或者是查找一个具有最大收益的解。
提高分支限界算法的效率：
实现分支限界算法时，首先确定目标值的上下界，边搜索边减掉搜索树的某些分支，提高搜索效率。
在搜索时，绝大部分需要用到剪枝。“剪枝”是搜索算法中优化程序的一种基本方法，需要通过设计出合理的判断方法，以决定某一分支的取舍。
若我们把搜索的过程看成是对一棵树的遍历，那么剪枝就是将树中的一些“死结点”，不能到达最优解的枝条“剪”掉，以减少搜索的时间。
所遵循的原则：
（1） 正确性
（2） 准确性
（3） 高效性
我们同样采用装载问题的例子
装载问题分支限界算法的数据结构
#define NUM 100 int n; //集装箱的数量
int c; //轮船的载重量
int w[NUM]; //集装箱的重量数组算法实现
int MaxLoading()
{
queue<int> Q;
Q.push(-1);
int i = 0;
int Ew = 0;
int bestw = 0;
int r = 0;
for(int j=1; j<n; j++)
r += w[j]; //搜索子空间树
while (true)
{
//检查左子树
int wt = Ew+w[i];
if(wt<=c) //检查约束条件
{
if(wt>bestw) bestw = wt; //加入活结点队列
if (i<n-1)Q.push(wt);
}
//检查右子树
//检查上界条件
if(Ew+r>bestw && i<n-1)
Q.push(Ew); //从队列中取出活结点
Ew = Q.front();
Q.pop();
if(Ew==-1) //判断同层的尾部
{
if(Q.empty()) return bestw; //同层结点尾部标志
Q.push(-1); //从队列中取出活结点
Ew =Q.front();
Q.pop();
i++;
r -=w[i];
}
}
returnbestw;
}
6、 动态规划算法
动态规划算法是解决多阶段决策问题的一种方法。
其中多阶段决策问题:
如果一类问题的求解过程可以分为若干个互相联系的阶段，在每一个阶段都需要做出决策，并影响到下一个阶段的决策。
多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果。
最优性原理:
不论初始状态和第一步决策是什么，余下的决策相对于前一次决策所产生的新状态，构成一个最优决策序列。
最优决策序列的子序列，一定是局部最优决策子序列。
包含有非局部最优的决策子序列，一定不是最优决策序列。
其具体指导思想:
在做每一步决策时，列出各种可能的局部解。
依据某种判定条件，舍弃那些肯定不能得到最优解的局部解。
以每一步都是最优的来保证全局是最优的。
几个概念:
阶段：据空间顺序或时间顺序对问题的求解划分阶段。
状态：描述事物的性质，不同事物有不同的性质，因而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。
决策：根据题意要求，对每个阶段所做出的某种选择性操作。
状态转移方程：用数学公式描述与阶段相关的状态间的演变规律。
动态规划算法的步骤:
(1)分析最优解的性质，并刻画其结构特征；
(2)递归地定义最优值（写出动态规划方程）；
(3)以自底向上的记忆化方法计算出最优值；
(4)根据计算最优值时得到的信息，构造一个最优解。
与此同时在上课学习的过程中，我们还进行了一系列lintcode的题目训练，让我对这些算法的应用有更深的了解。在计算机行业中，这门课程是非常重要的一门课程，对我们这些往计算机方向发展的数学学子来说，这无疑是为我们同计算机专业的学生拓宽了逻辑思维能力，将会提高我们在未来工作中的竞争力。
该谢老师的指导，虽然这门课程结束了，但是我还会继续学习这门课程，让自己更加有竞争力，为自己增彩。