C++程序设计例解(07)

07.一行有2*n个盒子，包括两个相邻的空盒子，n-1个符号为‘A’的盒子和n-1个符号为‘B’的盒子。比如n=5，初始配置如下:
a b b a..阿b阿b。

试着编译一个程序，按照下面的交换规则，把所有的‘A’放在所有‘B’的左边，不考虑相邻两个空框的位置。交换规则是任意两个非[/k0/]相邻框的内容可以移动到两个空框中，但移动时不得改变两个符号的顺序。写完程序，输入初始配置后，找出达到目标要求的最少交换次数的方案。
解法:
从一个箱子排列开始，每移动两个非空相邻箱子的内容到空箱子中的一个动作，都会使箱子有一个新的排列状态，用启发式的方法穷尽所有可能的动作来寻找问题的解。首先，将盒子的初始排列存储在移动步进表中，然后进行尝试和回溯循环。循环的工作内容是:检查当前排列，如果当前排列是所要求的最终状态，保存已经达到该状态的移动步数，回头寻找移动步数较少的解。当试验超过限定深度或当前状态的所有可能移动都已用尽时进行回溯；否则，取当前状态的当前移动方法，生成新的后续状态并存储在移动步长聚合表中，继续向前探查。为了从某个排列出发，通过移动生成更接近目标要求的排列，移动方式的选择规定如下:
。无意义地来回移动；
.不要向后移动两个带有相同符号“A”的相邻方框；
.否，将两个相邻的带有相同符号‘B’的方框向前移动；
.不会，两个盒子移到这样的位置，没有一个末端和相邻的盒子一样。
启发式回溯求解算法如下:
算法——启发式回溯求解
{
进入初始排列；
初始状态存储在移动步长聚合表中；
设置其他初始值；
d = 0；/*当前探针深度，或当前状态位置*/
do
{
if(当前状态为排盒最终状态)
{
保存解决方案；
记录当前解决方案的试验深度；
回溯；
如果(采取一切可能的解决方案)破裂；
}
if(探测深度超过设定值，或者当前状态下的所有选择都用尽)
{
回溯；
if(选择所有可能的选项)break
}
else
{
查找空框在新状态下的位置；
获取当前状态的移动方式和当前状态；
设置当前状态下的下一个移动方式；
路过各种不想要的方法；
生成新状态；