Ca985d682c2a978d4320803129d29576
回溯算法

1 引言

  回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
  例如:在玩迷宫游戏时,就应用到了回溯法。当游戏者到达某个路口时,面前有多条路可以选择时,任意选择其中一条前进。若沿着某一条路前进至死胡同时,无法继续前进。此时游戏者将退回至上一个做决策的路口,选择另外一条可行的路径进行探索下去,直至成功走出迷宫。

2 基础知识

  问题的解空间树:一个复杂问题的解决方案是由若干个小的决策步骤组成的决策序列,所以一个问题的解可以表示成解向量X=(x1,x2,.....xn),其中分量xi对应第i步的选择,X中个分量xi所有取值的组合构成问题的解向量空间,简称解空间或者解空间树(因为解空间一般用树形式来组织),由于一个解向量往往对应问题的某个状态,所以解空间又称为问题的解空间树。
  第一层节点(根节点):解空间树的根节点表示搜索的初始状态。
  第二层节点:表示对解向量第一个分量做出选择后到达的状态。
  第一层到第二层的边上标记为第一个分量选择结果。以此类推,则构成由根节点到叶子节点的解空间。
  可行解:解空间中满足约束条件的解空间。
  最优解:解空间中使目标函数取最大或者最小值的可行解。

  例如:在走迷宫问题时,迷宫的入口位置即可对应解空间树的根节点,第一次遇到岔路口时,则需要对第一个分量做出选择,在做出第一步选择后,产生了不同的状态,则根据不同的状态形成第二层节点,这样一步步选择下去,最终形成解空间树。

3 算法流程

  (1)设置初始化的方案(给变量赋初始值,读入已知数据等)。
  (2)变换方式去试探,若全部试完则转(7)。
  (3)判断此法是否成功(通过约束函数),不成功则转(2)。
  (4)试探成功则前进一步再试探。
  (5)正确方案还是未找到则转(2)。
  (6)以找到一种方案则记录并打印。
  (7)退回一步(回溯),若未退到头则转(2)。
  (8)已退到头,则结束或打印无解。

4 求子集问题

问题描述:
  已知一组数(其中无重复元素),求这组数可以组成的所有子集。结果中无重复元素。
例如:输入集合为:nums = [1,2,3]
输出结果为:[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]。

算法设计:
  利用回溯方法生成子集,即对于每个元素,都有试探放入或不放入集合中两种选择:
选择放入该元素,递归的进行后续元素的选择,完成放入该元素后续所有元素的试探;之后将其拿出,即再进行一次选择不放入该元素,递归的进行后续元素的选择,完成不放入该元素后续所有元素的试探。
  例如:当遇到元素1时,有两种选择,放入集合或者不放入集合,则此时对于第一个分量选择,得到两种状态,在对后续的元素2,3继续执行选择操作。得到的解空间树如下:

代码实现:

#include<stdio.h>
#define MAX 100
void back(int i,int n);
int a[MAX];//存储集合元素
int count=0;//记录子集个数,其实没必要记录,因为count=2^n这是很显然的。
int b[MAX]={0};//存储集合元素状态
int k=1;//表示第k个元素,从1开始数
int main()
{
    int i=0, n;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    back(1,n);//从第一个元素开始,确定第一个元素的状态
    printf("%d",count);
    return 0;
}
void back(int i,int n)
{
    int j;
    int sum =0;
    if(i>n)//i>n表示所有元素的状态都已经确定,那么接下来打印出来
    {
        printf("{");
        for(j=1;j<=n;j++)
        {
            if(b[j])    
                printf("%d,",a[j]);
                //sum +=a[j];求子集之和
        }
        //printf("%d",sum);
        printf("}\n");
        count++;
        return ;
    }
    {
        b[i]=1;//取第i个元素
        back(i+1,n);//处理下一个元素
        b[i]=0;//不取第i个元素
        back(i+1,n);//处理下一个元素
    }
    return ;    
}

5 迷宫问题

问题描述:
  以一个M×N的长方阵表示迷宫,1和0分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。
例如:7X7的迷宫输入为:

0,0,0,0,0,0,0,0,0,
0,1,1,0,1,0,0,0,0,
0,1,1,0,0,0,0,0,0,
0,0,1,1,0,0,0,0,0,
0,1,0,1,1,0,0,0,0,
0,0,0,1,1,0,0,0,0,
0,0,0,0,1,1,1,0,0,
0,0,0,1,1,0,1,1,0,
0,0,0,0,0,0,0,0,0

输出为:

1,1 -> 2,1 -> 2,2 -> 3,2 -> 3,3 -> 4,3 -> 5,3 -> 5,4 -> 6,4 -> 6,5 -> 6,6 -> 7,6 -> 7,7
1,1 -> 2,1 -> 2,2 -> 3,2 -> 3,3 -> 4,3 -> 4,4 -> 5,4 -> 6,4 -> 6,5 -> 6,6 -> 7,6 -> 7,7
1,1 -> 1,2 -> 2,2 -> 3,2 -> 3,3 -> 4,3 -> 5,3 -> 5,4 -> 6,4 -> 6,5 -> 6,6 -> 7,6 -> 7,7
1,1 -> 1,2 -> 2,2 -> 3,2 -> 3,3 -> 4,3 -> 4,4 -> 5,4 -> 6,4 -> 6,5 -> 6,6 -> 7,6 -> 7,7

问题分析:
  采用回溯法求解问题,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前进;否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路。假如所有可能的通路都探索到而未能到达出口,则所设定的迷宫没有通路。

代码实现:
```

include

define R 7

define C 7

int Move[4][2]={1,0,0,1,-1,0,0,-1};//下一步的方向:move[0][]下,move[1][]右,move[2][]上,move[3][]左

int M[R+2][C+2]={
{0,0,0,0,0,0,0,0,0},
{0,1,1,0,1,0,0,0,0},
{0,1,1,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0},
{0,1,0,1,1,0,0,0,0},
{0,0,0,1,1,0,0,0,0},
{0,0,0,0,1,1,1,0,0},
{0,0,0,1,1,0,1,1,0},
{0,0,0,0,0,0,0,0,0}
}; //初始化迷宫,1为路,0为墙
int Q[R+2][C+2]={0};
int stack[100][2]; //存放路线

top Created with Sketch.