八数码问题的 A* 算法解答

最新推荐文章于 2021-04-26 15:05:57 发布

Rappy

最新推荐文章于 2021-04-26 15:05:57 发布

阅读量3.6k

点赞数

分类专栏：算法 Sicily 解题文章标签：算法 distance 数据结构扩展 struct output

本文链接：https://blog.csdn.net/Rappy/article/details/1927819

版权

算法同时被 2 个专栏收录

11 篇文章

订阅专栏

Sicily 解题

4 篇文章

订阅专栏

搞了一个通宵，终于搞定了！偶也！
Sicily 的 1379 那题，就是求给定的初始状态到目标状态，转换至少需要多少步。
例如状态

1 2 3

4 5 0

7 8 6

到达目标状态

1 2 3

4 5 6

7 8 0

只需一步（将 0 下移一格）即可。

在周赛的时候用广度搜索生成所有状态，耗时 0.6S 过了。但是这样不是聪明的办法（不过原理简单，实现也简单）。解这个问题的经典方法是使用 A* 算法进行启发式搜索，一般的人工智能原理的书都会介绍，在此不多说了。
看了下百度之星 2005 的比赛里 ACRush 的代码，只看懂一小部分 orz... （注释都没有的！），不过也收获不少，hmhm。。也看了 Ray 的这篇报告，受益匪浅。
下面是对该报告的一些补充（最好自己先看看那篇报告和人工智能的书关于启发式搜索的那章）：
此题关键之一是使用曼哈顿距离来作启发函数。两个状态中对应的数字的的横向距离和纵向距离之和，定义为该数字的距离，而除了 0 的各个数字的距离之和定义为两个状态的距离，如上面提及的两个状态的距离为 1（只有数字 6 位置不同，而横向距离为 0，纵向距离为 1）。
不难证明两个状态之间转换所需的步数不少于它们的距离。这样就满足了一般的 A* 算法的要求。采用评价函数 f (state) = g (state) + distance (state, goalState)，越小就越有希望到达目标状态，其中 g (state) 为从初始状态到达该状态的步数（随着搜索的进行，会发现到达该状态的更短的转换步骤，因此 g (state) 会逐渐减少至最小值 g* (state)）。
从开始状态开始搜索，按照将 0 上下左右移动的四种方式生成新的状态（当然要考虑可行性，如 0 已在最右边就不能再右移了）。在新的状态中找出评价函数值 f (state) 最小的状态来继续搜索（我们需要维护一个最小优先级队列 -- OPEN 表 -- 来找出 f 值最小的状态），直至搜索到目标状态。如果两个状态是可以互相达到的，那么可证 A* 算法一定可以找到最优解。
不难证明曼哈顿距离满足单调性，即在状态转换 state 1 -> 2 -> 3 中，distance (state1, state3) < distance (state2, state3) + cost (state1, state2)。
在满足这样的条件下，我们的搜索将满足以下两个有趣且有用的特性：
当要选择一个状态生成新状态时，它的 g (state) = g* (state)，即找到到达该状态的最少步数（如果你记录转换的上下左右记录的话，也将得到最少步数的转换步骤）。
选择的状态的评价函数值 f 是逐渐递增的。
如果不满足这个条件，那么在选择一个状态生成新状态时，新状态可能已经被生成过而且还被选择过，而达到这个新状态的步数可能会更少，即发现了更少的转换步骤，这样就有重复的工作了。而在满足条件下，一旦被选择则步数就已经是最少的了，就像最短路的 Dijkstra 算法那样。
而为了查询一个状态是否选择过，我们可以用一个 CLOSED 表 -- 来记录状态，在 C ++ 的 STL 中，我们可以选择 map 这种数据结构（一种平衡的二叉查找树），将一个状态对应的数字（如目标状态表示为 123456780）映射到对应的耗费 g 值。当然我们可以使用 hash_map 或者 trie 这两种数据结构，，或者自己实现一个哈希表，甚至使用“康托展开”直接映射到一个数组元素（后面几种数据结构占用内存较多）。这也是关键之一，我用自己实现的 trie 来做速度加快很多。另外预处理和使用一个变量 pos 来记录数字 0 的位置也很关键。
以下是我的代码：

// 八数码问题 A* 算法
// by rappizit@yahoo.com.cn
// 2007-12-10

#include < cstdio >
#include < queue >
#include < map >
using namespace std;

const int ten [ 9 ] = { 100000000 , 10000000 , 1000000 , 100000 , 10000 , 1000 , 100 , 10 , 1 };
int dist [ 9 ][ 9 ], diff [ 9 ][ 9 ];
// dist [i][j] 为位置 i, j 的曼哈顿距离， diff [i][j] 为交换位置 i, j 使状态数改变的量
int goalPos [ 9 ] = { 8 , 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 };
// goalPos [i] 为目标状态中 i 的位置
int goalNum = 123456780 ;     // 目标状态的状态数
int goalInv = 0 ;         // 目标状态忽略 0 后的逆序数
int state [ 9 ];             // 当前状态

struct STATE{
     int num, pos, g, h;     // 状态数，0 的位置，达到此状态的耗费，到达目标状态的启发函数值
    STATE ( int num, int pos, int g, int h):num(num), pos(pos), g(g), h(h){}
     bool operator < ( const STATE & other) const      // 状态的评价函数等于耗费加上启发函数值
    {
         if (g + h == other.g + other.h) return h > other.h;     // 由于查询较少，此句帮助不大，可删掉
         return g + h > other.g + other.h;
    }
};

