常用算法及其伪代码

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

一、分治策略

分（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)
                  );
}

三、贪心算法

顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的近似值。
贪心算法需考虑到的方面
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]<dist[i][j]) dist[i]=dist[u]+c[u][j]
    3.输出dist
End

四、回溯法

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

• 基本思想
  1）针对所给问题，定义问题的解空间
  2）确定易于搜索的解空间结构
  3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索
  剪枝函数（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

五、分支界限法

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

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

/*任务分配问题分支界限法*/
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