回溯算法概要.docx

回溯算法概要.docx

《回溯算法概要.docx》由会员分享，可在线阅读，更多相关《回溯算法概要.docx（23页珍藏版）》请在冰点文库上搜索。

回溯算法概要

12．7回溯算法

在生活实际中有些问题是不能用数学公式去解决的，它需要通过一个过程，此过程要经过若干个步骤才能完成，每一个步骤又分为若干种可能；同时，为了完成任务，还必须遵守一些规则，但这些规则无法用数学公式表示，对于这样一类问题，一般采用搜索的方法来解决，回溯法就是搜索算法中的一种控制策略，它能够解决许多搜索中问题。

该算法的基本思想方法是：

在搜索过程中，由于求解失败，为了摆脱当前失败状态，返回搜索步骤中的上一点，去寻求新的路径，以求得答案。

要返回搜索，那么前进中的某些状态必须保存，才能使得退回到某种状态后能继续向前。

保存状态的比较好的方法，采用一种叫“栈”的数据存放方式，即将前进中的状态象“栈”一样一层层堆放，取出时从最上层一一取出。

本节中重点介绍用数组实现栈的功能，存放前边进中的状态。

所以回溯算法特点：

（1）搜索策略：

符合递归算法，问题解决可以化为子问题，其子问题算法与原问题相同，只是数据增大或减少；

（2）控制策略：

为了避免不必要穷举搜索，对在搜索过程中所遇到的失败，采取从失败点返回到上一点，进行重新搜索，求得新的求解路径。

（3）数据结构：

用数组保存搜索过程中的状态、路径。

假设回溯算法是要找出问题的所有答案（x1,x2,x3,……，xn）,对于每个答案都有一个由根结点（开始位置）到终点（所要到达结点）的路径设为T；另外假定存在一些规则设为B，则其回溯算法的一般形式是：

procedurebacktrack（n）；{回溯算法的抽象模式，每个解在x（1..n）中}

k←1

whilek>0do

begin

if还有没检验过的x（k）且

x（k）是其中可能一个解and满足规则B，

then

if存在由根结点到x（k）是一条到达答案结点的路径then

输出x

（1）,x

（2）,……x（k）路径endif

k←k+1

elsek←k-1{回溯到前一个位置}

Endif

End；

End；

下面介绍一些典型的回溯算法问题。

[例12-27]有2n个人排队购一件价为0.5元的商品，其中一半人拿一张1元人民币，另一半人拿一张0.5元的人民币，要使售货员在售货中，不发生找钱困难，问这2n个人应该如何排队？

找出所有排队的方案。

（售货员一开始就没有准备零钱）

分析：

（1）根据题意可以看出，要使售货员在售货中，不发生找钱困难，则在排队中，应该是任何情况下，持0.5元的排在前面的人数多于持1元的人数。

（2）该问题可以用二进制数表示：

用0表示持0.5元的人，用1表示持1元的人，那么2n个人排队问题化为2n个0、1的排列问题。

这里我们用数组B[1..2n]存放持币情况。

（3）设k是B数组下标指针，B[K]=0或B[K]=1，另用数组d[0]、d[1]记录0与1的个数，且必须满足：

n>d[0]>=d[1]。

（4）算法：

回溯搜索。

（a）先将B[1]、B[2]、……B[2n]置-1，从第一个元素开始搜索，每个元素先取0，再取1，即B[K]+1→B[K]，试探新的值，若符合规则，增加一个新元素；

（b）若k<2n，则k+1→k，试探下一个元素，若k=2n则输出B[1]、B[2]……，B[2n]。

（c）如果B[K]的值不符合要求，则B[K]再加1，试探新的值，若B[K]=2，表示第k个元素的所有值都搜索过，均不符合条件，只能返回到上一个元素B[K-1]，即回溯。

（d）返回到上一个元素k：

=k-1，并修改D[0]、D[1]。

（5）直到求出所有解。

程序如下：

Programp12_27；

Constmax=100；

Varb：

array[1．．2*max]of-1．．2；

D：

array[0．．1]of0．．max；

Done：

Boolean；

Total,n,k：

integer；

Procedureprint；{输出一组解}

Varx：

integer

Begin

Inc（total）；

Write（‘No．’,total,’：

’）；

Forx：

=1to2*ndowrite（b[x]：

2）；

Writeln；

End；

Begin{主程序}

Write（‘n=’）；

Readln（n）；

Fork：

=1to2*ndob[k]：

=-1；初始化程序段

Total：

=0；k：

=1；d[0]：

=0；d[1]：

=0；

Repeat

Repeat{按照问题的要求，产生一组数或回溯到上一个元素}

