魔板优化(基于树剪枝的优化)

问题解释

魔板由8个大小相同方块组成,分别用涂上不同颜色,用1到8的数字表示。

其初始状态是

1 2 3 4
8 7 6 5

对魔板可进行三种基本操作A操作(上下行互换):

8 7 6 5
1 2 3 4

B操作(每次以行循环右移一个):

4 1 2 3
5 8 7 6

C操作(中间四小块顺时针转一格):

1 7 2 4
8 6 3 5

用上述三种基本操作,可将任一种状态装换成另一种状态。

额外且是最关键的要求是,从初始状态转换到最终状态的步数大于10,这太关键了,必须重视这一点。

算法思想及解题用到的主要数据结构

算法思想:队列向前搜索的算法思想,在队尾持续加入新状态,在队头移除已经处理过的旧状态,不停地进行这一步,最终我们可以搜索到满足要求的新状态。

主要数据结构:构造一颗三叉树,

只要这颗三叉树一直往下生长,如果问题有解,我们就一定能找到解(不考虑时间和空间复杂度)。具体的实现是用一个队列记录三叉树的结点。

详细解题思路

1.我们使用2个整数来代表魔板,上边为一个四位数,下面也是一个四位数。

2.我们做的第一件事情是,检查,如果2个整数一开始就是目标函数,或者说题目测试样例中给出的步数是0,那么就跳过队列搜索过程而前往最终输出处,毕竟这种情况下没必要浪费资源。

3.如果没能够跳过队列搜索,那么我们只能规规矩矩地进行三叉树的构造,先是A操作,将其结果加入队尾,再进行B操作,加入队尾,C操作,也加入队尾,而后就弹出队头,不断向前。在这个过程中,我们可能遇到两种情况,一是我们找到了答案,二是步数超出限制,这两种情况里,我们不管遇到哪一种,都要停下来。

4.一旦队列搜索停下来了,我们就可以输出了,如果队尾是答案(每往队尾插入一个新状态,我们都检测是否找到答案,是否该停),输出具体解,如果不是,输出-1即可。

5.ABC三种操作的具体实现,都是求商求模的算法,用数学的方法,修改两个4位数的各位数位置。

6.至于超时超内存,这是个值得认真考虑的问题。如果我们不进行剪枝,进行90步,将有3的90次方个状态,这是个超级计算机都无法求解的算法!如果我们进行剪枝,但剪枝的思路却是“每次加入新状态时,遍历所有已有的状态,查看是否重复”,这样将极大浪费时间,每次插入前都比较8!次,耗时不是一般的大。所以我们的结论是:必须剪枝,但剪枝需要极高效的算法。我先后考虑了康托展开hash和求模hash,发现都不是很好用,回想起c++语言的STL里set自带了红黑树构造,插入和查询还算可以,如果套用上去,将非常perfect。

为了方便,我把两个4位数进一步处理,得到一个8位数(上边的处高位,下边的处低位)

逐步求精算法描述(含过程及变量说明)

qt节点,抽象三叉树的节点,也就是队列的节点,存放状态、操作符、从根节点到目前节点的所有操作符。

qm队列,存放所有的状态。

xy set,协助剪枝,将数据插入其中失败表明该数据已经在set中。

整数xx,yy,m,n,分别是目标魔板的2个四位数和当前魔板的2个四位数。

flag,标记是否可以继续搜索。

四个过程

Add:将某操作符得到的状态封入qt节点中,并加入qm队尾,如果已经找到解,则令flag为false。

A:如果没找到解,则对qm队列队头状态求出A操作相应的状态,并检测能否插入set中,如果可以,就调用Add,将新得到的状态插入qm队列。

B:如果没找到解,则对qm队列队头状态求出B操作相应的状态,并检测能否插入set中,如果可以,就调用Add,将新得到的状态插入qm队列。

C:如果没找到解,则对qm队列队头状态求出C操作相应的状态,并检测能否插入set中,如果可以,就调用Add,将新得到的状态插入qm队列。

Type qt=record

x,y:integer;

op:char;

pre:string;

end;

Var

…,m,n,xx,yy:integer;

qm:queue of qt;

xy:set of integer;

flag:boolean;

A操作(结果存入m,n变量中)

If(!flag) then return;

m:=qm.front().y; n=qm.front().x;

If(xy.insert(m * 10000 + n).second) then Add(‘A’);

B操作


If(!flag) then return;

m:=(qm.front().x mod 10) *1000+(qm.front().x div 10)

n:=(qm.front().y mod 10) *1000+(qm.front().y div 10)

If(xy.insert(m * 10000 + n).second) then Add(‘B’);

C操作

If(!flag) then return;

i:=(qm.front().x div 1000)*1000;

j:=qm.front().x-i; a:=j div 100;

b:=(j-a*100)div 10;

i1:=(qm.front().y div 1000)*1000;

j1:=qm.front().y-i1;

c:=j1 div 100;

d:=(j1-c*100)div 10;

m:=i+c*100+a*10+(qm.front().x mod 10);

n:=i1+d*100+b*10+(qm.front().y mod 10);

If(xy.insert(m * 10000 + n).second) then Add(‘C’);

Add操作

qm.push(qt(m, n, opx, qm.front().pre + opx));

if(m == xx && n == yy) then flag = false;

