Dylan 收录于 OI

2017-09-30 2023-03-31 约 3300 字预计阅读 7 分钟 - 次阅读 - 条评论

也谈八数码境界

题意

给定一个九宫格起始状态，其中八格放置1~8，有一格为空。空格可以和毗邻的格子交换，一次交换称为一次操作，求达到目标状态所需的最小字典序的最少操作次数及方案。

第一重：BFS+STL

略。

第二重：BFS+CantorHash

Cantor

对所有1~n的排列按字典序进行排序得到一个序列，那么任意一个排列都可以找到在这个序列中的位置（或者说排名），而且这个排名是一一对应的。所以一个排名可以唯一确定一个排列，那么在有关排列的问题里我们就可以利用排名来判重，而不是记下排列中所有的数。 Cantor提供了快速的实现由给定排列计算排名，以及由排名确定排列的方法，称为康托展开。

康托展开

给定一个1~n的排列，求其在所有排列中的排名。

思路

求该排列之前有多少比他小的排列，然后加一。

做法

从左到右枚举该排列的每一个数a[i] s=在该排列中以x开头的后缀,a[i->n] len=len(s) cnt=s中比a[i]小的数的个数 ans+=cnt*(len-1)!

原理

对于每一位，前面的数字已经用过而且固定了，那么这时比它小的排列就是将当前排列的当前位置换成小一点的数，然后将后面的剩余可用的数换来换去的全排列个数。

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int ans;
void cantor()
{
 int sum=0;
  for(int i=1;i<=n;++i)
  {
       int cnt=0;
       for(int j=i+1;j<=n;++j)
           if(a[j]<a[i])++cnt;
      sum+=cnt*fac[n-i];
   }
   ans=sum+1;
}

逆康托展开

就是康托展开的逆过程。主要思路是用排列的个数不断逼近已知的排名。

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool used[maxn];
void recantor(int cant)
{
​    --cant;//!!!
​    for(int i=1;i<=n;++i)
​    {
​        int k=cant/fac[n-i];
​        cant%=fac[n-i];
​        for(int j=1,cnt=0;j<=n;++j)
​        {
​            if(!used[j])
​            {
​                ++cnt;
​                if(cnt==k+1)
​                {
​                    b[i]=j;
​                    used[j]=true;
​                    break;
​                }
​            }
​        }
​    }
}

第三重：BFS+CantorHash+打表/逆序对

有些情况从起始状态是无法到达目标状态的，那么如果我们在刚开始就知道不可行，势必会有较好的效率提升。这里提供两种方法。

打表

对于目标状态确定的多组数据，并且不要求输出方案的八数码题目，我们可以采取从目标状态出发反着搜索，将所有能到达的点的最少步数记录下来。这样所有能到达目标状态的状态一定会有记录，如果没有记录的就是无法到达的状态。

逆序对

对八数码移动过程进行分析如下：假设当前处于如表所示状态：

b1	b2	b3
b4	0	b5
b6	b7	b8
其中0表示空白格。
那么这样的状态展开后可以表示为：b1,b2,b3,b4,0,b5,b6,b7,b8。
如果简单地定义逆序对为无序对(I,j)满足i<j且b[i]>b[j]
并且0不计算在内，那么接下来考虑四种移动方向。
向左向右：由于0不计算，所以没有影响
向上：b1,0,b3,b4,b2,b5,b6,b7,b8
可以看出只有与2有关的逆序对发生了改变，即(b2,b3),(b2,b4)的逆序对状态发生了改变。
有四种情况：
逆序对变化	(b2,b3)是逆序对	(b2,b3)不是逆序对
—————–	—————	—————–
(b2,b4)是逆序对	-1-1=-2	+1-1=0
(b2,b4)不是逆序对	-1+1=0	+1+1=2
所以逆序对数在操作前后奇偶性是不变的。
所以对于起始状态和目标状态逆序对数奇偶性不同的情况，从起始状态是一定不能到达目标状态的，可以直接输出unsolvable。
实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int getre()
{
    int re=0;
    for(int i=1;i<=9;++i)
    {
        if(b[i])
        for(int j=i+1;j<=9;++j)
            if(b[j]&&b[i]>b[j])++re;
    }
    return re;
}

