1

在标记为重复之前仔细阅读！

我有一个矩阵：
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

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

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

那么还应该使用哪些算法呢？

4

3 回答 3

2

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

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

伪代码：

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()

该解决方案的复杂性是指数级的，但这是预期的，因为两个节点之间存在指数级的简单路径。

于 2013-05-11T14:29:58.567 回答
0

我的专长！

哈斯克尔代码：

import Control.Monad (guard)

paths (a,b) (a',b') m n = solve [(a',b')] where
  solve result@((y,x):_) = do
    next@(y',x') <- [(y,x + 1),(y,x - 1),(y + 1,x),(y - 1,x)]
    guard (y' >= 0 && y' < m && x' >= 0 && x' < n && notElem (y',x') result)
    if next == (a,b) then [(next:result)] else solve (next:result)

输出：

*Main> take 2 . paths (0,3) (3,1) 5 $ 5
[[(0,3),(0,2),(0,1),(0,0),(1,0),(1,1),(1,2),(1,3),(1,4),(2,4),(2,3),(2,2),(2,1),(2,0),(3,0),(4,0),(4,1),(4,2),(4,3),(4,4),(3,4),(3,3),(3,2),(3,1)]
,[(0,3),(0,2),(0,1),(1,1),(1,2),(1,3),(1,4),(2,4),(2,3),(2,2),(2,1),(2,0),(3,0),(4,0),(4,1),(4,2),(4,3),(4,4),(3,4),(3,3),(3,2),(3,1)]]
(0.02 secs, 1595416 bytes)

*Main> length . paths (0,3) (3,1) 5 $ 5
4914
(1.28 secs, 100724732 bytes)

*Main Data.List Data.Ord> minimumBy (comparing length) . paths (0,3) (3,1) 5 $ 5
[(0,3),(1,3),(2,3),(3,3),(3,2),(3,1)]
(1.42 secs, 101955224 bytes)
于 2013-05-11T22:40:51.440 回答
0

我对与 OP 相同的问题感兴趣。我已经阅读过它并且很难找到合适的解决方案。许多解决方案都有图形方法，但没有矩阵。@amit 的评论和这个链接对我有很大帮助。

在这里您可以找到一个可行的解决方案： https ://repl.it/@gmunumel/StarryUniqueLicense

于 2018-04-10T15:29:36.383 回答