算法设计与分析_总结1

《算法设计与分析_总结1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一些概念递归：直接或间接的调用自身算法称为递归算法；用函数自身给出定义的函数称为递归函数。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治法（divide-and-conquer）的基本思想：A分割成k个更小规模的子问题。B对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。C将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解

2、。设计动态规划算法的步骤(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。最优子结构性质：矩阵连乘计算次序问题的最优解包含着其子问题的最优解。递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质贪心算法:贪心算法总是作出在当前看来最好的选择,它并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。活动安排问题就是要在所给的活动集合中选

3、出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。贪心算法：贪心算法求解的这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质贪心算法与动态规划算法的差异：贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式

4、作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?单源最短路径基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊

5、路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。回溯法的基本思想：(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。常见的两种分支限界法：（1）队列式(FIFO)分支限界法。按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。（2）优先队列式分支限

6、界法。按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。布线问题算法思想：解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。即加入剪枝的广度优先搜索。随机存储机R

7、AM它描述的形式计算机是一台带累加器计算机，他不允许程序修改其自身，RAM由只读输入带、只写输入带、程序存储部件、内存储器和指令计数器5个部分组成。P类和NP类语言的定义P={L

8、L是一个能在多项式时间内被一台DTM所接受的一眼}NP+{L

9、L是一个能在多项式时间内被一台NDTM所接受的语言}由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被非确定性图灵机接受。故P属于NPP类问题：是确定性计算模型下的易解问题类。NP类问题：是非确定性计算模型下的易验证问题类。NP完全类问

10、题：即多项式复杂度的非确定性问题类；简单的写法是NP=P？问题就在这个问号上，到底是NP等于P，还是NP不等于P。算法的渐进时间复杂性的含义？答：当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。最坏情况下的时间复杂性和平均时间复杂性有什么不同？答：最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的