Done：

=false；

Inc（b[k]）；

If（b[k]=0）and（d[0]

Inc（d[0]）；Done：

=true；

End；

If（b[k]=1）and（d[1]

Ifd[0]>=nthenbegin

Dec（d[0]）；Inc（d[1]）；

Done：

=true；

End

Elsebegin

Inc（d[1]）；Done：

=true；

End；

Untildoneor（b[k]=2）；

Ifdonethen

if（k=2*n）and（d[0]=d[1]）thenprint{一组数满足要求，则输出}

elseinc（k）{k<2n}

Elsebegin{如果b[k]=2，则表示第k个元素所有值已经试探过，均不符合条件，回溯}

Dec（d[1]）；{修改值}

B[k]：

=-1；{重新赋初值}

Dec（k）；{返回上一个点}

End；

Untilk=0；

Writeln；

End．

程序执行后的结果：

输出：

n=3（输入）

输出：

No．1：

000111

No．2：

001011

No．3：

001101

No．4：

010011

No．5：

010101

下面是n=3时产生第一个解以及从第一个解最后一位开始回溯到产生第二个解的情况，以帮助读者理解回溯算法的实际含义：

k123456

0

0

0

1

1

1

1

2

3

3

3

3

0

0

0

1

2

3

B[k]

第一个解000111

（1）

D[0]

D[1]

k123456

0

0

0

1

1

2

1

2

3

3

3

3

0

0

0

1

2

3

B[k]

B[6]加1，需要回溯

（2）

D[0]

D[1]

k123456

0

0

0

1

2

-1

1

2

3

3

3

0

0

0

1

2

回溯，k=5,B[5]加1，再回溯

（3）

B[k]

D[0]

D[1]

k123456

0

0

0

2

-1

-1

1

2

3

3

0

0

0

1

B[k]

回溯k=4，B[4]加1，

再回溯

（4）

D[0]

D[1]

k123456

0

0

1

-1

-1

-1

1

2

2

0

0

1

B[k]

回溯k=3,B[3]加1

（5）

D[0]

D[1]

k123456

0

0

1

0

-1

-1

1

2

2

3

0

0

1

1

B[k]

K加1，k=4,B[4]加1

（6）

D[0]

D[1]

k123456

0

0

1

0

1

-1

1

2

2

3

3

0

0

1

1

2

K=5,B[5]加1，D[0]≥3

B[5]再加1

（7）

B[k]

D[0]

D[1]

k123456

0

0

1

0

1

1

1

2

2

3

3

3

0

0

1

1

2

3

K=6,B[6]加1，d[0]≥3

B[6]再加1，得到第二个解001011

（8）

B[k]

D[0]

D[1]

由本例题的回溯算法的描述，可以知道回溯算法中经常用数组（如B数组）作为一个栈，记录访问过的点，用数组下标（如K）作为栈指针，表示搜索的进程（路径）。

栈的后进先出的操作规则，恰好符合回溯的后产生的点先回溯的特点。

所以回溯算法中经常用数组这样的数据结构存储操作过程。

针对本题的特殊性，还可以有其他更简便的方法，请读者自己设计完成。

　　[例12-28]骑士游历问题：

　　在　n×n　的国际象棋上的某一位置上放置一个马，然后采用象棋中“马走日字”的规则，要求这个马能不重复地走完n×n个格子，试用计算机解决这个问题。

图12-3

分析：

本题是典型的回溯算法问题，设骑士在某一位置，设（X,Y），按规则走，下一步可以是如图12-3（n=5）所示的8个位置之一。

　　我们将重点考虑前进的方向：

如果某一步可继续走下去，就试探着走下去且考虑下一步的走法，若走不通则返回，考虑另选一个位置，其算法是：

　　procedure试探下一步；

begin

选择准备；

repeat

８个位置中选一个；

　　　　　if选择可接受then

begin

记录移动情况；

if棋盘未遍历完then

begin

试探下一步；

if试探不成功then删去以前的记录{回溯}

end

end

until（移动成功）or（再无别的选择）

end；

该题是一种典型回溯算法，马走的路径可以用二维数组表示：

横向和纵向，其走的方向有8种可能，用数组表示某点所对应的8个方向的坐标。

constn=8；nsq=64；

typeindex=1..n；

vari,j：

index；

g：

boolean；

b：

array[1..n,1..n]ofinteger；

我们约定

b[i,j]＝0当棋格（i,j）未被占据

=k当棋格（i,j）在第K次移动中被占据

用数组B记录移动的情况，当可以走通时则b[i1,j1]：

=i；若走不通需删除以前记录时则b[i1,j1]：