第四重：双向广搜+CantorHash

略

第五重：A*（不同数字数目）+CantorHash

略

第六重：A*（曼哈顿距离）+CantorHash

A*

以下为个人见解，很不严谨，仅供参考。 A*算法是搜索算法的一种。它通过一种称为 “启发式”的策略来加速搜索的过程。所谓启发式，就是在面临许多选择时选择看起来最好的那个先搜索。这样做可以减少许多不必要的盲目乱撞。

公式

f(n)=g(n)+h(n) 其中： f(n)表示从状态n到目标状态的估计花费， g(n)表示从起始状态到状态n的实际花费， h(n)表示从状态n到目标状态的估计花费。

g(n)是我们搜索到达状态n所实际记录的花费，而h(n)则取决于我们的选择，也是一个启发式搜索算法优劣的重要因素。

做法

在得出每个相邻状态的f(n)时，我们选择f(n)最小的状态优先搜索。设gt为从状态n到达目标状态的实际花费，则h(n)与gt的差距越小，对花费的估计越准确，搜索范围越小，效率越高。

表

在A*的搜索过程中设立了两个表：Open表和Closed表。其中Open表记录所有已经生成而未访问的状态， Closed表记录所有访问过且不会再访问的节点。

过程

从一个状态开始，找出与它相邻的状态并加入Open表中，然后选择Open表中f(n)最小的状态继续搜索。直到目标节点被加入Closed表。（有些文章说搜到目标节点就结束？） Closed表的操作略。

应用

对于每个方格中的数字，令dis=它在目标状态中的位置与当前位置的曼哈顿距离。用sumdis表示对每个数字的dis累加（0除外），然后我们就可以利用这个值作为A*的启发函数。

第七重：A*（曼哈顿距离+堆）+CantorHash

在A*在过程中，我们每次要找到Open表中f(n)最小的节点。如果不加任何优化而是直接枚举比较的话，效率会比较低。所以对于这样的子问题，我们可以选择用堆来维护Open表，每次取出f(n)值最小的先计算。

第八重：IDA*（曼哈顿距离）

IDA*，即迭代加深的A*。不同于上面的A基于BFS，IDA基于DFS。

主要思想

每次限定一个搜索的最大步数，每次搜索时判断到达目标节点的预估距离：如果大于限制则跳出。如果一个限制步数搜索完毕还没有搜到目标状态，则加大限制步数继续搜索。这也是其称为迭代加深搜索的原因

优势

不需要康托展开哈希，也不需要用堆或者其他麻烦的东西，代码实现简练。而且由于对搜索深度进行了限制，效率比较高。

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
bool ok;
int limit;
char tmp[maxn];
char ans[maxn];
void dfs(int dep)
{
​    if(now.getsumDis()==0)
​    {
​        tmp[dep]=0;
​        for(int i=1;i<=dep;++i)
​            ans[i-1]=tmp[i];
​        ok=true;
​        return;
​    }
​
​    int tdis=now.getsumDis();
​    if(tdis+dep-1>limit||ok)return;
​    for(int ii=1;ii<=4&&!ok;++ii)
​    {
​        int i=order[ii];
​        if(tmp[dep-1]!=(dir[redir[i]]))
​        if(now.cango(i))
​        {
​            now.move(i);
​            tmp[dep]=dir[i];
​            dfs(dep+1);
​            tmp[dep]=0;
​            now.move(redir[i]);
​        }
​    }
}
void IDAstar()
{
​    ok=false;
​    now=s;
​    for(limit=s.getsumDis();!ok;++limit)
​    {
​        dfs(1);
​    }
}

