algorithm - N x N グリッド内のすべてのパスを計算するアルゴリズム、繰り返しなし

Question

NxN セルのグリッドがあります (Array[N][N] のように定義された 2 次元配列を考えてください)。

どのアルゴリズムが、すべてのセル a[i][j] からすべてのセル a[k][l] へのすべてのパスを計算するか:

1. 1 つのパス内にセルが 2 回含まれることはありません。
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セット]を呼び出します。