=0。

用K表示当前进行的方向，选下一个位置就是改变下标值：

设当前下标为（X,Y）→（U1,V1）其关系是U1=X-1,V1=Y+2；（X,Y）→（U2,V2）有关系是U2=X-2,V2=Y+1等,用坐标增量来表示移动情况。

　　程序如下：

Programp12_28；

　　constn=8；nsq=64；

typeindex=1..n；

vari,j：

index；

g：

boolean；

a：

array[1..2,1..n]ofinteger；{棋子移动时，坐标变化}

b：

array[1..n,1..n]ofinteger；

proceduretry（x,y：

index；i：

integer；varq：

boolean）；

vark,u,v：

integer；

q1：

boolean；

begin

k：

=0；

repeat

k：

=k+1；{第k个方向（8个方向）}

q1：

=false；

u：

=x+a[1,k]；{确定跳马的位置}

v：

=y+a[2,k]；

if（1<=u）and（u<=8）and（1=v）and（v<=8）

then

ifb[u,v]=0then{没有走过的空格位}

begin

b[u,v]：

=i；｛第i步在u,v处放置棋子｝

ifi

begin

try（u,v,i+1,q1）；{继续走下一步棋：

i+1}

ifnotq1thenb[u,v]：

=0；

｛不成功,退回，将已经填入的值清0｝

end

elseq1：

=true；

end；

untilq1or（k=8）；

q：

=q1；

end；

BEGIN{主程序}

a[1,1]：

=-1；a[2,1]：

=2；{８个方向的坐标增量　}

a[1,2]：

=-2；a[2,2]：

=1；

a[1,3]：

=-2；a[2,3]：

=-1；

a[1,4]：

=-1；a[2,4]：

=-2；

a[1,5]：

=1；a[2,5]：

=-2；

a[1,6]：

=2；a[2,6]：

=-1；

a[1,7]：

=2；a[2,7]：

=1；

a[1,8]：

=1；a[2,8]：

=2；

fori：

=1tondo

forj：

=1tondo

b[i,j]：

=0；

b[1,1]：

=1；{初始化棋子位置，并且开始搜索}

try（1,1,2,q）；{递归调用走棋子过程}

ifqthen{如果棋子走遍每个格子，q为真，则输出跳马过程}

fori：

=1tondo

begin

forj：

=1tondo

write（b[i,j]：

5）；

writeln；

end

elsewriteln（'nosolution'）；

END.

运行结果是：

[例12-29]四色问题。

设有如图12-4的地图，每个区域代表一个省，区域中的数字表示省的编号，现在要求给每个省涂上红、蓝、黄、白四种颜色之一，同时使相邻的省份以不同的颜色区分。

图12-4图12-5

分析：

（1）本题是图论中的一个搜索问题，我们可以将该问题简化：

将每个省看着一个点，而将省之间的联系看作一条边，可以得到如图12-5所示图形。

（2）从图12-5可以知道各省之间的相邻关系，我们可以数据阵列表示——矩阵，即用一个二维数组来表示：

R[x，y]=1表示省x与省y相邻

0表示省x与省y不相邻

由图12-5可以得到如下矩阵

1234567

1

0

1

0

0

0

0

1

2

1

0

1

1

1

1

1

3

0

1

0

1

0

0

0

4

0

1

1

0

1

0

0

5

0

1

0

1

0

1

0

6

0

1

0

0

1

0

1

7

1

1

0

0

0

1

0

（3）从编号为1的省开始按四种颜色顺序填色，当第一个省颜色与相邻省颜色不同时，就可以确定第一个省的颜色，然后，再依次对第二、第三，……，进行处理，直到所有省份颜色都涂上为止。

（4）问题关键在于在填色过程中，如果即将填的颜色与相邻省的颜色相同，而且四种颜色都试探过，均不能满足要求，则需要回溯到上一个点（即前一个省），修改上一个省的颜色，重新试探下一个省的颜色。

所以本题仍然是一个用回溯方法求问题的解。

其基本算法是：

用数组S表示某个省已涂的颜色，涂色过程算法如下：

Procedure涂色过程；

Begin

初始化工作；

对第一个省涂色

Whilex<=ndo{还有省份没有涂色}

While（y<=4）and（x<=n）do{选择颜色}

Begin

Ifk

试探下一区：

k+1→K

If当前颜色不能涂，then试探下一种颜色：

y+1→y

Else本区域涂色，准备试探下一区域

If试探不成功then{回溯}

x-1→x{返回上一个点（省）}

修正y颜色的值

end；

end；

在上面算法中，如何检测相邻区域是否涂色以及涂什么颜色的计算机表示方法：

