遍历2D数组(网格)的最佳寻路算法(JavaScript/Java/ c#)

Best pathfinding algorithm for traversing a 2D array (grid) touching some mandatory points (JavaScript/Java/C# )

本文关键字：算法 JavaScript Java 寻路 2D 数组 网格 遍历 最佳      更新时间：2023-09-26

我有一个2D数组，我想遍历它，从一个点开始到另一个点结束，条件如下:

  • 只允许在水平和垂直方向移动
  • 路径必须触及数组内的每个强制点
  • 数组没有障碍物

图示:

+---+---+---+---+---+---+
| 0 | 0 | 1 | 0 | 0 | E |
+---+---+---+---+---+---+
| 0 | 1 | 1 | 0 | 1 | 0 |
+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+
| S | 0 | 1 | 0 | 0 | 0 |
+---+---+---+---+---+---+

从S点开始，算法应该能够找到到达E的最短路径，触及所有以"1"表示的点，并且只能水平或垂直移动。

我必须在Javascript中实现它(但即使在c#或Java中也应该很好，我想我可以翻译它:))

哪种算法最适合我的需要?我已经谷歌了很多，但发现只有一些Dijkstra或a星实现是相似的，但不同(他们不必触及强制性点…)

有人遇到过这样的问题吗?

有人能帮忙吗?

提前感谢

好的，很抱歉回复晚了。我想你可能已经得到了一些实现。如果没有，想想这个。

让我先做一个简单的版本。假设S和E在各自的列中要么是最上面的，要么是最下面的。问题的图景与此相符。

算法应该:

  1. 向上(向下)移动列，直到达到最大值(当前列顶部，下一列顶部)。
  2. 切换到下一列。下一列成为当前列。
  3. 向下移动列，直到达到最大值(当前列底部，下一列底部)

注意事项

  1. 可以按行运行算法。
  2. 最后一行/列需要进行不同的处理。
  3. 最后一行/列和第一行/列可能需要遍历两次。
  4. 如果S和E位于行/列中间，需要修改。

注:我记得在什么地方做过这个算法问题。如果我找到来源，我会把它贴出来。

相关文章：