求助！（推箱子的自动解法算法）—— 如解答满意，给分2000
开学不久就要交了
我现在还没有好的算法可以做这个的
让电脑自动推箱子
找出解法的算法
哪位兄弟做过
希望不吝赐教，小生感激不尽啊
如果有具体解法的
欢迎发至邮箱：muguateng@vip.sina.com
给分2000，决不食言
希望包括以下方面：
1. 如何寻找小人每推一次走的最短路径
2. 如何有效的找到解法（尽量少的系统资源）！！最重要的一点！！
非常感谢！
问题点数：0、回复次数：10Top
1 楼ZhangYv（迎着朝阳,走向地狱）回复于 2003-02-03 23:37:05 得分 0
hehe...不用2000分。这种经典问题早有现成算法，建议你去看看人工智能的算法。此问题可以用A*,自己去搜索引擎找找。
http://www.vchelp.net/vchelp/type.asp?class_id=1&type_id=74
如果需要可以参考其中的代码，别忘了向原作者道个谢。Top
2 楼Johnny_L（局长）回复于 2003-02-04 13:19:49 得分 0
这个是NP难问题啊
固定算法没有的啊
我想要的是大致的思路的
光用A*不行的
那个代码我有找过
可是看不透彻啊~Top
3 楼ZhangYv（迎着朝阳,走向地狱）回复于 2003-02-04 21:50:33 得分 0
你既然知道是NP Hard那还要什么思路，除了搜你还能想怎么样？所以才用A*来搜啊，A*的效率相对要高。
为什么只用A*不行，算法不行还是效率不高？我没想过，你先说说？Top
4 楼Johnny_L（局长）回复于 2003-02-05 13:07:01 得分 0
关键是不管你用什么优化公式来排序都无法保证那是优选啊
所以就有的时候一些很白痴的地图都解不出来
头痛啊Top
5 楼ZhangYv（迎着朝阳,走向地狱）回复于 2003-02-05 17:10:59 得分 0
A*是“启发式搜索”，评价函数做不好是你自己的问题了，可以参考一下别人的评价函数Top
6 楼whoke（hy）回复于 2003-02-09 22:04:22 得分 0
xxTop
7 楼aSenY（阿森）回复于 2003-02-09 23:17:57 得分 0
Up~~BGTop
8 楼IO_X（IO_X）回复于 2003-02-11 11:12:20 得分 0
用A*
正向搜索和逆向搜索一起进行会快一些吗？
还是用遗传算法或模糊逻辑更快？
Top
9 楼ftway（路上摔的）回复于 2003-02-11 23:01:55 得分 0
你们好强啊！！Top
10 楼MarkDong（）回复于 2003-02-12 15:50:29 得分 0
我是很爱玩推箱子的，当碰到很难的关时，也曾想过做一个算法实现自动搜索，有过简单思路，给大家说说
推箱子应该分为两种路线，第一是人无箱跑动的路线，第二种当然就是推箱子的路线，而第一种是由第二种决定的。
对于格子，我想可以分为如下几种，一种是目标格子，一种是普通格子，一种是死格。死格就是那种箱子只要推进去就打死也推不出来的格子。而某些死格可能是和箱子的位置相关的（我们可以称其为临时死格）。那么每当我们推了一次箱子（一次！不是一格）就应该重新计算临时死格。
普通格子我们也可以赋予它一些权值，我想可以是从这个格子移动到某个目标格子的拐弯次数（因为如果不用拐弯，那么就可以推着箱子一次到达目的）。那么相同权值的格子就形成了路线，我们的宗旨就是尽量将箱子从权值高的格子移动到权值低的格子上（当然中间可能会有利用权值高的格子过渡的情况）。
以上是我的一些思路，但是没想出来如何能实现，呜呜Top
