shortest-path - 为什么矩形的两个角之间的路径看起来很奇怪？

Question

我编写了一个小程序来使用A* 算法找到两点之间的最短路径。

我将矩形中的每 10 个像素创建一个节点（宽度：100 个节点，高度：50 个节点）并将其与周围的 4 个节点（顶部、左侧、底部、右侧）连接起来。程序必须找到从左上角到右下角的最快路径。结果是这样的：

起初我想知道为什么这实际上是最快的方法，但后来我想我应该添加对角线连接。这是后来的样子：

到达终点需要 100 个节点，大约需要 100 个节点。1193 像素。这让我更加恼火，现在我想知道我的程序是否错误，或者这实际上是否是最短的方法。

你怎么看？

像第一张一样走同样的路，最后只走对角线不是更快吗？

标签： shortest-patha-star

Answer 1

如果没有对角线移动，最快的路径将采取(width-1)+(height-1)移动到达终点。但是对于对角线，它会更少。的移动，但我们只能进行min(width-1,height-1)对角线移动，其余移动必须是非对角线（在这种特殊情况下向右）。因此，这两张图片确实显示了您的代码似乎正确的最短路径。