常用算法及其伪代码

2023-04-22 01:02| 来源: 网络整理| 查看: 265

因为准备有关于算法分析与设计的考试，所以对一些经典的算法问题做了总结。

一、分治策略

分（Divide）将规模为n的问题分解为 k 个规模较小的子问题治（Conquer）对k个子问题分别求解，然后将各个子问题的解合并得到原问题的解分治策略是从下至上求解并将合并得到解

/*二分查找法分治策略*/ Begin 输入有序数组a[],查找元素x,数组最左边下标i，最右边下标j i->0,j->a.length 1.while(i>=j)循环执行: 1.1 设置 m =(i+j)/2; 1.2 if(x==a[m]) return m; 1.3 if(x W) return knapSack(W, wt, val, n-1); else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1), knapSack(W, wt, val, n-1) ); } 三、贪心算法

顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的近似值。贪心算法需考虑到的方面 1）候选集（C）问题可能解的集合 2）解集（S）满足问题的完整解，S是C的一个子集 3）可行解函数用于检验S是否构成问题的一个可行解 4）选择函数即贪心策略，也是贪心算法的关键 5）约束函数检测解集S加入一个候选对象是否满足约束

/*dijkstra算法单源最短路径*/ Begin 1 初始 s={1},v={2...n},dist[i]=c[i][j]; 2 2.1 u=min{dist[i][j]|i属于v} 2.2 s=sU{v},v=v-{u}; 2.3 对于 v 中顶点 i if(dist[u]+c[u][i]n)则返回当前解bestp,结束算法 2. if 当前背包重量 cw+w[i]bestp,进入右子树,即Backtrack(i+1) End 五、分支界限法

求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树

基本思想在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止 /*任务分配问题分支界限法*/ Begin 1 根据限界函数计算目标函数的下界down;采用贪心法得到上界up; 2. 将待处理结点活结点表初始化为空； 3. for(i=l;i=l) 5.1 x[k]=l; 5.2 while (x[k]

【本文地址】

常用算法及其伪代码

常用算法及其伪代码

今日新闻

推荐新闻