优化1

由于limit每次增大的步长为1，所以在DFS中dep!=limit+1的情况下一定是找不到解的，所以可以不用每次都判断now.getsumDis()==0，而是在搜到最后一层，即dep==limit+1的时候再判断。这样可以节约许多时间。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void dfs(int dep)
{
​    if(dep==limit+1)
​    {
​        if(now.getsumDis()==0)
​        {
​            tmp[dep]=0;
​            for(int i=1;i<=dep;++i)
​                ans[i-1]=tmp[i];
​            ok=true;
​            return;
​        }
​    }
​    else
​    {
​        int tdis=now.getsumDis();
​        if(tdis+dep-1>limit||ok)return;
​        for(int ii=1;ii<=4&&!ok;++ii)
​        {
​            int i=order[ii];
​            if(tmp[dep-1]!=(dir[redir[i]]))
​            if(now.cango(i))
​            {
​                now.move(i);
​                tmp[dep]=dir[i];
​                dfs(dep+1);
​                tmp[dep]=0;
​                now.move(redir[i]);
​            }
​        }
​    }
}

优化2

其实可以让limit增大的步长变长一些。采取的策略是，计算每次搜索能够得到的距离目标状态最小的预估步数mindis，如果当前限制步数不能搜到，那么令limit+=mindis。但是这个优化有几个注意的地方：

 不能使用优化1。因为可能存在这样一种情况：某状态A到目标的实际步数为a，在限制步数为lim时，A的预估步数为b>a，且g(A)<lim，b+g(A)>lim，这时A就不会被继续搜索下去。

假设lim时得到的最小预估步数为c，c>a，那么下一次的lim’=lim+c。如果使用了优化1，那么只有在dep=lim+c+1的时候会判断是否达到目标状态，可是从状态A到达目标状态的步数g(aim)=g(A)+a<lim+c=lim，所以状态A的分支即使到达了终点也不会被判断，不亦悲乎？ 2. 对于求最小步数的问题该优化不适用。由于和“不能用优化1”同样的原因，限制步数为lim’时，真正到达终点的步数可能是lim+1~lim’这一段区间的某个值，或者某些值。而这里使用的是DFS，就可能导致步数大的先被搜到而退出。

所以对于没有上述要求的题目，比如输出任意一组方案，那么优化2还是有较好效果的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
bool ok;
int limit;
int mindis;
char tmp[maxn];
char ans[maxn];
void dfs(int dep)
{
​    if(now.getsumDis()==0)
​    {
​        tmp[dep]=0;
​        for(int i=1;i<=dep;++i)
​            ans[i-1]=tmp[i];
​        ok=true;
​        return;
​    }
​    int tdis=now.getsumDis();
​    if(tdis<mindis)mindis=tdis;
​    if(tdis+dep-1>limit||ok)return;
​    for(int i=1;i<=4&&!ok;++i)
​    {
​        if(tmp[dep-1]!=(dir[redir[i]]))
​        if(now.cango(i))
​        {
​            now.move(i);
​            tmp[dep]=dir[i];
​            dfs(dep+1);
​            tmp[dep]=0;
​            now.move(redir[i]);
​        }
​    }
}
void IDAstar()
{
​    ok=false;
​    now=s;
​    for(limit=s.getsumDis();!ok;limit+=mindis)
​    {
​        mindis=inf;
​        dfs(1);
​    }
}

例题

POJ1077 HDU1043 HDU3567

参考资料

http://www.cnblogs.com/goodness/archive/2010/05/04/1727141.html http://www.cnblogs.com/zufezzt/p/5659276.html

http://dev.gameres.com/Program/Abstract/a8first_2.htm http://www.cppblog.com/mythit/archive/2009/04/19/80492.aspx http://dev.gameres.com/Program/Abstract/Arithmetic/AmitAStar.mht