![【XGAMER 元代碼 - 主題曲: 寂聲 (日本語)】 日語歌詞： Verse 1 目を閉じたいだけ 気にしていないふうに... 内の信念は 正しくない 風と海[真実を]告げて 失くしない 幻がなくて Chorus: 徹夜で戦った 日差し...](https://scontent.fdsa2-1.fna.fbcdn.net/v/t15.5256-10/336656091_162215126698640_3843734250325810940_n.jpg?stp=dst-jpg_p600x600&_nc_cat=102&ccb=1-7&_nc_sid=08861d&_nc_ohc=kQATFNXRo-kAX9EeaEw&_nc_ht=scontent.fdsa2-1.fna&oh=00_AfCnUOW2Bv6j_cgJTtG7RU2CcjvsthXu1Pj6XjGBE5943w&oe=641C69A7#)
.png&fb_obo=1&utld=tszching.uk&stp=c0.5000x0.5000f_dst-emg0_p160x160_q75_u&ccb=13-1&oh=06_AbHte9dNdbu6od1dt_bDvJQdrQLITsrLEPNhBtFxHSuSwQ&oe=63BDB559&_nc_sid=698a6b#){kind=icon}
要在《原神》中造访所有七天神像，最短的路线是什么样的？
这个问题可以归结成旅行商问题（TSP），即「给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路」[1]。这是个NP-hard的问题，但对于原神的17个神像，要精确求解仍然非常简单。很多软件里都有现成的算法可以用，关键是数据怎么提取。我从这个网站截了个图。本想看看源代码里有没有神像位置的数据，无奈代码太过繁杂，没有找到数据。所以我直接用图像匹配的方法搞到了数据。思路很简单：用神像的图标作为模板，算每个点的相似度。然后找一个阈值，得到黑白的图像：提取所有白色像素的位置，再用K-Means做个聚类，算一下均值，就得到了每个神像的坐标了：找TSP最短路径倒是非常简单，Mathematica内置了FindShortestTour函数，直接就把结果给出来了：当然，这里还只是个近似。实际情况中，要考虑地形（水、墙、山地等），问题会复杂很多。但大体的路线应该差不了多少。考虑稻妻不能直接走过去，分开算的话是这样的： 来源：知乎 www.zhihu.com 作者：知乎用户（登录查看详情） 【知乎日报】千万用户的选择，做朋友圈里的新鲜事分享大牛。 点击下载 此问题还有 1 个回答，查看全部。 延伸阅读：《原神》中神里绫人圣遗物怎么选择？原神深境螺旋什么时候才会开放呢?
这个问题可以归结成旅行商问题（TSP），即「给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路」[1]。这是个NP-hard的问题，但对于原神的17个神像，要精确求解仍然非常简单。很多软件里都有现成的算法可以用，关键是数据怎么提取。
我从这个网站截了个图。本想看看源代码里有没有神像位置的数据，无奈代码太过繁杂，没有找到数据。所以我直接用图像匹配的方法搞到了数据。
思路很简单：用神像的图标作为模板，算每个点的相似度。然后找一个阈值，得到黑白的图像：
提取所有白色像素的位置，再用K-Means做个聚类，算一下均值，就得到了每个神像的坐标了：
找TSP最短路径倒是非常简单，Mathematica内置了FindShortestTour函数，直接就把结果给出来了：
当然，这里还只是个近似。实际情况中，要考虑地形（水、墙、山地等），问题会复杂很多。但大体的路线应该差不了多少。
考虑稻妻不能直接走过去，分开算的话是这样的：
来源：知乎 www.zhihu.com
作者：知乎用户（登录查看详情）
【知乎日报】千万用户的选择，做朋友圈里的新鲜事分享大牛。
点击下载
此问题还有 1 个回答，查看全部。
延伸阅读：
《原神》中神里绫人圣遗物怎么选择？
原神深境螺旋什么时候才会开放呢?
李芷晴
https://tszching.uk
