computer_science

算法

"算法"

Posted by yueLng on 2017-03-30
  1. 穷举=树型搜索
  2. 递归=树型搜索+剪枝
  3. 动态规划=树型搜索+剪枝+节点合并
  4. 因此算法效率：动态规划>递归>穷举。

  1. 递归与分治策略

    一个直接或间接地调用自身的算法称为递归算法。

    分治算法的模式如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    Divide_and_Conquer(P)
    {
        if(|P|<=n0)
        Adhoc(P);//Adhoc(P)是基本子算法
        divide P into smaller subinstances
        P1,P2,...,Pk
        for(i=1;i<=k;i++)
        yi=Divide_and_Conquer(Pi);
        return Merge(y1,y2,...,yk);
    }

  2. 动态规划

  3. 最优子结构：子问题最优时母问题通过优化选择后一定最优的情况叫做“最优子结构”。
  4. 子问题重叠：母问题与子问题本质上是同一个问题的情况称为“子问题重叠”。
  5. 边界：子问题在一定时候就不再需要提出子子问题的情况叫做边界，没有边界就会出现死循环。
  6. 子问题独立：当前被选择的子问题两两互不影响的情况叫做“子问题独立”。

动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略

  1. 贪心算法

    贪心算法总是作出在当前看来是最好的选择。也就是说，贪心算法并不从整体最优上加

    以考虑，它所作出的选择只是在某种意义上的局部最优选择。贪心算法不是对所有问题都能
    得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或是整体最优解的近似
    解。

  2. 回溯法
      回溯法以深度优先的方式系统地搜索一个问题的所有解或任一解，伪代码描述如下：

    1
    2
    3
    4
    5
    6
    Proc Search(当前状态)
    Begin
        If 当前状态等于目标状态 then exit；
        For 对所有可能的新状态
        Search(新状态)；
    End；

  递归回溯的算法框架如下：

1
2
3
4
5
6
7
8
9
10
11
void Backtrack(int t)
{
    if(t>n)// //t 是递归深度，n 是解空间树的高度
        Output(x);
    else
        for(int i=f(n,t);i<=g(n,t);i++){
            x[t]=h(i);
            if(Constraint(t)&&Bound(t))
            Backtrack(t+1);
        }
}

  迭代回溯的算法框架如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void IterativeBacktrack(void)
{
    int t=1;
    while(t>0){
        if(f(n,t)<=g(n,t))//t 是递归深度，n 是解空间树的高度
        for(int i=f(n,t);i<=g(n,t);i++){
            x[t]=h(i);
            if(Constraint(t)&&Bounds(t)){
                if(Solution(t))
                Output(x);
                else
                t++;
            }
        }
        else
        t--;
    }
}

  用回溯法搜索子集树的一般算法可描述为：

1
2
3
4
5
6
7
8
9
10
void Backtrack(int t){
    if(t>n)
        Output(x);
    else
        for(int i=0;i<=n;i++){
            x[t]=h(i);
            if(Constraint(t)&&Bounds(t))
            Backtrack(t+1);
        }
}

  用回溯法搜索排列树的一般算法可描述为：

1
2
3
4
5
6
7
8
9
10
11
12
void Backtrack(int t)
{
    if(t>n)
        Output(x);
    else
        for(int i=t;i<=n;i++){
            Swap(x[t],x[i]);
            if(Constraint(t)&&Bounds(t))
            Backtrack(t+1);
            Swap(x[t],x[i]);
        }
}

4.分支界限法
  分为队列式(FIFO)分支界限法和优先队列式分支界限法。

  1. 概率算法
CATALOG
    FEATURED TAGS
    computer_science
    FRIENDS