0%

算法:Back Tracking回溯法

Posted on Edited on In Valine:

说到回溯法就让人头大，理解起来倒是很容易，就是把问题看成一个树形的解空间，然后在对这个空间进行DFS深度优先遍历的基础上进行剪枝操作但是要与具体问题结合起来分析就没那么简单了。看了网上很多回溯法的算法框架都写得不明所以，这种东西果然还是要自己动手写一些才行。

n皇后问题

这是回溯法可以解决的一个经典问题。回溯法大体上有递归和非递归两种解法，n皇后问题也不例外。

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int queen[N] = {0};
int gcount = 0;

void Queen_Recursion(int queen[],int i)
{
    queen[i]++;//第i行
    while(无法继续进行 && 还有别的放置方式)
    {
        queen[i] ++;//对i行下一列判断
    }
    if(queen[i] <= N)//第i行的每一列还没判断完
    {
        if(i == N -1 )//最后一行也放完了
        {
            gcount ++;//则确认为一种放法
        }
        else
        {
            i++;
            queen[i] = 0;//从下一行的第一列开始
        }
        Queen_Recursion(queen,i);//递归
    }
    else//i行每一列都判断了
    {
        i--;//回溯到上一行，对下一列判断
        if(i<0)
        {
            return;
        }
        Queen_Recursion(queen,i);//递归
    }

}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void Queen()
{
    int queen[N] = {0};       //初始化
    int i = 0;
    int count = 0;
    while(i>=0)
    {
        queen[i]++;   //列从1开始
        while(无法继续进行 && 还有别的放置方式) //判断此列是否符合条件。
        {
            queen[i] ++;  //下一列
        }
        if(eight_queen[i] <= N)//第i行的每一列还没判断完
        {
            //找到一个位置
            if(i == N-1)
            {
                //这是一个解
                count ++;
            }
            else
            {
                //没有到最后一行，则进行下一行
                i++;
                queen[i] = 0; //下一行的第一列
            }
        }
        else//如果这一行到最后也没有找到合适的列，则回溯上一行。
        {
            i--;
        }
    }
    cout<<count<<endl;
}

回溯法框架

从具体例子反过来理解框架会方便一些

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int a[n];
try(int i)
{
    if(i>n)//遍历到叶子
       输出结果;
     else
    {
       for(j = 下界; j <= 上界; j=j+1)  // 枚举i所有可能的路径
       {
           if(条件)                 // 满足限界函数和约束条件
             {
                a[i] = j;//下一条路径
              ...                         // 其他操作
                try(i+1);//递归
              回溯前的清理工作（如a[i]置空值等）;
              }
         }
     }
}

非递归

int a[n],i;//初始化数组a[]
i = 1;
while (i>0(有路可走)   and  (未达到目标))  // 还未回溯到头
{
    if(i > n)// 搜索到叶结点
    {   
          搜索到一个解，输出；
    }
    else // 处理第i个元素
    { 
          a[i]第一个可能的值；
          while(a[i]在不满足约束条件且在搜索空间内)
          {
              a[i]下一个可能的值；
          }
          if(a[i]在搜索空间内)
         {
              标识占用的资源；
              i = i+1;                              // 扩展下一个结点
         }
         else 
        {
              清理所占的状态空间；            // 回溯
              i = i –1; 
         }
}

未完maybe待续