程序注释清单


#include

#include

#include

#include

#include

struct qt
{
int x, y;
char op;
std::string pre;
qt(int xx, int yy, char opop, std::string prepre) {
x = xx;
y = yy;
op = opop;
pre = prepre;
}
qt() {
x = 0;
y = 0;
op = 0;
pre = “”;
}
}; // 队列节点

std::queue qm;
std::set xy;
int xx, yy, m, n;
bool flag;

void Add(char opx) {
qm.push(qt(m, n, opx, qm.front().pre + opx));
if (m == xx && n == yy)
{
flag = false;
}
}

void A() {
if (!flag)
{
return;
}

m = qm.front().y;
n = qm.front().x;

// m = (qm.front().x % 100) 100 + (qm.front().x / 100);
// n = (qm.front().y % 100)
100 + (qm.front().y / 100);
if (xy.insert(m * 10000 + n).second)
{
Add(‘A’);
}
}

void B() {
if (!flag)
{
return;
}
m = (qm.front().x % 10) 1000 + (qm.front().x / 10);
n = (qm.front().y % 10)
1000 + (qm.front().y / 10);

// m = (qm.front().x % 1000) 10 + (qm.front().x / 1000);
// n = (qm.front().y % 1000)
10 + (qm.front().y / 1000);
if (xy.insert(m * 10000 + n).second)
{
Add(‘B’);
}
}

void C() {
if (!flag)
{
return;
}
int i = (qm.front().x / 1000) 1000;
int j = qm.front().x - i;
int a = j / 100;
int b = (j - a
100) / 10;
int i1 = (qm.front().y / 1000) 1000;
int j1 = qm.front().y - i1;
int c = j1 / 100;
int d = (j1 - c
100) / 10;
m = i + c 100 + a 10 + (qm.front().x % 10);
n = i1 + d 100 + b 10 + (qm.front().y % 10);

if (xy.insert(m * 10000 + n).second)
{
Add(‘C’);
}
}

int main() {
int N;
std::cin >> N;
//N = 4;
while (N != -1)
{
while (!qm.empty())
{
qm.pop();
}
xy.clear();

int a, b, c, d;
std::cin >> a >> b >> c >> d;
xx = a * 1000 + b * 100 + c * 10 + d;
//xx = 4123;
std::cin >> a >> b >> c >> d;
yy = a * 1000 + b * 100 + c * 10 + d;
//yy = 8567;

m = 0;
n = 0;

// 如果初始状态就是解,或者步数为0
if (xx == 1234 && yy == 8765 || N == 0)
{
  flag = false;
}
else
{
  flag = true;
}

qm.push(qt(1234, 8765, 'x', ""));
// 把两个4位数进一步处理,得到一个8位数(上边的处高位,下边的处低位)
xy.insert(1234 * 10000 + 8765);

/**
 * 如果没能够跳过队列搜索,那么我们只能规规矩矩地进行三叉树的构造
 * ,先是A操作,将其结果加入队尾,再进行B操作,加入队尾,C操作,也
 * 加入队尾,而后就弹出队头,不断向前。在这个过程中,我们可能遇到
 * 两种情况,一是我们找到了答案,二是步数超出限制,这两种情况里,
 * 我们不管遇到哪一种,都要停下来。
 */
while (flag && !qm.empty())
{
  A();
  B();
  C();
  qm.pop();
  // 步数超出限制
  if (qm.back().pre.size() > N)
  {
    flag = false;
    break;
  }
}

/**
 * 如果队尾是答案(每往队尾插入一个新状态,我们都检测是否找到答案
 * ,是否该停),输出具体解,如果不是,输出-1即可。
 */
if (qm.back().x == xx && qm.back().y == yy)
{
  if (qm.back().pre.size() > 0)
  {
    std::cout << qm.back().pre.size() << " " << qm.back().pre << "\n";
  }
  else
  {
    std::cout << "0\n";
  }
}
else
{
  std::cout << "-1\n"; } std::cin >> N;

}

return 0;
}


测试数据

分析与改进

本程序里,占用时间和空间最多的,莫过于剪枝所用的set。

时间复杂度:Set的底层使用了红黑树,红黑树的特点的插入有时挺慢的(为了挪动相应的数据),但查询极快,时间复杂度是lg(N),但是,set的插入性能有时却不好(尤其是本题这种数据间并无序的例子),为了平衡红黑树,需要调整一些数据,所以,在插入的时候,将会占用极大量的时间。但是,如果步数比较少,那使用set是很值的,因为需要做的调整比较少,费时少,但是如果步数比较多,插入的时间复杂度又将极大增加,这是个值得取舍的问题。

空间复杂度:因为set使用了红黑树,占用的存储空间会稍微大一些(为了存储节点信息)。

优化思路:正所谓,天底下没有最优算法,只有更合适的算法。没有哪种算法是最好的,也没有哪种数据结构是最好的,我们需要根据实际情况选取不同的算法和数据结构。在本题目中,如果步数仅大于10且接近于10,那么速度将极快,但是步数接近20的时候,就超时了。所以,为了处理步数接近100的例子,只能够更换另外的算法了,这里考虑康托展开。

但是实际操作中,针对测试用例34125687,康托展开的时间复杂度和我的算法的时间复杂度差不多,优点是内存占用减少50%。