回溯算法原理和几个常用的算法实例

回溯算法思想：回溯〔backtracking〕是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间〔solutionspace〕，这个空间必须至少包含问题的一个解〔可能是最优的〕。

下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图(迷宫问题)或树(N皇后问题)。一旦定义了解空间的组织方法，这个空间即可按深度优先的方法从开始节点进行搜索。回溯方法的步骤如下：1)定义一个解空间，它包含问题的解。

2)用适于搜索的方式组织该空间。

3)用深度优先法搜索该空间，利用限界函数防止移动到不可能产生解的子空间。回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保存从开始节点到当前节点的路径。因此，回溯算法的空间需求为O〔从开始节点起最长路径的长度〕。这个特性非常重要，因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话，再多的空间也不够用。算法应用：回溯算法的求解过程实质上是一个先序遍历一棵"状态树"的过程,只是这棵树不是遍历前预先建立的,而是隐含在遍历过程中。(1)幂集问题(组合问题)(参见《数据结构》〔严蔚敏〕)求含N个元素的集合的幂集。

如对于集合A={1,2,3},那么A的幂集为

p(A)={{1,2,3},{1,2},{1,3},{1},{2,3},{2},{3},Φ}

幂集的每个元素是一个集合，它或是空集，或含集合A中的一个元素，或含A中的两个元素，或者等于集合A。反之，集合A中的每一个元素，它只有两种状态：属于幂集的元素集，或不属于幂集元素集。那么求幂集P〔A〕的元素的过程可看成是依次对集合A中元素进行“取〞或“舍〞的过程，并且可以用一棵状态树来表示。求幂集元素的过程即为先序遍历这棵状态树的过程。程序：#include<stdio.h>

#include<malloc.h>

#defineERROR0

#defineOK1

typedefintElemType;

typedefstructLNode

{

ElemTypedata;

structLNode*next;

}LNode,*LinkList;

//初始化

LinkListListInit()

{

LNode*base=(LinkList)malloc(sizeof(LNode));

base->data=0;

base->next=NULL;

returnbase;

}

//插入一个元素

intListInsert(LinkListL,inti,ElemTypee)

{

LNode*p,*s;

intj=0;

p=(LNode*)L;

while(p&&j<i-1)

{

p=p->next;

++j;

}

if(!p||j>i-1)

returnERROR;

s=(LNode*)malloc(sizeof(LNode));

s->data=e;

s->next=p->next;

p->next=s;

returnOK;

}

//删除一个结点

intListDelete(LinkList&L,inti,ElemType&e)

{

LinkListp=L,q;

intj=0;

while(p->next&&j<i-1)

{

p=p->next;

++j;

}

if(!(p->next)||j>i-1)

returnERROR;

q=p->next;

p->next=q->next;

e=q->data;

free(q);

}

//长度

intListLength(LinkListL)

{

LinkListp=L;

intj=0;

if(!L)

returnERROR;

while(p->next)

{

p=p->next;

++j;

}

returnj;

}

//查找一个元素

intGetElem(LinkListL,inti,ElemType&e)

{

LNode*p=L;

intj=0;

while(p->next&&j<i)

{

p=p->next;

++j;

}

if(!p||j>i)

returnERROR;

e=p->data;

returnOK;

}

//输出链表元素

voidDisplay(LinkListL)

{

LNode*p=L;

if(!(p->next))

{

printf("NULL,");

return;

}

elsep=p->next;

while(p)

{

printf("%d,",p->data);

p=p->next;}

}

//求幂集

voidPowerSet(inti,LinkListA,LinkList&B)

{

intk=0;

ElemTypee=0;

if(i>ListLength(A))

{

Display(B);

printf("\n");

}

else{

GetElem(A,i,e);

k=ListLength(B);

ListInsert(B,k+1,e);

PowerSet(i+1,A,B);

ListDelete(B,k+1,e);

PowerSet(i+1,A,B);

}

}

intmain()

{

LinkListlist=ListInit();//初始化

LinkListlist2=ListInit();//初始化

ListInsert(list,1,1);//插入元素

ListInsert(list,2,2);

ListInsert(list,3,3);

Display(list);//输出元素

printf("\npowersetis:\n");

PowerSet(1,list,list2);//求幂集

}(2)迷宫问题(参见《数据结构》〔严蔚敏〕)

