我知道我必须应用 Dijkstra 算法才能得到答案。整个算法在 answers 之一中进行了深入解释。 . 但是为什么我们需要将Dijkstra算法应用于这个问题。据我所知Dijkstra会找到最短距离路径。
但是问题设置者已经明确要求最小成本路径。考虑到这一点,我们不应该将 Prim 的算法应用于该问题并找到整个棋盘的 MST。
Here 是问题的链接。
最佳答案
Dijkstra 算法确实是为了寻找最短距离路径。但是,请注意,“距离”不一定是指以正常方式(即用尺子)测量的距离。
事实上,Dijkstra 算法也适用于在任何网络中寻找最短成本路径(前提是所有成本都大于或等于零)。您需要做的就是定义任意两个节点之间的距离等于相应边的成本。
因此,在这个问题中,当他们搜索最短路径时,他们根据问题中定义的成本函数来定义距离。
关于algorithm - 关于应用于国际象棋的算法的困惑,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47997928/