algorithm - 计算 N×N 网格中每条路径的算法，不重复

Question

我有一个 NxN 单元格的网格（想想一个二维数组，定义如下 Array[N][N]）。

哪个算法将计算从每个单元格 a[i][j] 到每个单元格 a[k][l] 的每条路径，其中：

1. 没有单元格在单个路径中包含两次。
2. 只有相邻的对角线、水平和垂直移动都是合法的。
3. 平均而言，该算法是最快的。
4. 使用最少的内存。

Answer 1

广度优先搜索将完全符合您的要求。生成所有路径时没有最快的

Answer 2

我假设您想要实际路径，而不仅仅是它们的数量。

您可以通过使用在同一路径中探索的顶点上维护集合的 DFS 来实现它，并避免探索已经在同一路径中发现的顶点。visited

伪代码：

DFS(v,target,visited):
   if (v == target):
      print path to v from the initial sorce
      return
   visited.add(v)
   for each vertex u such that u is a neighbor of v:
      if (u is not in visited):
          u.parent <- v
          DFS(u,target,visited)
   visited.remove(v)

调用with DFS(source,target,{})[其中{}是一个空visited集]。