计算机解迷宫时，通常用的是"试探和回溯"的方法，即从入口出发，顺某一方向向前探索，假设能走通，那么继续往前走；否那么沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止,如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道。1．从入口进入迷宫之后，不管在迷宫的哪一个位置上，都是先往东走，如果走得通就继续往东走，如果在某个位置上往东走不通的话，就依次试探往南、往西和往北方向，从一个走得通的方向继续往前直到出口为止；2．如果在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通；3．所谓"走不通"不单是指遇到"墙挡路"，还有"已经走过的路不能重复走第二次"，它包括"曾经走过而没有走通的路"。显然为了保证在任何位置上都能沿原路退回，需要用一个"后进先出"的结构即栈来保存从入口到当前位置的路径。并且在走出出口之后，栈中保存的正是一条从入口到出口的路径。由此，求迷宫中一条路径的算法的根本思想是：

假设当前位置"可通"，那么纳入"当前路径"，并继续朝"下一位置"探索；假设当前位置"不可通"，那么应顺着"来的方向"退回到"前一通道块"，然后朝着除"来向"之外的其他方向继续探索；假设该通道块的四周四个方块均"不可通"，那么应从"当前路径"上删除该通道块。设定当前位置的初值为入口位置；

do{

假设当前位置可通，

那么{

将当前位置插入栈顶；//纳入路径

假设该位置是出口位置，那么算法结束；

//此时栈中存放的是一条从入口位置到出口位置的路径

否那么切换当前位置的东邻方块为新的当前位置；

}

否那么

{

假设栈不空且栈顶位置尚有其他方向未被探索，

那么设定新的当前位置为:沿顺时针方向旋转找到的栈顶位置的下一相邻块；

假设栈不空但栈顶位置的四周均不可通，

那么{删去栈顶位置；//从路径中删去该通道块

假设栈不空，那么重新测试新的栈顶位置，

直至找到一个可通的相邻块或出栈至栈空；

}

}

}while(栈不空)；程序如下:#include<stdio.h>

#defineWALL0//墙#defineCORRIDOR1//通道#definePATH9//为路径上的一块#defineTRIED2//#defineROW_NUM7//迷宫数组行数#defineCOL_NUM13//列数#defineTRUE1

#defineFALSE0

#defineMAXSIZE50

typedefstruct{

introw;

intcol;

}PosType;

typedefstruct{

intord;//通道块在路径上的"序号"

PosTypeseat;//通道块在迷宫中的坐标

intdi;//当前通道块的方向

}SElemType;

typedefstruct{

SElemTypeS[MAXSIZE];

inttop;

}MazeType;

//迷宫

intgrid[ROW_NUM][COL_NUM]={{1,1,1,0,1,1,1,0,0,1,1,1,1},

{1,0,1,1,1,0,1,1,1,1,1,0,1},

{1,0,0,0,0,0,1,0,1,0,1,0,1},

{1,0,0,0,1,1,1,0,1,0,1,1,1},

{1,1,1,1,1,0,0,0,0,1,0,0,0},

{0,0,0,0,1,0,0,0,0,0,0,0,0},

{0,0,0,0,1,1,1,1,1,1,1,1,1}};

//当前位置是否可以通过

boolValid(PosTypepos)

{

if(pos.row>=0&&pos.row<=ROW_NUM&&pos.col>=0&&pos.col<=COL_NUM&&grid[pos.row][pos.col]==CORRIDOR)

returnTRUE;

elsereturnFALSE;

}

voidFootPrint(PosTypepos)//留下足迹

{

grid[pos.row][pos.col]=PATH;

}

voidUndo(PosTypepos)//留下不能通过的标识

{

grid[pos.row][pos.col]=TRIED;

}

//当前位置的下一个位置

PosTypeNextPos(PosTypecur,intdi)

{

PosTypenext;

switch(di)

{

case0://东

next.row=cur.row;

next.col=cur.col+1;

break;

case1://南

next.row=cur.row+1;

next.col=cur.col;

break;

case2://西

next.row=cur.row;

next.col=cur.col-1;

break;

case3://北

next.row=cur.row-1;

next.col=cur.col;

break;

}

returnnext;

}

//是否到达终点

boolDone(PosTypecur,PosTypeend)

{

if(cur.row==end.row&&cur.col==end.col)

returnTRUE;

elsereturnFALSE;

}

//寻找迷宫路径

boolMazePath(MazeType&path,PosTypestart,PosTypeend)

