八数码问题
04计网 杨全海
(暨南大学珠海学院计算机科学与技术系)
关键字:八数码、搜索、人工智能
摘要:八数码问题是一个出名的人工智能问题,本文介绍基于搜索解决八数码问题的相关算法。
前言:《人工智能》课的作业,前前后后写了两个多月,很多起初认为不可能的后来经过长时间的思考也变成了可能,查了一些资料,发现自己好不容易想到的很多都已经被别人想到过了,强烈的郁闷中……
一、问题描述
在一个3*3的方格盘上,放有八个数码,剩下第九个为空,每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置,要求通过一系列的数码移动,将初始位置转化为目标位置。本文全部目标状态都为(1, 2, 3, 4, 5, 6, 7, 8, 0)。
例如:
4 1 3 x 1 3 1 x 3 1 2 3 1 2 3 1 2 3
x 2 5 4 2 5 4 2 5 4 x 5 4 5 x 4 5 6
7 8 6 -> 7 8 6 -> 7 8 6 -> 7 8 6 -> 7 8 6 -> 7 8 x
二、问题分析
1、状态表示
把一个状态,自左至右,自上而下地用一个长度为9的一维数组表示,其中空格用数字0表示。
例如:
1 2 3
4 5 x
7 8 6 可以表示为:(1, 2, 3, 4, 5, 0, 7, 8, 6)
规定四个算符,(u, d, l, r)分别对应于空格的四种移动方向。
2、无解判断
八数码问题不是任何情况下都是有解的,考察数组中除去0后的八位,如果在位置i<j时,有a[i]>a[j],则说明存在一个逆序。空格横向移动时,逆序总数无变化,而空格纵向移动时,逆序总数改变-2,0或2,因此,在任何情况下,方格盘上的逆序总数奇偶性不会改变。
3、避免重复访问
对于9!(362880)种状态,每个状态都是数字[0..9]的一个排列。如果我们能找到一个全排列到[0...362879]的一一映射,就可以用一个哈稀表记录状态是否被访问过,而且可以用位表示,空间开销也不大。
对于状态(x1, x2, x3, x4, x5, x6, x7, x8, x9),比它小的有两种情况:
i. 以y1开头的长度为9的所有排列,其中1<=y1<x1。如果这样的y1不存在,则表示没有比它更小的。
ii. 以x1开头的长度为9的排列(x1, y2, y3, y4, y5, y6, y7, y8, y9),其中(y2, y3, y4, y5, y6, y7, y8, y9)为比(x2, x3, x4, x5, x6, x7, x8, y9)更小的排列。
而对于后面一种,我们可以进行递归处理。
三、解决问题
1、盲目式搜索法(宽度优先搜索法)
从初始节点开始,一层一层向下扩展,直到找到目标节点。这种方法是万能的,只要初始节点和目标节点的奇偶性一致,总会有一条从初始状态到目标状态的路径。但这种方法的效率极低,一层一层扩展下去,状态总数可以说是成倍增长。为了提高效率,可以将同一层中相同的状态去掉。
ACM程序:http://www1.blog.163.com/article/-Uqdk-uFTYMZ.html
北大提交结果:
Problem Id:1077 User Id:zdker
Memory:2216K Time:609MS
Language:C++ Result:Accepted
2、盲目式搜索法(有界深度优先搜索法)
对于八数码问题,如果解存在,则绝对可以在一个常数C步内得到答案,C不超过32。
程序实现,不会从数学角度给出证明。
程序:http://www1.blog.163.com/article/-Uqdk-uFmnAM.html
ACM程序:http://www1.blog.163.com/article/-Uqdk-uGwz3e.html
北大提交结果:
Problem Id:1077 User Id:zdker
Memory:68K Time:171MS
Language:C++ Result:Accepted
3、盲目式搜索法(双向搜索法)
实质也是宽度优先搜索法。从初始状态和目标状态两边同时向中间广度搜索,如果左边扩展的新节点在右边已出现或者右边扩展的新节点在左边已出现,得到答案,结束搜索。
ACM程序:http://www1.blog.163.com/article/-Uqdk-uMhHOs.html
北大提交结果:
Problem Id:1077 User Id:zdker
Memory:3116K Time:46MS
Language:C++ Result:Accepted
4、启发式搜索法(A算法)
盲目式搜索虽然万能,但效率太低,空间耗费也很大,极不实用。为了提高算法的效率,我们采用启发式搜索法,就是利用与问题的有关信息引导搜索,以达到减少搜索量的目的。
每一次找出当前已扩展的最佳的状态接点继续进行搜索。
我们建立优先函数f(n)=g(n)+h(n);
从起始状态到当前状态的实际代价估计值:g(n);
从当前状态到目标状态的实际代价估计值:h(n);
g(n):深度(n结点)
h(n):
i. h1(n):不在位的棋子数。
例如:
2 8 3
1 6 4
7 x 5 h1(n)=6
ii. h2(n):所有棋子到其目标位置的距离和。
例如:
2 8 3
1 6 4
7 x 5 h2(n)=1+1+0+2+2+1+0+2=9
又分局部择优和全局择优。
5、启发式搜索法(A*算法)
我们重点关心的是快速得到解,而不一定要是最优的,对八数码这个特殊的问题,奇偶一样,就一定存在解。因此我们可以建立优先函数:
要求:g*(n)<=g(n); f*(n)>=f(n);
g*(n):深度(n结点)
h*(n):10*h2(n);
北大提交结果:
Problem Id:1077 User Id:zdker
Memory:1164K Time:78MS
Language:C++ Result:Accepted
四、待解决的问题
后来发现有界深度优先程序是错的,虽然提交过了。通过记录节点是否被访问过,后面的生成的节点有可能把前面可能的路径截断,而自己又因为深度控制而停止搜索。(如果不控制深度又内存不够,矛盾!)
深度搜索得到的解不一定是最优的,通过构造可以得到最优解。(不会)
五、问题总结
全部程序都可以在我的个人主页上找到,节点都避免了重复的扩展,同时都进行了无解判断,全部都在北大POJ(网址:http://acm.pku.edu.cn/JudgeOnline/)提交通过,其中扩展节点数是指输入为(2, 3, 4, 1, 5, x, 7, 6, 8)时的情况。
搜索策略\分析 | 时间 | 空间 | 扩展 节点数 | 分析 | ||
盲 目 式 搜 索 法 | 宽度优先 | 609MS | 2216K | 46290个 | 对时空要求高,但得到的解是最优的。 | |
有界 深度优先 | 171MS | 68K | 201248个 | 得到的解不一定是最优的。 内存里保存的是初始节点到当前节点的路径。 (不重复扩展+深度控制=错误) | ||
双向搜索 | 46MS | 3116K | 1089个 | 时空都是减少了一个数量级~~ (真正用到的) | ||
启 发 式 搜 索 法 | A 算 法 | h1(n) |
|
|
|
|
h2(n) |
|
|
|
| ||
A*算法 | 78MS | 1164K |
| 程序非我写,还没看明白。 |
http://www1.blog.163.com/article/-Uqdk-uvIuCR.html
参考文献
[1]《人工智能》教材(李陶深主编)
[2]本问后面的一篇文章(无名氏)
[3]一些杂碎的网络资料
[4]搜索推理技术(网址:http://www1.blog.163.com/article/-Uqdk-ukoUtq.html)
作者:
QQ:332910789
个人主页:http://zdker.blog.163.com/
网上找到的一篇文章:
The solution above essentially implements a breadth-first search to find a shortest solution to the problem. The fact that the number of puzzle configurations is not too large (eight factorial) means that there is enough storage for both the queue used in the search and the bitset used to identify configurations already searched. Such a solution would not work for the 15-puzzle, which I originally intended to use for this problem, because there would not be enough memory to handle the da
The judge's test case requires 31 moves to solve. This test case was generated by starting the breadth first search from the solution and working backwards until every legal configuration had been explored; this is the last of those configurations.
The most creative solution used randomness to search blindly for either the solution or a particular infeasible configuration. There was some discussion about whether this answer should be accepted, even if it worked, because it might not work on some case. We searched but never found the case that could whip it - that is, make it run beyond 30 seconds. It's interesting to consider whether a hybrid approach, that used both memory and randomness, could solve the 15 puzzle in a reasonable time.
In case you wondered, the generalized 15-puzzle (that is, the n-puzzle, where n is on
-- The End --
http://blog.163.com/liuhai_2097/blog/static/77550115200981594813791/
评论