ZOJ Problem Set – 3020 – Puzzle Quest

不知道多少人玩过 Puzzle Quest 这个游戏。这是个有日式画风,用宝石方块的对战方式来进行的RPG。一般的游戏模式需要进行消去,同时使用得到的宝石攻击对手。而怪物捕捉模式需要玩家将一块特定布局的棋盘上的宝石全部消去(GameFAQs 上有所有谜题的解答)。

ZOJ 3020 就是要求程序自动解这类的消去全部宝石的谜题(除去了爆炸骷髅这种宝石)。
最简单的解法当然就是深度优先搜索。流程代码还是比较简单的,就是检查每一种可能的操作和计算操作的结果,如果结果通过剪枝的话就迭代继续搜索。初步的剪枝算法也很简单,只要棋局中出现只有单个或两个的同种类宝石,就已经无解了。
深度优先搜索在比较简单的谜题上是没问题的,但是对一些复杂的谜题(一些需要10步以上操作的)就非常慢了。当一个谜题跑了10分钟还没结果的时候我放弃了,光靠优化算法的效率和使用更有效的复杂剪枝算法看来已经没法控制时间复杂度了。(之后看到别人给的代码,在深度搜索中加入了 hash表 作为棋局的缓存(类似动态规划了),能在3秒左右完成ZOJ的测试数据,但是在我的数据上仍然跑了1分钟多。)
于是对算法作了改动,改用启发式的最优最先搜索,由当前优先级最高的棋局继续搜索。这需要一个额外的判断棋局优先级的启发式算法(“看起来更有希望”的棋局有更高的优先级)。调查了几个花时间最长的谜题,加入两个条件,一个是棋局中剩余的宝石种类越少优先级越高(一是种类少一般剩余的宝石数量也少,另外也更方便接下去的消去操作),另一个是孤立的宝石距其它能凑成3个的宝石越远优先级越低(宝石分开的远的话很有可能在接下来的操作中没法把这些宝石凑在一起消除,鼓励程序优先消去这样的孤立宝石)。这样使程序的时间复杂度有了戏剧性的提高,能在1秒内跑完我全部的测试数据。
最后的成果是ZOJ上300毫秒的运行时间,之前ZOJ记录中最快的也需要2秒。
C++ 代码:

这类用程序自动解益智游戏的题还是相当有趣的。

Advertisements
This entry was posted in ACM, Science and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s