}
}
}
因此算法的计算时间上界为O（n3）。
算法所占用的空间显然为O（n2）。
1.简述算法的五个重要的特征。
：
①有穷性：
一个算法必须包管执行有限步之后结束；②确切性：
算法的每一步调必须有确切的定义；③输入：
一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法自己定义了初始条件；④输出：
一个算法有一个或多个输出，以反映对输入数据加工后的结果。
没有输出的算法是毫无意义的；⑤可行性：
算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
备注：
算法可以没有输入。
因为有些算法中包含了输入，如随机发生输入。
2.简答贪心算法的基本元素：
①贪心选择性质：
所谓贪心选择性质指所求问题的整体最优解可以通过一系列局部最优的选择达到。
②最优子结构性质：
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。
3.简述动态规划算法的基本思想和基本步调以及动态规划问题的特征。
动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而防止计算重复的子问题，以解决最优化问题的算法战略。
按以下几个步调进行：
①分析最优解的性质，并刻划其结构特征。
②递归地定义最优值。
③以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。
④根据计算最优值时得到的信息，构造一个最优解。
动态规划问题的特征：
动态规划算法的有效性依赖于问题自己所具有的两个重要性质：
最优子结构性质和子问题重叠性质。
1、最优子结构：
当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
2、重叠子问题：
在用递归算法自顶向下解问题时，每次发生的子问题其实不总是新问题，有些子问题被反复计算多次。
动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保管在一个表格中，在以后尽可能多地利用这些子问题的解。
4.简述回溯算法的基本思想及解题步调。
回溯法的基本思想：
确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。
这个开始结点就成为一个活结点，同时也成为当前的扩展结点。
在当前的扩展结点处，搜索向纵深方向移至一个新结点。
这个新结点就成为一个新的活结点，并成为当前扩展结点。
如果在当前的扩展结点处不克不及再向纵深方向移动，则当前扩展结点就成为死结点。
换句话说，这个结点不再是一个活结点。
此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。
回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
（9分）
运用回溯法解题通常包含以下三个步调：
（1）针对所给问题，定义问题的解空间；（2分）
（2）确定易于搜索的解空间结构；（2分）
（3）以深度优先的方式搜索解空间，而且在搜索过程中用剪枝函数防止无效搜索。
5.简述分治算法的基本思想及基本步调。
分治法的基本思想：
对于一个输入规模为
的问题，若该问题容易的解决，则直接解决，否则将其分解为
个规模较小的子问题，这些子问题相互独立且与原问题形式相同，递归求解这些子问题，然后将各个子问题的解合并，得到原问题的解。
（9分）
分治法在每一层递归上由以下三个步调组成：
①划分：
将原问题分解为若干规模较小、相互独立、与原问题形式相同的子问题；（2分）
②解决：
若子问题规模较小，则直接解决；否则递归求解各个子问题。
（2分）
③合并：
将各个子问题的解合并为原问题的解。
（2分）
6.分支限界法的基本思想：
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
问题的解空间树是暗示问题解空间的一棵有序树，罕见的有排列树。
在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式分歧。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。
活结点一旦成为扩展结点，就一次性发生其所有儿子结点。
在这些儿子结点中，那些导致不成行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，偏重复上述结点扩展过程。
这个过程一直持续到找到所求的解或活结点表为空时为止。
7.贪心算法的基本思想如下：
从问题的某一个初始解出发逐步迫近给定的目标，以尽可能快的地求得更好的解。
当达到某算法中的某一步不克不及再继续前进时，算法停止，得到问题的一个解。
贪心算法存在问题：
1.不克不及包管求得的最后解是最佳的；2.不克不及用来求最大或最小解问题；3.只能求满足某些约束条件的可行解的范围。
8.动态规划与分治法的异同：
相同点：
动态规划法与分治法类似，它们都是将问题划分为更小的、相似的子问题，并通过求解子问题发生一个全局最优解。
分歧点：
而分治法中的各个子问题是独立的（即不包含公共的子子问题），因此一旦递归地求出各子问题的解后，即可自下而上地将子问题的解合并成问题的解。
但分歧的是，如果各子问题是不是相互独立的，则分治法要做许多不需要的工作，重复地解公共的子问题。
9.分支限界法与回溯法的异同：
分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。
但在一般情况下，分支限界法与回溯法的求解目标分歧。
回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
因此，回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。
10.证明装载问题具有贪心选择性质.
证明:
设集装箱已依其重量从小到大排序,（x1,x2,…,xn）是最优装载问题的一个最优解.又设1.当k=1时,（x1,x2,…,xn）是一个满足贪心选择性质的最优解.
2.当k>1时,取y1=1;yk=0;yi=xi,1因此,（y1,y2,…,yn）是所给最优装载问题的一个可行解
另一方面,由
（y1,y2,…,yn）是一个满足贪心选择性质的最优解
所以,最优装载问题具有贪心选择性质
Hanoi塔问题:
voidhanoi（intn,inta,intb,intc）
{
if（n>0）
{
hanoi（n1,a,c,b）;
move（a,b）;
hanoi（n1,c,b,a）;
}
}
创作时间：
贰零贰壹年柒月贰叁拾日
升级会员 