查找平方矩阵上2个点之间的所有路径 [英] Finding ALL paths between 2 points on a square Matrix

问题描述

重复标记之前请仔细阅读！

READ CAREFULLY BEFORE MARKING AS DUPLICATE!

我有一个矩阵：

0 0 0 x 0

0 0 0 0 0

0 0 0 0 0

0 x 0 0 0

0 0 0 0 0

I have a matrix:
0 0 0 x 0
0 0 0 0 0
0 0 0 0 0
0 x 0 0 0
0 0 0 0 0

您不能在矩阵中对角移动！

You CANNOT move diagonally in the matrix!

我想找到两个 x之间的所有可能路径。唯一的条件是，路径不能自身交叉（因此没有循环）。显然，DSF算法无法找到每个单独的路径（要了解原因，请参阅本文： http://www.algolist.net/Algorithms/Graph/Undirected/Depth-first_search ）。

I want to find ALL possible paths between the two 'x's. The only condition is, that the path cannot cross itself (so no cycles). Apparently the DSF algorithm would not find every single path (to understand why, see this paper: http://www.algolist.net/Algorithms/Graph/Undirected/Depth-first_search).

那么还应该使用什么算法？

So what algorithms should else be used?

推荐答案

没有访问集的DFS将在图中找到所有路径。

DFS without a visited set WILL find all paths in a graph.

您将必须维护一个特殊的访问集变体，该变体仅与当前路径相关，而不与全局相关。为此，每次完成探索顶点时，都必须将其从集合中删除。

You will have to maintain a special visited set variation that is relevant only for the current path, and not global. To do so, every time you "finish" exploring a vertex, you will have to remove it from the set.

伪代码：

DFS(source,target,visited,path):
   if (source == target): //stop clause
       print path
       return
   for each son v of source:
      if v is in visited: //the vertex is already in the current path
           continue
      path.append(v)
      visited.add(v)
      DFS(v,target,visited,path)
      visited.remove(v)
      path.deleteLast()

此解决方案的复杂度是指数级的，但由于两个节点之间的简单路径数量呈指数级，因此可以预期。

Complexity of this solution is exponential, but it is expected since there are exponential number of simple paths between two nodes.

这篇关于查找平方矩阵上2个点之间的所有路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！