void preprocess ()         // 预处理
{
     for ( int i = 0 ; i < 9 ; i ++ ){
        dist [i][i] = 0 ;
         for ( int j = 0 ; j < i; j ++ ){
            dist [i][j] = dist [j][i] = abs (i / 3 - j / 3 ) + abs (i % 3 - j % 3 );
            diff [i][j] = diff [j][i] = abs (ten [i] - ten [j]);
        }
    }
}

bool noAns ( int pos)         // 检查开始状态忽略 0 后的逆序数，如果和目标状态的逆序数奇偶性不一致，则没有解
{
     int inv = 0 ;
     for ( int i = 0 ; i < 9 ; i ++ ){
         for ( int j = 0 ; j < i; j ++ ){
             if (state [j] > state [i]) inv ++ ;
        }
    }
     return (inv - pos - goalInv) % 2 != 0 ;
}

int heu ( int pos)         // 计算启发函数值
{
     int h = 0 ;
     for ( int i = 0 ; i < 9 ; i ++ ){
         int j = goalPos [state [i]];
        h += dist [i][j];
    }
     return h - dist [pos][goalPos [ 0 ]];
}

int astar ()
{
     // int cnt = 0;
     int num = 0 , pos = 0 ;
     for ( int i = 0 ; i < 9 ; i ++ ){
        scanf ( " %d " , & state [i]);
    }
     for ( int i = 0 ; i < 9 ; i ++ ){
        num = num * 10 + state [i];
    }
     for ( int i = 0 ; state [i]; i ++ ){
        pos ++ ;
    }
     if (noAns (pos)) return - 1 ;     // 检查是否无解
    map < int , int > ng;         // CLOSED 表，已扩展的结点（状态数 -> 到达该结点的最少耗费）
    priority_queue < STATE > q;     // OPEN 表，待扩展的结点，但是仍然会存在已扩展的结点的记录
    STATE start(num, pos, 1 , heu (pos));     // 因为 map 对不存在的 key 返回 0，故初始状态的耗费应设为 1
    q.push (start);
     while (q.size ()){
         // cnt ++;
        STATE top = q.top ();     // 考察 OPEN 表中评价函数值最小的结点
        q.pop ();
         int pos = top.pos, num = top.num, g = top.g, h = top.h;
         if (num == goalNum){
             // printf ("%d ", cnt);
             return g - 1 ;     // 找到最优解，注意要减去 1
        }
         if (ng [num]) continue ;     // 已经扩展过此结点则忽略
        ng [num] = g;         // 结点加入 CLOSED 表
         // 扩展此结点
         if (pos > 2 ){         // move 0 up
             int p = pos - 3 ;
             int i = num / ten [p] % 10 , n = num - i * diff [pos][p];
             int h2 = h - dist [p][goalPos [i]] + dist [pos][goalPos [i]];
             if ( ! ng [n]) q.push (STATE (n, p, g + 1 , h2));
        }
         if (pos < 6 ){         // move 0 down
             int p = pos + 3 ;
             int i = num / ten [p] % 10 , n = num + i * diff [pos][p];
             int h2 = h - dist [p][goalPos [i]] + dist [pos][goalPos [i]];
             if ( ! ng [n]) q.push (STATE (n, p, g + 1 , h2));
        }
         if (pos % 3 ){         // move 0 left
             int p = pos - 1 ;
             int i = num / ten [p] % 10 , n = num - i * diff [pos][p];
             int h2 = h - dist [p][goalPos [i]] + dist [pos][goalPos [i]];
             if ( ! ng [n]) q.push (STATE (n, p, g + 1 , h2));
        }
         if (pos % 3 != 2 ){     // move 0 right
             int p = pos + 1 ;
             int i = num / ten [p] % 10 , n = num + i * diff [pos][p];
             int h2 = h - dist [p][goalPos [i]] + dist [pos][goalPos [i]];
             if ( ! ng [n]) q.push (STATE (n, p, g + 1 , h2));
        }
    }
     return 0 ;
}

int main ()
{
     // freopen ("input.txt", "r", stdin);
    preprocess ();
     int t;
    scanf ( " %d " , & t);
     while (t -- ){
        printf ( " %d " , astar ());
    }
     return 0 ;
}

/*
Input
第一行是一个整数n，表示一共有多少组测试数据。
下面n行每行9个字符，用空格隔开，代表一个初始状态。
目标状态是 1 2 3 4 5 6 7 8 0。

Output
最小操作步数，无解时输出-1。

sample input
4
1 2 3 4 5 0 7 8 6
1 2 3 4 0 5 6 7 8
8 6 7 2 5 4 3 0 1
6 4 7 8 5 0 3 2 1

sample output
1
14
31
31

注意在 Release 模式下运行此程序，否则可能会很慢！
注意优先队列 priority_queue 是最大堆，因此在定义 STATE 结构的比较函数时要让 f 值较小的元素较大，
而当 f 相等的时候，启发函数 h 较小的状态应该优先考虑，故让该状态较大。
优先队列中仍然会存在一些 CLOSED 表中的状态，因为在生成新的状态时没有查找删除该新状态是否生成过。
*/