回溯法 - webdancer's Blog

回溯法

webdancer posted @ 2011年4月07日 01:50 in 算法 with tags 算法 , 1640 阅读

回溯法:从问题的某一种状态(初始状态)出发,搜索从这种状态出发所能达到的所有“状态”,当一条路走到“尽头”的时候(不能再前进),再后退一步或若干步,从另一种可能“状态”出发,继续搜索,直到所有的“路径”(状态)都试探过。这种不断“前进”、不断“回溯”寻找解的方法,就称作“回溯法”。

回溯算法:

 

  1. 形式化解的结构,根据形式描述,建立解树。解树的每个非叶子节点描述一类可行解,而叶子节点通常描述一个可行解。
  2. 利用深度优先搜索解空间。算法根据目标函数,确定节点所代表解的优化程度,当访问叶子节点时,解就唯一的确定了;访问中间节点时还没法唯一的确定,无法计算目标函数值。利用启发函数和分支定界,避免移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的,这是回溯算法的一个重要特性。

解空间:

回溯算法的解空间一般分为:子集树和排列树。

子集树:二叉树来表示,较为熟悉。

排列树:第一层树有n个选择,第二层有n-1个选择,以此类推,直到叶子节点。

 

子集树和排列树都是“隐式图”。

 

子集树遍历的伪代码:

void backtrack(int  t)

{
     if(t>n)   
        output(x);
     else
        for(int i=0; i<=1; i++)
      {  
             x[t] = i; 
             backtrack(t+1);
       }  
}

排列树遍历的伪代码:

     void backtrack(int  t)

    {
       if(t>n)  

           output(x);
       else      

          for(int i=t; i<=n; i++)
          {
            swap(x[t], x[i]);
            backtrace(t+1);
            swap(x[t], x[i]);       

         }     

   }

 

 

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee