寻一个解智力游戏的算法

皇家救星

游戏截图见：
http://hiphotos.baidu.com/%BB%CA%BC%D2%BE%C8%D0%C71985/mpic/item/ff0062f8bf6fe12cd9f9fde8.jpg

规则介绍

游戏开始时会给出16个顺序混乱的棋子（分成4行4列），棋子上面有序号
要求把棋子按顺序排列

移动棋子规则：
一次只能把整行棋子往左或右移动一格
或者把整列棋子往上或下移动一枨

举例：
棋子初始状态
1 2 3 4
5 6 7 8
9 10 11 12
0 13 14 15

要求转换成
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

-----------解题过程----------

将初始状态第四行往左移动一格变成

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

即是结果状态

tyc611

15数码问题的状态空间太大，广度和深度搜索都不适合，可以考虑A*

皇家救星

问题：如何编程实现游戏求解

在csdn上也问了这个问题[链接已更正]
http://topic.csdn.net/u/20090503 ... c-edde994dd761.html

有人回复用双向广度搜索　我根据这个算法的思路写了一个，但是效率不行

有其它更好的方法吗？

[ 本帖最后由 皇家救星 于 2009-5-9 12:44 编辑 ]

daybreakcx

和楼上的意见是相同的，状态空间太大

皇家救星

各位有比较好的A*估价算法吗？

我原来也想用A* 但考虑到编程复杂度和估价算法复杂度就没去实现

不知道A*算法比较广搜效率如何

daybreakcx

广搜的一大问题是空间消耗太大，如果用队列的话，越往下状态空间树就越大，粗略估计15码广搜按照所有的棋盘情况来分的话大概有16!=20922789888000，除去无解的还是很大，基本上很难负载的起来
A*如果评估函数选择的好的话效率比广搜高（广搜可以算是A*算法的一个特列），但是评估函数不好选，楼主还是去看看网络上八数码的实现可能可以找到启发

bidongliang

这是A*算法的例子啊，忘了是哪本书了! <人工智能>?

daybreakcx

人工智能上的例子是八数码问题貌似如果我没记错的话