C++程序设计例解(07)
07. 有2*n个盒子排成一行，其中有两个相邻的空盒，有n-1个盒子有符号'A'，有n-1个盒子有符号'B'。例如，n=5，并有初始配置如下：
A B B A . . A B A B
试编制程序，将输入的盒子排列状态按以下交换规则将全部‘A'放到全部‘B'的左边，不管相邻两空盒的位置。交换规则是任意两个非空相邻盒子的内容可移入两个空盒中，但移动时不得变更两符号的前后次序。编写程序输入初始配置后，找出达到目标要求的最少交换次数的方案。
解：
从一种盒子排列出发，将其中两个非空相邻盒子中的内容移入空盒的每一种移动，会使盒子产生新的排列状态，采用试探法穷举所有可能的移动找问题的解。首先将盒子初始排列存入移动步聚表，然后是试探和回溯循环。循环工作内容有：检查当前排列，若当前排列是要求的最终状态，则将达到该状态的移动步聚保存，并回溯去找更少移动步数的解。在试探超 过限定的深度或当前状态的所有可能移动都已试探穷尽情况下回溯；否则对当前状态取其当前移动方法产生新的后继状态存入移动步聚表，并继续向前试探。为能从某种排列出发，通过移动产生更接近目标要求的排列，对移动方法的选取作如下规定：
。掠过无意义的来回移动；
。不把两个相邻的同为符号‘A'的盒子向后移；
。不把两个相邻的同为符号‘B'的盒子向前移；
。不把两个盒子移入到这样的位置，移入后其首尾没有一个与相邻的盒子相同。
试探回溯找解算法如下：
算法---试探回溯找解
{
输入初始排列；
初始状态存入移动步聚表；
设置其它初值；
d=0; /*当前试探深，或当前状态位置*/
do
{
if(当前状态为盒子排列的终态)
{
保存解；
记录当前解的试探深度；
回溯；
if(取尽所有可能的解)break;
}
if(试探深度超过设定值，或取尽当前状态的所有选择)
{
回溯；
if(取尽所有可能的选择)break;
}
else
{
求新状态的空盒位置；
取当前状态的移动方法和当前状态；
设定当前状态的下一个移动方法；
掠过各种不希望的方法；
生成新状态；
试探深度增1；
}
}while(1);
if(找到解)
输出解；
}
程序代码如下：
#include<stdio.h>
#include<string.h>
#define N 30
#define DEPTH 15
char b[2*N+1];
struct node
{
int empty; /*两空盒的开始位置*/
char s[2*N+1]; /*盒子排列*/
int no; /*下一个移动开始的位，或称移动方法*/
}q[DEPTH]; /*移动步聚表*/
char result[DEPTH][2*N+1]; /*存放解*/
char *s;
int best,empty,i,j,n,an,bn,sn,c,d;
void main()
{
printf("nEnter N: ");
scanf("%d",&n);
printf("Enter initial state.n"); /*输入初始状态*/
for(an=bn=sn=i=0;i<2*n;)
{
c=getchar();
if(c==' ')
{
if(sn)continue; /*强制两空白符连续出现*/
sn=1;
empty=i;
b[i++]='_';
b[i++]='_';
}
if(c=='A'||c=='a')
{
if(an==n-1)continue; /*限制A的个数*/
an++;b[i++]='A';
}
if(c=='B'||c=='b')
{
if(bn==n-1)continue; /*限制B的个数*/
bn++;b[i++]='B';
}
}
b[2*n]='';
strcpy(q[0].s,b); /*初始状态存入移动步聚表*/
q[0].empty=empty;
q[0].no=0;
best=DEPTH-1; /*设定试探深度*/
d=0;
do
{
for(s=q[d].s; *s!='B';s++);
for(;*s&&*s!='A';s++);
if(*s=='') /*当前状态为盒子排列的终态*/
{
for(j=0;j<=d;j++) /*保存解*/
strcpy(result[j],q[j].s);
best=d; /*记录当前解的试探深度*/
d--; /*回溯*/
while(d>=0&&q[d].no==2*n-1)d--;
if(d<0)break; /*取尽所有可能的选择*/
}
if(d>=best||q[d].no==2*n-1)
{
d--; /*回溯*/
while(d>=0&&q[d].no==2*n-1)d--;
if(d<0)break; /*取尽所有可能的选择*/
}
else
{
empty=q[d].empty; /*新状态的空盒位置*/
j=q[d].no++; /*取当前状态的移动方法和设定新移动方法*/
if(d>=1&&q[d-1].empty==j)continue; /*掠过来回移动*/
s=q[d].s; /*取当前状态*/
/*掠过各种不希望的移动*/
if(s[j]=='_'||s[j+1]=='_')continue;
if(j<empty&&s[j]=='A'&&s[j+1]=='A')continue;
if(j>empty&&s[j]=='B'&&s[j+1]=='B')continue;
if(empty!=0&&s[empty-1]!=s[j]&&
(empty!=2*n-2&&s[empty+2]!=s[j+1]))continue;
if(empty==0&&s[j]=='B')continue;
if(empty==2*n-2&&s[j+1]=='A')continue;
/*生成新状态*/
strcpy(q[d+1].s,q[d].s); /*形成移动后的状态*/
q[d+1].s[empty]=q[d+1].s[j];
q[d+1].s[empty+1]=q[d+1].s[j+1];
q[d+1].s[j]=q[d+1].s[j+1]='_';
q[d+1].empty=j;
for(j=0;strcmp(q[j].s,q[d+1].s);j++);
if(j<=d)continue;
q[d+1].no=0;
d++; /*试探深度增1*/
}
}while(1);
if(best!=DEPTH-1)
{
printf("nn");
for(j=0;j<=best;j++)
printf("%sn",result[j]);
}
}