福哥答案2020-06-12:#福大大架构师每日一题#

问:推箱子关卡可以用电脑求解吗?
答:对不太大,箱子不太多的关卡,目前有不少程序都能够求出答案。但是,推箱子已经被数学家和计算机科学家证明 是PSPACE完全(PSPACE-complete)问题,即基本可以认为不存在快速(多项式时间)的求解算法。对于比较大的关卡(如我们MF8推箱子比赛的关卡), 如今的个人电脑还无能为力。

方法如下:
1.BFS;
2.DFS;
3.A和IDA
4.遗传算法。

这4种方法,我只用第1种方法,其他方法不熟悉。方法1具体介绍:
①拉箱子比推箱子更高效,更有效。原因是拉箱子比起推箱子,天然自带死锁分析,天然自带剪枝功能。
②拉箱子和推箱子可以同时进行。拉箱子和推箱子一旦碰头,这就算解决了。经过测试,双向同时进行不一定比只拉箱子高效,原因是推箱子效率不高,太耗时,拖后腿了。
③对初始画面进行抽象。画面里有人、箱子、目标、墙、空间、人目标、箱子目标,经过抽象,会有1个起点画面和多个终点画面。起点画面和终点画面里只有箱子、墙、静止空间(人不能去的空间)、运动空间(人可以去的空间)。这样一来,人移动,不会做记录的,只有箱子移动才会做记录。
④重复节点过滤。每拉一次或者推一次,都需要保存到缓存。如果缓存里已经有了这个节点,就不需要再保存。
⑤每步节点。对于拉箱子节点,保存当前值和下一步节点,理由是当前节点只有1个下一步节点,而下一步节点有多个当前节点。对于推箱子节点,保存当前值和上一步节点,理由是当前节点只有1个上一步节点,而上一步节点有多个当前节点。
⑥死锁分析。死锁分析只针对推箱子。
福哥地雷法:在推箱子画面里,如果能移动箱子,这个箱子消失;如果不能移动,说明这个箱子死锁了。每个箱子相当于地雷,可以移动的,箱子就爆炸消失。
四块死锁、死角死锁、并排死锁、之字形死锁。福哥地雷法能解决。
凹形死锁、闭合死锁。福哥地雷法不能解决。
图片说明
图片说明
源码用的golang语言编写。代码超过了1000行,所以发布在github上。推箱子AI源码下载