登录 [F2] | 注册 | 找回密码 | 软件下载 | 更新历史 | 关于本站 | 管理团队
首页 排行榜 录像 雷界 论坛 教程 雷神殿 我的地盘 新手上路
[杂谈]【刷记录】上帝视角下最短路径gif动图观看 (2/563)
 [雷神] 王嘉宁 发表于 2019年9月6日
以前做的一个东西,现在再公开一下。就是如果已知雷的位置,即所谓上帝视角下,扫完雷图的最短路径。以丹帝的记录局为例,做下来最由结果是186.5571格,乘16,path应该就是2984.9136。我觉得这个东西可以当成一个记录来刷(如果有其他人有兴趣的话)。规则就是从(1,1)开始,终点是任意的,然后一定是点在格子的正中间。
最好是编程算,手算没有太多的乐趣。我这边用的算法就是原始的模拟退火算法,然后每次迭代再用贪婪算法优化一遍,效果其实不是很好。大家如果有兴趣还很闲可以用别的算法再做一遍。
当然主要是满足一下对这个问题好奇的人的好奇心。

https://pan.baidu.com/s/1_ZGU9RqXnwDHHBrRZYVRGQ
最近一次修改:2019-9-6 19:00:30
回复此主题
第 1 楼
 [雷神] 王嘉宁 回复于 2019年9月6日
补充:目前的这个路径不是最短的啊,而且只是NF扫法下的,之前可能没有说清楚。这个路径的最短值理论上是求不出的,因为是NP难题。所以说可以当成记录来刷。解这个问题时候,模拟退火算法其实是性能最差的算法之一,所以这个记录还有很大的进步的空间,本贴只是一个demo。
不过重要的是,你会发现在上帝视角下扫雷会缺少美感,想把标题的“欣赏”改成“观看”。
第 2 楼
 [雷神] 王嘉宁 回复于 2019年9月6日
还真能改
  共 2 篇回复  首页 | 上一页 | 下一页 | 末页  现在是第 1/1 页
楼主信息
Copyright @ 2008 扫雷网 Saolei.wang 版权所有 陕ICP备19026089号-1