（精选）最优化方法复习题

平均情况: 设待查找的元素在数组中的概率为P，不在数组中的概率为1-P,若出现在数组中每个位置的概率是均等的为p/n

T(n)=P1D1+P2D2+...+PiDi+(1-P)Dn+1

=p/2+n(1-p/2)

1.叙述分治算法和动态规划算法的基本思想，并比较两种算法的异同。

答:分治法将待求解的问题划分成K个较小规模的子问题,对这K个子问题分别求解,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解.

动态规划将待求解的问题分解成若干的子问题，自底向上地通过求解子问题的解得到原问题的解。动态规划将每个子问题只求解一次并将其解保存在一个表格中,当需要再次求解此子问题时,只是简单的通过查表过的该子问题的解,避免了大量的重复计算.

异同：分治法求解的问题分解后的子问题都是独立的，而使用动态规划求解的问题分解后得到的子问题往往不是相互独立的。

分治法是自顶向下用递归的方法解决问题，而动态规划则是自底向上非递归解决问题。

1. 简述分治算法求解过程的三个阶段。

答:（1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。

（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。

（3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效 性很大程度上依赖于合并的实现。

2. 叙述分治法的基本思想，并分析分治法与减治法二者的区别。

答：分治法将待求解的问题划分成K个较小规模的子问题,对这K个子问题分别求解,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解.

区别：分治法是把一个大问题划分成若干个子问题，分别求解各个子问题，然后把子问题的解进行合并并得到原问题的解。减治法同样是把一个大问题划分成若干个子问题，但是这些子问题不需要分别求解，只需求解其中的一个子问题，因而也无需对子问题的解进行合并。

算法复习试题

一、名词解释：

1、算法：就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。

2、贪心算法：能够得到某种量度意义下的最优解的分级处理方法称为贪心算法。

3、分治法：分治法的求解思想就是把整个问题分成若干个小问题后分的治之

4、递归过程：一个递归过程的执行类似于多个子程序的嵌套调用，递归过程是自己调用自己本身代码。

递归算法的特点：思路清晰，算法的描述简洁且易理解。

5、集合：在研究某一类对象时，可把这类对象的整体称为集合。

6、生成树：设G=(V,E)是一个无向连通图。如果G的生成子图T=(V,E')是一棵树，则称T是G的一棵生成树。

7、算法具有以下5个属性：

有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口

可行性：就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。

输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。

输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。

8、迭代法：称辗转法，是一种不断用变量的旧值递推出新值的解决问题的方法。

9、贪婪法: 是一种不追求最优解，只希望得到较为满意解的方法。贪婪法不要回溯

10、动态规划：是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。

11、分支限界法：是一种用于求解组合优化问题的排除非解的搜索算法。

12、树：树是一个或多个结点的有限集合。

12、二元树：它是结点的有限集合，它或者为空，或者由一个根和两棵树

（左子树和右子树）的不相交的二元树所组成。

13、二分检索树：T是一棵二元树，它或者为空，或者其每个结点含有一个可比 较大小的数据元素。

14、图：图是数据结构，一个图G是由称之为结点V和边E的两个集合组成的

机械优化设计期末复习题

一、填空题

1。组成优化设计数学模型的三要素是 设计变量 、 目标函数 、 约束条件 。

2。函数在点处的梯度为，海赛矩阵为

3。目标函数是一项设计所追求的指标的数学反映，因此对它最基本的要求是能用来评价设计的优劣，，同时必须是设计变量的可计算函数 。

4。建立优化设计数学模型的基本原则是确切反映 工程实际问题，的基础上力求简洁 。

5。约束条件的尺度变换常称 规格化，这是为改善数学模型性态常用的一种方法。

6。随机方向法所用的步长一般按 加速步长 法来确定，此法是指依次迭代的步长按一定的比例 递增的方法。

7.最速下降法以 负梯度 方向作为搜索方向，因此最速下降法又称为

梯度法,其收敛速度较 慢 。

8。二元函数在某点处取得极值的必要条件是 , 充分条件是该点处的海赛矩阵正定

9.拉格朗日乘子法的基本思想是通过增加变量将等式约束 优化问题变成 无约束优化问题，这种方法又被称为 升维 法。

10改变复合形形状的搜索方法主要有反射，扩张，收缩，压缩

11坐标轮换法的基本思想是把多变量 的优化问题转化为 单变量 的优化问题

12．在选择约束条件时应特别注意避免出现 相互矛盾的约束, ，另外应当尽量减少不必要的约束 。

13．目标函数是n维变量的函数，它的函数图像只能在n+1， 空间中描述出来，为了在n维空间中反映目标函数的变化情况，常采用 目标函数等值面 的方法。

14。数学规划法的迭代公式是 ,其核心是 建立搜索方向， 和 计算最佳步长 。

15协调曲线法是用来解决 设计目标互相矛盾 的多目标优化设计问题的。

16。机械优化设计的一般过程中， 建立优化设计数学模型 是首要和关键的一步，它是取得正确结果的前提。

二、选择题

1、下面 方法需要求海赛矩阵。

机械优化设计复习题解答

一、填空题

1、用最速下降法求fX=100x2- x12 2+1- x1 2的最优解时,设X0＝,T,第一步迭代的搜索方向为

-47,-50T;

2、机械优化设计采用数学规划法,其核心一是寻找搜索方向,二是计算最优步长;

3、当优化问题是凸规划的情况下,任何局部最优解就是全域最优解;

4、应用进退法来确定搜索区间时,最后得到的三点,即为搜索区间的始点、中间点和终点,它们的函数值形成 高－低－高 趋势;

5、包含n个设计变量的优化问题,称为 n 维优化问题;

6、函数 CXBHXXTT21的梯度为HX+B;

7、设G为n×n对称正定矩阵,若n维空间中有两个非零向量d0,d1,满足d0TGd1=0,则d0、d1之间存在共轭关系;

8、 设计变量 、 目标函数 、 约束条件 是优化设计问题数学模型的基本要素;

9、对于无约束二元函数),(21xxf,若在),(x20100xx点处取得极小值,其必要条件是

,充分条件是 正定 ;

10、 库恩-塔克 条件可以叙述为在极值点处目标函数的梯度为起作用的各约束函数梯度的非负线性组合;

11、用黄金分割法求一元函数3610)(2xxxf的极小点,初始搜索区间]10,10[],[ba,经第一次区间消去后得到的新区间为 10 ;

12、优化设计问题的数学模型的基本要素有设计变量、 目标函数 、 约束条件;

13、牛顿法的搜索方向dk= ,其计算量大 ,且要求初始点在极小点 附近 位置;

14、将函数fX=x12+x22-x1x2-10x1-4x2+60表示成CXBHXXTT21的形式

;

15、存在矩阵H,向量 d1,向量 d2,当满足d1THd2=0,向量 d1和向量 d2是关于H共轭;