{

SElemTypee;

path.top=-1;

intstep=1;

PosTypecurpos=start;

do{

if(Valid(curpos))

{

FootPrint(curpos);

e.ord=step;

e.di=0;

e.seat=curpos;

path.S[++path.top]=e;

if(Done(curpos,end))

returnTRUE;

curpos=NextPos(curpos,0);

step++;

}

else{

if(path.top>-1)//棧不空

{

e=path.S[path.top--];

while(e.di==3&&path.top>-1)

{

Undo(e.seat);

e=path.S[path.top--];

}

if(e.di<3)

{

e.di++;

path.S[++path.top]=e;

curpos=NextPos(e.seat,e.di);

}

}//if

}//else

}while(path.top>-1);

returnFALSE;

}

//输出路径

voidPrintPath(MazeTypepath)

{

inti=0;

while(i<=path.top)

{

printf("第%d步:(%d,%d)\n",path.S[i].ord,path.S[i].seat.row,path.S[i].seat.col);

i++;

}

}

//输出路径

voidPrintPath2()

{

for(inti=0;i<ROW_NUM;i++)

for(intj=0;j<COL_NUM;j++)

if(grid[i][j]==PATH)

printf("(%d,%d)\n",i,j);

}

intmain()

{

MazeTypepath;

PosTypestart={0,0},end={6,12};

if(MazePath(path,start,end))

PrintPath(path);

elseprintf("notreachable!\n");

PrintPath2();

}(3)N皇后问题:在一个N*N的棋盘上放置N个皇后，且使得每两个之间不能互相攻击，也就是使得每两个不在同一行，同一列和同一斜角线上。

对于N＝1，问题的解很简单，而且我们很容易看出对于N＝2和N＝3来说，这个问题是无解的。所让我们考虑4皇后问题并用回溯法对它求解。因为每个皇后都必须分别占据—行，我们需要做的不过是为图1棋盘上的每个皇后分配一列。

我们从空棋盘开始，然后把皇后1放到它所在行的第一个可能位置上，也就是第一行第—列。对于皇后2，在经过第一列和第二列的失败尝试之后，我们把它放在第一个可能的位置，就是格子〔2，3),位于第二行第二列的格子。这被证明是一个死胡同,因为皇后：将没有位置可放。所以，该算法进行回溯，把皇后2放在下一个可能位置(2，4)上。然后皇后3就可以放在(3，2)，这被证明是另一个死胡同。该算法然后就回溯到底，把皇后1移到(1，2)。接着皇后2到(2，4)，皇后3到(3，1)，而皇后4到(4，3)，这就是该问题的一个解。图2给出了这个查找的状态空间树。

程序如下：#include<stdio.h>

#include<math.h>

#defineN4

intcol[N+1];

//输出结果

voidOutput()

{

for(inti=1;i<=N;i++)

{

printf("(%d,%d)\n",i,col[i]);

}

printf("\n");

}

//求解函数

voidQueen(inti,intn)

{

if(i>n)

Output();

else{

for(intj=1;j<=n;++j)

{

intk=1;

col[i]=j;

while(k<i)

{

if((col[k]-col[i])*(fabs(col[k]-col[i])-fabs(k-i))!=0)

{

k++;

if(k==i)

Queen(i+1,n);

}

else{

break;

}

}

}

}

}

intmain()

{

printf("theansweris:\n");

for(inti=1;i<=N;i++)

{

col[1]=i;//设置第一行

Queen(2,N);

}

}结果如下:

(四)骑士周游问题/跳马问题跳马问题也称为骑士周游问题，是算法设计中的经典问题。其一般的问题描述是：

考虑国际象棋棋盘上某个位置的一只马，它是否可能只走63步，正好走过除起点外的其他63个位置各一次？如果有一种这样的走法，那么称所走的这条路线为一条马的周游路线。试设计一个算法找出这样一条马的周游路线。此题实际上是一个Hamilton回路问题,和迷宫问题很相似,可以用回溯算法来解决.

考虑到马在每一个位置,最多有8种跳法,如下列图所示:K7K0K6K1KK5K2K4K3可以使用N皇后问题的算法模板。

算法如下：#include

<stdio.h>

#include

<stdlib.h>

/**///棋盘行数

constint

N

=

8;

int

step[N

*

N]

=

{-1};

//保存每一步做出的选择

int

chess[N][N]

=

{0};

//棋盘

//下一个方向

int

Jump[8][2]

=

{{-2,

1},

{-1,

2},

{1,

2},

{2,

1},

{2,

-1},

{1,

-2},

{-1,

-2},

{-2,

-1}};

int

p

=

0;//对解的个数计数

//判断是否合法

int

canJump(int

x,

int

y)

