搬运工问题的启示搜索.docx
《搬运工问题的启示搜索.docx》由会员分享，可在线阅读，更多相关《搬运工问题的启示搜索.docx（14页珍藏版）》请在冰点文库上搜索。
搬运工问题的启示搜索
搬运工问题的启示
重庆外语学校刘汝佳
【关键字】搬运工问题，人工智能搜索，IDA*
【摘要】本文讨论了一个有趣又富有挑战性的问题：
搬运工问题。
文章从状态空间搜索的基本知识开始讨论，根据搬运工问题的特点选择了IDA*算法，并做了初步改进。
本文的主要部分讨论了让程序智能化的几个方法–下界估计的改进，死锁判断，合适的任务分解与合并，模式搜索已经随机化实验，最后粗略的介绍了一些前面没有提到的想法，并做了总结。
前言
正文
一状态空间搜索基本知识
二搬运工问题及其特点
三用IDA*算法解搬运工问题–实现与改进
四如何使程序智能化
五模拟人的预测能力–下界估计
六模拟人的判断能力–死锁
七模拟人的安排能力–任务分解与合并
八模拟人的学习能力–模式搜索
九给程序注入活力–随机化实验
十另一些成功的和失败的想法
十一总结
附录
A.游戏（XsokobanforLinux和SokoMindforWindows）
B.测试关卡（标准90关，儿童61关，文曲星170关）
C.RollingStone源程序
D.我的程序S4-Srbga’sSuperSokobanSolver
E.论文配套幻灯片
F.参考资料
前言
“搬运工”是一个十分流行的单人智力游戏，玩家的任务是在一个仓库中操纵一个搬运工人将N个相同的箱子推到N个相同的目的地。
不清楚规则不要紧，玩一玩附件里的SokoMind就知道了。
我在里面加上了标准的测试关卡90关，幼儿关卡61关和文曲星170关，在以后的介绍中，我们就用这些关来测试我们的程序，因此我建议你自己先试一试，看看你能过多少关：
）
因为本文内容不算少，在这里我先给大家提供一个小小的阅读建议。
初学的朋友或者不知道IDA*算法的朋友一定要从第一章开始阅读并弄懂，因为它是全文的基础。
第二章很好懂，大家只需要做一个了解，知道搬运工问题的难点在哪里，为什么我们选择了IDA*算法。
急于看程序的朋友可以先看看第三章，我们的第一个版本S4-Baby诞生了，接着是一系列的改进措施，喜欢人工智能的朋友不妨认真看看，也许会找到灵感哦！
最后是总结，和第一章一样的重要，不要错过了。
我假定本文的读者已经对相关知识有一定了解，所以一般不给出很严格的定义或者论证，只是粗略的提一下，语言尽量做到通俗易懂。
但由于我的水平实在有限，错误之处一定不少，恳请大家批评指正：
）
欢迎大家和我联系。
Email:
****************,OICQ:
2575127。
一状态空间搜索基本知识
1.状态空间（statespace）
对于一个实际的问题，我们可以把它进行一定的抽象。
通俗的说，状态（state）是对问题在某一时刻的进展情况的数学描述，状态转移（state-transition）就是问题从一种状态转移到另一种（或几种）状态的操作。
如果只有一个智能体（Agent）可以实施这种状态转移，则我们的目的是单一的，也就是从确定的起始状态（startstate）经过一系列状态转移而到达一个（或多个）目标状态（goalstate）。
如果不止一个智能体可以操纵状态转移（例如下棋），那么它们可能会朝不同的，甚至是对立的目标进行状态转移。
这样的题目不在本文讨论范围之内。
我们知道，搜索的过程实际是在遍历一个隐式图，它的结点是所有的状态，有向边对应于状态转移。
一个可行解就是一条从起始结点出发到目标状态集中任意一个结点的路径。
这个图称为状态空间（statespace），这样的搜索就是状态空间搜索（Single-AgentSearch）
2.盲目搜索（UninformedSearch）
盲目搜索主要包括以下几种：
纯随机搜索（RandomGenerationandRandomWalk）
听起来比较“傻”，但是当深度很大，可行解比较多，解的深度又不重要的时候还是有用的，而且改进后的随机搜索可以对付解分布比较有规律（相对密集或平均，或按黄金分割比例分布等）的题目。
一个典型的例子是：
你在慌乱中找东西的时候，往往都是进行随机搜索。
广度优先搜索（BFS）和深度优先搜索（DFS）
大家都很熟悉它们的时间效率，空间效率和特点了吧。
广度优先搜索的例子是你的眼镜掉在地上以后，你趴在地板上找：
）-你总是先摸最接近你的地方，如果没有，在摸远一点的地方…深度优先搜索的典型例子是走迷宫。
它们还有逆向和双向的搜索方式，但是不再本文讨论范围之内。
重复式搜索
这些搜索通过对搜索树扩展式做一些限制，用逐步放宽条件的方式进行重复搜索。
这些方法包括：
重复式深度优先（IterativeDeepening）
限制搜索树的最大深度Dmax,然后进行搜索。
如果没有解就加大Dmax再搜索。
虽然这样进行了很多重复工作，但是因为搜索的工作量与深度成指数关系，因此上一次（重复的）工作量比起当前的搜索量来是比较小的。
这种方法适合搜索树总的来说又宽又深，但是可行解却不是很深的题目（一般的深度优先可能陷入很深的又没有解的地方，广度优先的话空间又不够）
重复式广度优先（IterativeBroadening）
它限制的是从一个结点扩展出来的子节点的最大值Bmax,但是因为优点不是很明显，应用并不多，研究得也比较少。
柱型搜索（BeamSearch）
它限制的是每层搜索树节点总数的最大值Wmax。
显然这样搜索树大小与深度成正比，但是可能错过很接近起点的解，而增加Wmax的时候保留哪些节点，Wmax增加多少是当前正在研究的问题。
3.启发式搜索（InformedSearch）
我们觉得一些问题很有“想头”，主要是因为启发信息比较多，思考起来容易入手，但是却不容易找到解。
我们不愿意手工一个一个盲目的试验，同样也不愿意我们的程序机械的搜索。
也就是说，我们希望尽可能的挖掘题目自身的特点，让搜索智能化。
下面介绍的启发式搜索就是这样的一种智能化搜索方法。
在刚才的那些算法中，我们没有利用状态本身的信息，只是利用了状态转移来进行搜索。
事实上，我们自己在解决问题的时候常常会估计状态离目标到底有多接近，进而对多种方案进行选择。
把这种方法用到搜索中来，我们可以用一个状态的估价函数来估计它到目标状态的距离。
这个估价函数是和问题息息相关的，体现了一定的智能。
为了以后叙述方便，我们先介绍一些记号：
S
问题的任何一种状态
H*（s）
s到目标的实际（最短）距离–可惜事先不知道：
）
H（s）
s的启发函数–s到目标距离的下界，也就是h（s）<=h*（s）,如果h函数对任意状态s1和s2,还满足h（s1）<=h（s2）+c（s1,s2）（其中c（s1,s2）代表状态s1转移到s2的代价）,也就是状态转移时，下界h的减少值最多等于状态转移的实际代价，我们说h函数是相容（consistent）的。
（其实就是要求h不能减少得太快）
G（s）
到达s状态之前的代价，一般就采用s在搜索树中的深度。
F（s）
s的估价函数，也就是到达目标的总代价的估计。
直观上，应该
有f（s）=g（s）+h（s），即已经付出的和将要付出的代价之和。
如果g
是相容的，对于s1和它的后辈节点，有h（s1）<=h（s2）+c（s1,s2）
两边同时加上g（s1）,有h（s1）+g（s1）<=h（s2）+g（s1）+c（s1,s2）,也就是
f（s1）<=f（s2）。
因此f函数单调递增。
表1启发式搜索用到的符号
贪心搜索（Best-FirstSearch）
象广度优先搜索一样用一个队列储存待扩展，但是按照h函数值从小到大排序（其实就是优先队列）。
显然由于h估计的不精确性，贪心搜索不能保证得到的第一个解最优，而且可能很久都找不到一个解。
A*算法
和贪心搜索很类似，不过是按照f函数值进行排序。
但是这样会多出一个问题：
新生成的状态可能已经遇到过了的。
为什么会这样呢？
由于贪心搜索是按照h函数值排序，而h只与状态有关，因此不会出现重复，而f值不仅状态有关，还与状态转移到s的方式有关，因此可能出现同一个状态有不同的f值。
解决方式也很简单，如果新状态s1与已经遇到的状态s2相同，保留f值比较小的一个就可以了。
（如果s2是待扩展结点，是有可能出现f（s2）>f（s1）的情况的，只有已扩展结点才保证f值递增）。
A*算法保证得到最优解，但是所用的空间是很大的，难以适应我们的搬运工问题。
IDA*算法
既然A*算法存在空间问题，那么我们能不能借用深度优先搜索的空间优势，用重复式搜索的方式来缓解危机呢？
经过研究，Korf于1985年提出了一个IternativeDeepeningA*（IDA*）算法，比较好的解决了这一问题。
一开始，我们把深度最大值Dmax设为起始结点的h值，开始进行深度优先搜索，忽略所有f值大于Dmax的结点，减少了很多搜索量。
如果没有解，再加大Dmax的值，直到找到一个解。
容易证明这个解一定是最优的。
由于改成了深度优先的方式，与A*比较起来，IDA*更加实用：
1.不需要判重，不需要排序，只用栈就可以了。
操作简单。
2.空间需求大大减少，与搜索树大小成对数关系。
其他的启发式搜索
这些方法包括深度优先+最优剪枝式的A*，双向A*,但是由于很不成熟或者用处并不大，这里就不介绍了。
A*算法有一个加权的形式，由于在搬运工问题中效果不明显，这里从略。
二搬运工问题及其特点
在对状态空间搜索算法有一定了解之后，我们来看看我们的搬运工问题。
究竟用什么方法比较好呢？
让我们先来看看该问题的特点。
1.搬运工问题
我们在前面已经介绍过搬运工问题，这里我只是想提一些和解题有关的注意事项。
首先，我们考虑的搬运工问题的地图规模最大是20*20，这已经可以满足大部分关卡了。
为了以后讨论方便，我们把地图加以编号。
从左往右各列称为A，B，C…，而从上往下各行叫a,b,c…。
而由于不推箱子时的走路并不重要，我们
在记录解的时候忽略了人的位置和移动，只记录箱子的移动。
人的动作很容易根据箱子的动作推出来。
下面是包含解答的标准关卡第一关。
呵呵，怎么样，第一关都要那么多步啊…以后的各关，可是越来越难。
2.搬运工问题的特点
我在前言里吹了这么半天，我想你即使以前没有玩，现在也已经玩过了吧：
）。
有什么感觉呢？
是不是变化太多了，不好把握？
不仅人不好把握，连编程序也变得困难了很多。
我们不妨拿它与经典的8数码问题作一个比较。
1.死锁！
初学者很快就会学到什么是死锁–一旦他（她）把一个箱子推到角上。
显然，这样的布局再继续玩下去是没戏了，不管以后怎么推都不可能把这个箱子推离那个角。
不少玩家都总结了不少死锁的经验，但是要比较系统的解决这个问题并不是一件容易的事。
我们将用整整一章（其实也不长啦）的篇幅来分析这个问题。
典型的死锁。
想一想，为什么：
）我们再看一下8数码问题。
它没有死锁，因为每一步都是可逆的。
在这一点上，搬运工问题要令人头疼得多了。
容易看出，这样的状态空间不是无向图，而是有向图。
2.状态空间。
8数码问题每次最多有4中移动方法，最多的步数也只有几十步。
而搬运工问题呢？
困难一点的关卡可以是一步有100多种选择，整个解答包括600多次推箱子动作。
分支因子和解答树深度都这么大，状态空间自然就非同小可了。
3.下界估计
在启发式搜索中，我们需要计算h值，也就是需要对下界进行估计。
8数码问题有很多不错的下界函数（如“离家”距离和），但是搬运工问题又怎么样呢？
我们不能直接计算“离家”距离，因为谁的家是哪儿都不清楚。
很自然，我们可以做一个二分图的最佳匹配，但是这个下界怎么样呢？
a.准确性
对于A*及其变种来说，下界与实际代价越接近，一般来说算法效率就越高。
我们这个最佳匹配只是“理想情况”，但是事实上，在很多情况下箱子相互制约，不得已离开目标路线来为其他箱子腾位置的事情是非常普遍的。
例如我们的标准关卡第50关，有的箱子需要从目标格子穿过并离开它来为其它箱子让路。
我们的下界函数返回值是100，但是目前的最好结果是370。
多么大的差别！
b.效率
由于下界函数是一个调用非常频繁的函数，其效率不容忽视。
最佳匹配的时间渐进复杂度大约是O（N^3）,比8数码的下界函数不知大了多少…我们将会在后面给出一些改进方法，但是其本质不会改变。
3.如何解决搬运工问题
已经有人证明了搬运工问题是NP-Hard，看来我们还是考虑搜索吧。
回想一下上一节提到过的状态空间搜索，用哪一种比较好呢？
既然是智力游戏，可用的启发式信息是非常丰富了，我们不仅是要用，而且要用得尽量充分,所以应该用启发式搜索。
而前面已经提到了，搬运工问题的状态空间是非常大的，A*是没有办法了，因此我们选择了IDA*算法：
实现简单，空间需求也少。
既然搬运工问题这么难，为什么有那么多人都解决了相当数量的关卡呢（标准的90N年以前就被人们模透了）。
因为人聪明嘛。
他们会预测，会安排，会学习，有直觉的帮助，还有一定的冒险精神。
他们（也包括我啦，呵呵）常用的是一些“高层次”的解题策略，既有效，又灵活。
（Srbga:
想学吗?
Readers:
当然想!
!
）可惜这些策略不是那么简单易学，也不是很有规律的。
在后面的章节中，我将尽力模仿人的思维方式给我们的程序加入尽量多的智能。
三用IDA*算法解搬运工问题
实现与改进
在上一节中，我们知道了IDA*算法是我们解决搬运工问题的核心算法。
在这一节里，我们将用IDA*算法来做一个解决搬运工问题的程序–虽然是我们的最初版本（我们称做S4-Baby），但是不要小看它哦！
1IDA*算法框架
由前所述，IDA*算法是基于重复式深度优先的A*算法，忽略所有f值大于深度限制的结点。
那么，我们不难写出IDA*算法框架的伪代码
伪代码1-IDA*算法框架
procedureIDA_STAR（StartState）
begin
PathLimit:
=H（StartState）–1;
Success:
=False;
repeat
inc（PathLimit）;
StartState.g:
=0;
Push（OpenStack,StartState）;
repeat
CurrentState:
=Pop（OpenStack）;
IfSolution（CurrentState）then
Success=True
ElseifPathLimit>=CurrentState.g+H（CurrentState）then
ForeachChild（CurrentState）do
Push（OpenStack,Child（CurrentState））;
untilSuccessorempty（OpenStack）;
untilSuccessorResourceLimitsReached;
end;
这只是一个很粗略的框架，什么事情都不能做。
不过我想大家可能比较急于试验一下IDA*的威力，因此我们不妨就做一个最最基本的程序。
2.第一个程序
要从框架做一个程序需要填充一些东西。
在这里我们就展开一些讨论。
输入输出文件格式
输入文件是一个文本文件，它由N行构成，每行是一些字符。
各种字符的含义是：
SPACE
空地
.
目标格子
$
箱子
*
目标格子中的箱子
@
搬运工
+
目标格子中的搬运工
#
墙
表2输入文件格式
这种格式和Xsokoban,SokoMind和RollingStone的格式是一致的，因此会比较方便一些。
输出文件第一行是推箱子的次数M，以下M行，每行的格式是：
xydirection,代表把第x行第y列的箱子往direction的方向推一步。
Direction可以是left,right,up,down之中的一个,1<=x,y<=20
数据结构
由于是最初的版本，我们不必考虑这么多：
只需要可行，编程方便就可以了，暂时不管它的效率和其他东西。
优化是以后的事。
我们定义新的数据类型BitString,MazeType,MoveType,StateType和IDAType。
请大家看附录中的程序，不难猜出它们的含义和用途。
唯一需要说明的BitString类型。
记录状态时，我们把地图看成一个大数，一个格子是一个bit。
那么所有箱子构成一个BitString,检查某一个是否有箱子（或者目标，墙）时只需要检测对应位置上的bit是否为1。
这样虽然会浪费一些空间，但是判断会比较快，操作也比较简单。
我们把x,y坐标合并成一个”position”变量。
其中Position=（x-1）*width+（y-1）。
我们用常量数组DeltaPos:
array[0..3]表示上，下，左，右的Position增量。
算法
为了简单起见，我们连最佳匹配也不做了，用所有箱子离最近目标的距离和作为下界函数。
不过，这里的“距离”是指推的次数，计算的时候（MinPush函数），只要忽略其它所有箱子，然后用一次BFS就可以了。
效果
嘿嘿，这个效果嘛，不说你也知道的，就是标准关一个也过不了啦。
不过为了说明我的程序是正确的，你可以试验一下幼儿关卡（共61关）嘛！
什么！
第一关都就没有动静了…55555，生成了18万个结点不过很多关都很快就过了的。
我们用1,000,000个结点为上限（在我的Celeron300A上要运行十多分钟）,得到以下的测试结果：
No.
步数
结点数
No.
步数
结点数
No.
步数
结点数
1
15
186476
21
8
102
41
11
145
2
6
24
22
7
110
42
10
118
3
5
14
23
10
192
43
12
223
4
6
24
24
10
432
44
8
63
5
9
31
25
4
23
45
12
138
6
5
8
26
11
846
46
14
178
7
6
35
27
3
18
47
8
296
8
11
39
28
9
38
48
8
156
9
4
12
29
10
142
49
5
60
10
5
14
30
8
641
50
11
14451
11
5
13
31
7
192
51
N/A
>1M
12
4
19
32
3
12
52
N/A
>1M
13
4
14
33
11
51
53
8
470
14
6
20
34
11
332
54
16
24270
15
6
57
35
16
11118
55
N/A
>1M
16
12
3947
36
10
242
56
14
3318
17
6
63
37
9
1171
57
N/A
>1M
18
11
5108
38
11
556
58
N/A
>1M
19
10
467
39
10
72
59
11
328
20
10
1681
40
9
203
60
N/A
>1M
61
N/A
>1M
没有解决的几关是：
51,52,55,57,,58,60,61
比较困难的几关是1,16,18,20,26,30,35,37,38,50,53,54,56
下面，我们来看看“困难关卡”的下界估计的情况，看看“偷懒”付出的代价。
关卡
最优步数
初始深度
结点总数
顶层结点数
1
15
11
186476
7416
16
12
7
3947
844
18
11
10
5108
49
20
10
6
1681
42
26
11
5
846
394
30
8
6
641
200
35
16
3
11118
3464
37
9
4
1171
493
38
11
5
556
250
50
11
6
14451
51
53
8
5
470
48
54
16
9
24270
2562
56
14
4
3318
460
由此可见，下界估计对于搜索树的大小是很有关系的。
看看第18,20,35,50,54,56关吧。
顶层结点多么少！
如果一开始就从这一层搜索不就…看来我们真的需要用最佳匹配算法了。
很抱歉，第四章之后的部分我也没有见到。
升级会员 