这个问题可以归结成旅行商问题(TSP),即「给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路」[1]。这是个NP-hard的问题,但对于原神的17个神像,要精确求解仍然非常简单。很多软件里都有现成的算法可以用,关键是数据怎么提取。
我从这个网站截了个图。本想看看源代码里有没有神像位置的数据,无奈代码太过繁杂,没有找到数据。所以我直接用图像匹配的方法搞到了数据。
思路很简单:用神像的图标作为模板,算每个点的相似度。然后找一个阈值,得到黑白的图像:
提取所有白色像素的位置,再用K-Means做个聚类,算一下均值,就得到了每个神像的坐标了:
找TSP最短路径倒是非常简单,Mathematica内置了FindShortestTour函数,直接就把结果给出来了:
当然,这里还只是个近似。实际情况中,要考虑地形(水、墙、山地等),问题会复杂很多。但大体的路线应该差不了多少。
考虑稻妻不能直接走过去,分开算的话是这样的:
来源:知乎 www.zhihu.com
作者:知乎用户(登录查看详情)
【知乎日报】千万用户的选择,做朋友圈里的新鲜事分享大牛。
点击下载
此问题还有 5 个回答,查看全部。
延伸阅读:
《原神》中神里绫人圣遗物怎么选择?