S数组表示某区域所涂的颜色，R数组表示省之间的关联，用0，1表示，因此检查相邻区域是否涂色或涂的颜色是否相同用：

s[k]*R[x,k]<>x表示。

完整程序如下：

Programp12_29；

Constmax=100；

VarR：

array[1..max,1..max]of0..1；

S：

array[1..max]ofinteger；

N,a,b：

integer；

Proceduremapcolor；

Varx,y,k：

integer；

Begin

S[1]：

=1；x：

=2；y：

=1；{初始化}

Whilex<=ndo

While（y<=4）and（x<=n）do

Begin

K：

=1；

While（ky）dok：

=k+1；

Ifk

=y+1{试探下一种颜色}

Elsebegin

S[x]：

=y；{给本区涂y颜色}

X：

=x+1；{准备试探下一个区域}

Y：

=1；{颜色重新赋值}

End；

Ify>4thenbegin{回溯到上一个省}

X：

=x-1；

Y：

=s[x]+1；{修正颜色值}

End；

End；{whiley}

End；{过程结束}

Begin

Write（‘n=‘）；

Readln（n）；

Fora：

=1tondo{输入省之间关联}

Forb：

=1tondo

Read（R[a,b]）；

Readln；

Fora：

=1tondo{输出关联矩阵}

Begin

Forb：

=1tondo

write（R[a,b]）；

writeln；

End；

Mapcolor；{调用涂色过程}

Fora：

=1tondo{输出解}

Writeln（x：

5,’：

’,s[x]：

5）；

End.

程序运行结果

当输入数据矩阵，计算机输出数据矩阵，并输出

1：

1

2：

2

3：

1

4：

3

5：

1

6：

3

7：

4

例题12-30在n*n的棋盘上（1<=n<=10）填入1，2，3，……，n*n,共有n*n个数，使得任意两个相邻数的和为素数。

1

2

4

3

例如：

当n=2时，有：

当n=4时，一种可以填写的方案如下表，在这里我们约定：

左上角的格子里必须填数字1。

程序要求：

输入n；输出：

有多个解，则输出第一行、第一列之和为最小的排列方案；若无解，则输出“NO！

”

1

2

11

12

16

15

8

5

13

4

9

14

6

7

10

3

分析：

（1）从问题可以看出这是一个搜索问题，程序中必须完成判断相邻两个数的和是否是素数的任务。

（2）如果一边填数，一边求和及判断素数，程序运行速度将大大减慢，所以我们可以采用数组结构，将2～n*n之间所有素数存放在一个数组中。

由于问题中指出n<=10，所以，最大的相邻两个数的和是：

99+100<200。

我们只需要将2～200之间的素数存放在数组中就可以了。

（3）按行、列填入数据，并求相邻两个数的和，将其与素数数组比较，若是素数，则当前格可以填数，继续填数。

若当前格没有数据可以填，则要回溯到上一格，重新填写上一格数据，再进行判断。

数据结构：

（1）用一个布尔数组T表示1～n*n之间的数是否用过，false表示没有用过，true表示已经用过。

（2）用一个二维数组A，存放棋盘格子上填数的状态，其中A[1，1]=1。

（3）用一个数组下标指针，表明递归调用层次和回溯的层次。

算法如下：

procedure填数过程；

begin

初始化工作；

对第一格填数：

A[1，1]=1；

WhileK<=n*ndo{还有空格没有填数}

Begin

If（第K个数未用过）and（相邻数的和是素数）then

将数据填入格子内，且设置为已填过此数（真）；

准备试探下一个空格

If当前数据不能填then试探下一个数据

If试探不成功then{回溯或退栈返回前一个格子}

Dep:

=dep-1

重新填数

end；

end;

程序如下：

Programp12_30；

Constmax=10；

Typearr=array[1．．2*max*max]ofBoolean；

VarI,j,k,m,n,x,y：

integer；

T：

arr；

A：

array[1..max,1..max]ofinteger；

H：

array[1..max*max]ofBoolean；

Functionsuccess（x,y,k：

integer）：

Boolean；{

Begin{相邻数之和是否是素数}

Success：

=true；

Ifx>1thenifnot（T[a[x-1,y]+k]）thensuccess：

=false；

Ify>1thenifnot（T[a[x,y-1]+k]）thensuccess：

=false；

End；

Procedureprint；{输出数据阵列}

Varx,y：

integer；

Begin

Forx：

=1tondo

Begin

Fory：

=1tondowrite（a[x,y]）：

4）；

Writeln;

End;

End;

ProcedureTTT（x,y,dep：

integer）；{递归}

Var