{

if

(x

>=

0

&&

x

<

N

&&

y

>=

0

&&

y

<

N

&&

chess[x][y]

==

0)

return1;

return0;

}

//输出结果

void

OutPutChess()

{

int

i;

for

(i

=

1;

i

<=

N

*

N

-

1;

++i)

{

printf("%d

",

step[i]);

}

printf("\n");

for(i=0;i<N;i++)

{

for(int

j=0;j<N;j++)

printf("%3d

",chess[i][j]);

printf("\n");

}

}

//回溯算法

void

BackTrace(int

t,

int

x,

int

y)

{

if

(t

>=

N

*

N)

//if(t>=37)

{

p++;

OutPutChess();//输出结果

exit(1);

//求得一个解时,退出程序

//return;

//求得所有解

}

else{

for

(int

i

=

0;

i

<

8;

++i)

{

if

(canJump(x

+

Jump[i][0],

y

+

Jump[i][1]))

{

//求下一个结点

x

+=

Jump[i][0];

y

+=

Jump[i][1];

printf("(%2d,%2d)",x,y);//打印当结点

chess[x][y]

=

t

+

1;

step[t]

=

i;

BackTrace(t

+

1,

x,

y);//递归调用

//回溯

chess[x][y]

=

0;

x

-=

Jump[i][0];

y

-=

Jump[i][1];

}

}

}

}

/**/int

main()

{

int

x

=

0;

int

y

=

0;

chess[x][y]

=

1;

BackTrace(1,

x,

y);

printf("All

Results

Number

=

%d

",

p);

}

该算法最坏的时间复杂度为O〔8N*N〕。这是一个相当大的数字，不能接受，但实际情况好得多。并且在37步的时候，开始发生回溯,可通过改BackTrace中的第一个if中的参数发现。据说,总的回溯次数达300多百万次.

我的机子运行20分钟也没运行出结果.我们可以考虑,当N=8时,为2192,即使对于2100=1.3*1030,对于一台每秒1万亿(1012)次操作的计算机,也需要4*1010才能完成,超过了45亿年---地球的估计年龄.

但是,该算法可以适当改良,考虑到:

即向前看两步，当每准备跳一步时，设准备跳到(x,y)点，计算(x,y)这一点可能往几个方向跳〔即向前看两步〕，将这个数目设为(x,y)点的权值，将所

有可能的(x,y)按权值排序，从最小的开始，循环遍历所有可能的(x,y)，回溯求出结果。算法可以求出所有可能的马跳棋盘路径，算出一个可行的结果很快，但在要算出所有可能结果时，仍然很慢，因为最坏时间复杂度本质上并没有改变，仍为O(8^(N*N)),但实际情况很好,在瞬间即可得到一个解,当然,要求得所有解,也需要很长的时间.

下面是实现这一思想的代码：#include

<stdio.h>

#include

<stdlib.h>

/**///棋盘行数

constint

N

=

8;

int

step[N

*

N]

=

{-1};

//保存每一步做出的选择

int

chess[N][N]

=

{0};

//棋盘

int

Jump[8][2]

=

{{-2,

1},

{-1,

2},

{1,

2},

{2,

1},

{2,

-1},

{1,

-2},

{-1,

-2},

{-2,

-1}};

int

p

=

0;//对解的个数计数

//判断是否合法

int

canJump(int

x,

int

y)

{

if

(x

>=

0

&&

x

<

N

&&

y

>=

0

&&

y

<

N

&&

chess[x][y]

==

0)

return1;

return0;

}

//求权值

int

weightStep(int

x,

int

y)

{

int

count

=

0;

for

(int

i

=

0;

i

<

8;

++i)

{

if

(canJump(x

+

Jump[i][0],

y

+

Jump[i][1]))

count++;

}

return

count;

}

//权值排序

void

inssort(int

a[],

int

b[],

int

n)

{

if

(n

<=

0)

return;

for

(int

i

=

0;

i

<

n;

++i)

{

for

(int

j

=

i;

j

>

0;

--j)

{

if

(a[j]

<

a[j

-

1])

{

int

temp

=

a[j

-

1];

a[j

-

1]

=

a[j];

a[j]

=

temp;

temp

=

b[j

-

1];

b[j

-

1]

=

b[j];

b[j]

=

temp;

}

}

}

}

//输出结果

void

OutPutChess()

{

int

i;

for

(i

=

1;

i

<=

N

*

N

-

1;

++i)

{

printf("%d

",

step[i]);

}

printf("\n");