神仙道神兵解锁中的数学问题解析
|
关键字：神仙道攻略 神仙道神兵 神仙道全锁路线 神兵并不是一笔画问题，并不是要求尽量少重复的走完某些路线，而是要走过所有的点。 另外牵涉到买锁，这就不单单是只求过所有点的最短路线的问题了。 注：以下讨论均不考虑器魂(道源)的价值，对于不急于求成的道友，算器魂的成本意义不大。 道友们一般完成神兵的步骤是，寻找格子重复最少的路线，全锁走完。 想得多一点的道友，就会再看看是不是有等价的路线，可以在某个分叉口省1,2把锁。 想得更深一点的道友，还会想哪一种最短路线需要的锁的数量最少，是全锁走锁最少的路线还是在路口随机剩下1把锁。 实际上这就是一个数学问题(个人觉得是图论领域内的，但是我不懂图论)。 下面探讨几个问题： 1)一条确定的全锁路线需要的锁数怎么算 一条确定的路线有以下3个部分组成：全图点集合、重复点、终点。 全图点集合：神兵图上全部点的集合，每个点算一次，后面简称全图。 一条完整的路线，会经过每个点，因此路线其中必然包含一个全图点集合。 重复点：不得已必须回头重复的格子。 重复点也是一条完整的路线除开全图外，剩下的部分。 终点 之所以把终点拿出来说，是因为终点的时候不需要锁了。 然后再定义一个不难理解的概念——格锁数(简称格锁) 格锁=处在某个格子时必定往下一个位置走时所需要锁的数量=相邻格子的总数量-1 由定义可以看出，每个格子有唯一且确定的格锁。 在每一条确定路线上，一个点移动到下一个点所需要的锁的数量为前一个点的格锁。 整条路线由全图点集合和重复点组成。 路线走到终点时完结。 考虑到以上3点，可以给出一条确定路线需要的总锁数的公式： 总锁数=全图格锁+重复点格锁-终点格锁 根据这个公式，对于同时存在的几条最短路线来说： 全图格锁是一定的;重复点周边格子越少，总锁数越少;终点周边格子越多，总锁数越少。 在道友不想细算的时候，可以就根据以上规律判断，耗锁最少的路线。 2)存在两条最短路线时，分叉口是留2个方向还是1个方向 这个问题可能很多道友都选择留2个方向，省一把锁。 但是，实际上应该考虑每条路线的锁耗情况。 下面还是举例说明吧。 道友们看看附件的第一张图，很简单，但是也很容易说明问题。 后面给出4条最短路线，见图2 图3 图4 图5，都是只重复1格的路线。 按照之前的格锁公式，4个路线需要的总锁分别是14,15,15,17，道友可以验算下，看我算错没。 而这4条路线是由两个分叉路口的不同选择形成的，这个道友们应该很容易明白。 回到我们要讨论的问题，在分叉的地方要不要省锁，让系统随机2选1呢。 分情况讨论 1)如果2个分叉口都不随机，肯定是挑14锁的那一条路线走完最优; 2)如果2个分叉口都随机，可以省下2把锁，产生4种路线的锁数分别为:12,13,13,15，出现权重各25%,期望值13.25 3)如果只在第一个分叉口(图中红点处)不随机，优选形成路线1，路线2的方向。第二个分叉口随机，可以省下1把锁，产生2种等权重的结果,13,14.期望值13.5 4)如果只在第一个分叉口(图中红点处)随机，第二个分叉口人为优选，最后形成路线1和路线3，省下1把锁，产生2种等权重的结果,13,14.期望值13.5。 从上面4种情况的讨论看来，策略2，即全随机是最优的。 但是，这并不意味着有等价分叉路的时候，就该随机省锁。 举个返利，两条等价路线的锁分别是16和19，随机的期望是16.5，高于16，随机并不合适。 所以说，具体情况具体分析，我只是把分析实例的方法过程列出来了，以供参考。 3)是不是最短路线的锁数是最少的 答案：不是。 直觉上，应该是重复少的路线锁耗少，但是我们再来看看公式 锁数=全图格锁+重复格锁-终点格锁 存在一些特例，某一条路线和最短路线比，多重复了一格，但是终点格锁要少很多。 比如最后那一幅图和前面4附图的路线比多重复了一格，但是总锁数，我们来算下，14+2+2-3=15，也要比图4的耗锁要少，和图2,3相当。所以，最短路线的锁耗有优劣，并不是最短路线的耗费锁数就一定比非最短路线要少 不过目前看来，几种最短路线中最优的那一条的锁耗还是最少，但是我相信在某些复杂的图中是存在例外的。 结束语：基本上每一副神兵图就是一个数学题了，我想，求最优解，解数学题的乐趣应该是大于省下20元宝的乐趣的。(吐糟一下：其实就算算出最优解，也省不了多少元宝) 更多精彩内容： 更多精彩内容尽40407神仙道在：http://www.40407.com/sxd/ 【责任编辑：佚名】 |
