• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computational Intelligence and AI in Games, IEEE Transactions on >Memory-Efficient Method for Fast Computation of Short 15-Puzzle Solutions
【24h】

Memory-Efficient Method for Fast Computation of Short 15-Puzzle Solutions

机译：快速计算15难题短解的内存有效方法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

While the 15-puzzle has a long and interesting history dating back to the 1870s, it still continues to appear as apps on mobile devices and as minigames inside larger video games. We demonstrate a method for solving the 15-puzzle using only 4.7 MB of tables that on a million random instances was able to find solutions of 65.21 moves on average and 95 moves in the worst case in under a tenth of a millisecond per solution on current desktop computing hardware. These numbers compare favorably to the worst case upper bound of 80 moves and to the greedy algorithm published in 1995, which required 118 moves on average and 195 moves in the worst case.
机译：尽管15拼图的历史可追溯到1870年代，但历史悠久而有趣，但它仍然继续作为移动设备上的应用以及大型视频游戏中的迷你游戏出现。我们演示了一种仅使用4.7 MB的表来解决15难题的方法，在一百万个随机实例上，该解决方案能够找到平均电流为65.21步的解决方案，最坏情况下为95步的解决方案，当前每个解决方案的十分之一毫秒以内桌面计算硬件。这些数字与最坏情况下的80个移动上限和1995年发布的贪婪算法相比较，后者平均需要118个移动，最坏情况下需要195个移动。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号