常用算法的伪代码

一、分治策略

分（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<a[m]) j=m-1; else i=m+1; 2.return -1; End

二、动态规划

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，并且它能够解决子问题不相互独立时的某些情况 不同子问题的数目常常只有多项式量级，即在用分治法求解时，有些子问题被重复计算了有限多次。

基本要素 最优子结构:问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质 重叠子问题:递归求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质基本步骤 找出最优解的性质，并刻划其结构特征 递归地定义最优值 以自底向上的方式计算出最优值 根据计算最优值时得到的信息，构造最优解 /*0-1背包问题*/ int knapSack(int W, int wt[], int val[], int n) { if (n == 0 || W == 0) return 0; if (wt[n-1] > 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)); }

三、贪心算法

顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的近似值。

贪心算法需考虑到的方面

候选集（C）问题可能解的集合解集（S）满足问题的完整解，S是C的一个子集可行解函数用于检验S是否构成问题的一个可行解选择函数即贪心策略，也是贪心算法的关键约束函数检测解集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]<dist[i][j]) dist[i]=dist[u]+c[u][j] 3.输出dist End

四、回溯法

回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索

基本思想

针对所给问题，定义问题的解空间确定易于搜索的解空间结构以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索

剪枝函数（Pruning Function）：约束条件或目标函数的界，即判定该节点是否包含问题的解。如果肯定不包含，则跳过对以该节点为根的子树的搜索，这便是所谓的剪枝

/*0-1背包问题回溯算法*/ Begin 设Backtrakc(i)表示对第i层结点的搜索 1. if(i>n)则返回当前解bestp,结束算法 2. if 当前背包重量 cw+w[i]<c,进入左子树 2.1 cw+=w[i];当前价值cp+=v[i]; 2.2 搜索下一层结点 Backtrack(i+1); 2.3 回退,cw-=w[i],cp=v[i]]; 3. 如果Bound(i+1)>bestp,进入右子树,即Backtrack(i+1) End

五、分支界限法

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

基本思想

在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止

/*0-1背包问题回溯算法*/ /*任务分配问题分支界限法*/ Begin 1 根据限界函数计算目标函数的下界down;采用贪心法得到上界up; 2. 将待处理结点活结点表初始化为空； 3. for(i=l;i<=n;i++) x[i]= 0; 4. k=l;i=0; //为第k个人分配任务，i为第k-1个人分配的任务 5. while (k>=l) 5.1 x[k]=l; 5.2 while (x[k]<=n) 5.2.1 如果人员k分配任务x[k]不发生冲突，则 5.2.1.1 计算目标函数值lb; 5.2.1.2 若lb<=up,则将i，<x[k]，k>lb存储在活结点表中; 5.2.2 x[k]=x[k]+l; 5.3 如果k==n且叶子结点的lb值在活结点表中最小, 则输出该叶子结点对应的最优解; 5.4 否则，如果k==n且活结点表中的叶子结点的lb值不是最小,则 5.4.1 up=活结点表中的叶子结点最小的lb值； 5.4.2 将活结点表中超出目标函数界的结点删除； 5.5 i=活结点表中lb最小的结点的x丨k]值； 5.6 k=活结点表中lb最小的结点的k值;k++; End