以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 算法理论与分析 』  (http://bbs.xml.org.cn/list.asp?boardid=60)
----  求助：制作一个拼图的算法！！  (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=19365)

--  作者：mimang
--  发布时间：6/7/2005 11:53:00 PM

--  求助：制作一个拼图的算法！！
题目：
＿＿＿＿＿＿
　｜　｜　｜
－｜－｜－｜初始状态时数字杂乱无章，空格的位置也随便放
＿｜＿｜＿｜
＿｜＿｜＿｜　　　　　

＿＿＿＿＿＿＿＿＿
　１｜２　｜３　｜
－｜－｜－｜－－－这是目标状态
＿４｜５＿｜６＿｜
＿７｜８＿｜＿＿｜
题目要求：可以以空格为参照物，每次空格都有四个方向的移动选择，但要求到达目标状态时所走步数最少
这个是我们小时候常玩的游戏，现在您能尝试着去设计吗？

--  作者：mimang
--  发布时间：6/7/2005 11:58:00 PM

--  
呵呵，不好意思，第２个图没画好
希望高手们多多指教呀，这题目困扰我好久了呢！
--  作者：asadafag
--  发布时间：6/10/2005 11:44:00 PM

--  
phoenix把那个visual eight放上来吧：）
--  作者：asadafag
--  发布时间：6/11/2005 4:19:00 PM

--  
http://learn.tsinghua.edu.cn/homepage/2003012267/Eight.rar
--  作者：mimang
--  发布时间：6/13/2005 11:27:00 PM

--  
以下是引用asadafag在2005-6-11 16:19:13的发言：
http://learn.tsinghua.edu.cn/homepage/2003012267/Eight.rar



呵呵，这里是什么呀?
--  作者：mimang
--  发布时间：6/13/2005 11:30:00 PM

--  
哦，呵呵,看到了,谢谢呀
--  作者：galois
--  发布时间：10/13/2005 10:29:00 PM

--  
八数码问题本身似乎非常经典。如果要求最小步数，就是一个典型的宽度优先搜索算法。一个训练有素的程序员应该在两个小时以内调试完整个程序。 好象最多二十来步肯定有结果。当年在486机器上也一会会儿就有结果了。现在的机器肯定瞬间就出来了。使用反向搜索将可以求出最多的搜索树深。 还有就是排列的奇偶性问题，形成了状态间的一个划分。
几年前，对这个问题我跟一位朋友做过讨论，当时（1998年）的讨论结果是，宽度优先搜索最多承受3*4的矩阵了。如果是4*4的15数码，无论如何利用普通机器都不可能在短时间有结果了（当然指的是最短的步数）。
不知各位高手对这个问题有没有深入的研究。
--  作者：admin
--  发布时间：10/14/2005 12:45:00 AM

--  
很多人工智能教材以这个作为范例的。可以翻几本书看看

以下是引用galois在2005-10-13 22:29:00的发言：
八数码问题本身似乎非常经典。如果要求最小步数，就是一个典型的宽度优先搜索算法。一个训练有素的程序员应该在两个小时以内调试完整个程序。 好象最多二十来步肯定有结果。当年在486机器上也一会会儿就有结果了。现在的机器肯定瞬间就出来了。使用反向搜索将可以求出最多的搜索树深。 还有就是排列的奇偶性问题，形成了状态间的一个划分。
几年前，对这个问题我跟一位朋友做过讨论，当时（1998年）的讨论结果是，宽度优先搜索最多承受3*4的矩阵了。如果是4*4的15数码，无论如何利用普通机器都不可能在短时间有结果了（当然指的是最短的步数）。
不知各位高手对这个问题有没有深入的研究。

W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 46.875ms