算法设计期末总结.doc

第一部分：算法基础1、算法五个特征：零个或多个输入、至少一个输出、确定性、能行性、有穷性。2、算法意义：算法就是求解一类问题的任意一种特殊的方法。3、算法与程序的联系与区别：联系：算法+数据结构=程序，算法是程序设计的核心，算法的好坏程度上决定了一个程序的效率。一个好的算法可以降低一个程序运行的时间复杂度和空间复杂度。区别：算法是解决问题的步骤，程序是算法的代码实现依靠程序来完成功能，程序作为算法的灵魂。程序是结果算法是手段，编写一个同样功能的程序，使用不同的算法，可以让程序的体积和效率有很大的该变。4、好算法的特性：正确性、简明性、效率、最优性（健壮性、可靠性）。5、影响程序运行的时间因素：程序所依赖的算法、问题规模和输入数据、计算机系统性能6、时间复杂性分为3种情况，最好情况、平均情况、最坏情况，可操作性最好，最具有实际价值的是最坏情况下的时间复杂性。7、渐进表示法：大O几号（渐进上界）：定义：设函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在两个正常数c和n0,使得当n=n0时，有f(n)= n0时，有f(n)=cg(n),则记做f(n)= (g(n),称为记号（omega notation）【算法设计与分析c+描述第二版陈惠南p20面例题】。记号（渐进下界）：定义：设有函数f(n)和g(n)是定义在非负整数集合上的正整数，如果存在正常数c1,c2和n0,使得当n=n0时，有c1g(n)=f（n）4，从3处断开，于是就得出（A0（A1，A2）(A3（A4，A5）)例题：1】p0=20, p1=10, p2=8, p3=5, p4=40, mii=0，sii=i，i=0,1,2,3; m01=minm00+ m11+20*10*8=1600，s01=0； m12=minm11+ m22+10*8*5=400，s12=1； m23=minm22+ m33+8*5*40=1600， s23=2； 计算过程： m02=minm00+ m12+20*10*5, m01+ m22+20*8*5, =min400+1000,1600+800=1400，s02=0 ； m13=minm11+ m23+10*8*40, m12+ m33+10*5*40, =min1600+3200,400+2000=2400，s13=2 ； m03=minm00+ m13+20*10*40, m01+ m23+20*8*40, m02+ m33+20*5*40 =min2400+8000,1600+1600+6400,1400+4000=5400，s03=2*完全加括号的形式：（A0 （A1 A2 ）A3 ）第五部分：回溯法1、 回溯法 法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。第六部分：分枝界限法1、分枝限界法 法在问题的解空间树中，按广度优先策略，从根结点出发搜索解空间。*附加*回溯法和分支限界法的不同之处。通过搜索状态空间树的方法求问题答案的方法可分为两类: 深度优先搜索和广度优先搜索. 如果在运用搜索算法是使用剪枝函数, 便成为回溯法和分枝限界法. 一般而言, 回溯法的求解目标是在状态空间树上找出满足约束条件的所有解, 而分枝限界法的求解目标则是找出满足约束条件的一个解, 或是在满足约束条件的解中找出最优解.递推关系式#include #includeusing namespace std; #define MAX 99 /定义无穷大 struct Nodeint length; /权值（源点到该结点的路径长度）int i; /结点编号friend bool operator b.length;class Graph public: void ShorestPaths(int); void ShowDist(); Graph(); Graph();private: int n; /图的节点个数 int *prev; /存放顶点的前驱节点 int *c; /存放图的邻接矩阵 int *dist; /存放源点到各个顶点的距离 ; Graph:Graph() int wi = 0; int yi = 0; int s;int i,j,m; coutn; couts; c = new int*n; for (wi = 0; wi n; wi+) cwi = new intn; dist = new intn; prev = new intn; for (wi = 0; wi n; wi+) /初始化邻接矩阵 for (yi = 0; yi n; yi+) cwiyi = MAX; cout请输入图的边( i，j，ci,j ) endl;/ 以邻接矩阵存储，(无穷大（99）代表节点间无边 for (wi = 1; wi ijm;cij = m; for (wi = 0; wi n; wi+) /初始化数组 distwi = MAX; prevwi = -1; Graph:Graph() for(int i=0;in;i+) delete ci; delete c;delete dist;delete prev;void Graph:ShowDist() cout endl 从源点到各节点的最短路径: endl; int i = 0; int temp = 0; for (i = 0; i n; i+) cout dist i = disti endl; cout 从源点到终点的最短路径长度为: distn-1 endl; cout =0 ) cout temp; if(temp) cout -; temp = prevtemp; cout endl; void Graph:ShorestPaths(int v) priority_queue H; /定义优先队列（最小堆） Node E; /扩展节点 E.i = v; E.length = 0; distv = 0; cout当前扩展节点：E.i，权重：E.lengthendl; while (true) int j; for (j = 0; j n; j+) /查找该结点的所有邻接点 if (cE.ij != MAX) & (E.length + cE.ij distj) ) /邻接点 distj = E.length + cE.ij; prevj = E.i; /记录前驱结点/加入活结点优先队列 ,若节点为终点，则不加入活结点队列 if (j != n-1) Node N; N.i = j; N.length = distj; H.push(N); /N结点入队 cout入队结点：N.i,权重：N.lengthendl; /forif(!H.empty() E=H.top();/出队 cout出队：E.