2

在本主题中： 如何在 mxn 表中查找路径 我发现了如何在两点之间生成路径，这是代码：

go m n (i,j) = 
   [ (i+1,j) | i<m ] ++
   [ (i-1,j) | i>1 ] ++
   [ (i,j+1) | j<n ] ++
   [ (i,j-1) | j>1 ] 

-- isEndOfPath p q = (p == q)

genPath p q acc m n input buf = g p q acc buf where
  g p q acc buf | p==q = [(acc)]   -- return acc, buf
  g p q acc buf = [s
                     | r <- go m n q, notElem r buf, notElem r acc, 
                       notElem r input,
                       s <- genPath p r (r:acc) m n input (r:buf)] ++
                  [s
                     | r <- go m n q, notElem r acc, 
                       r==p,
                       s <- genPath p r (r:acc) m n input (r:buf)]

例如，我们可以在 2x2 板上搜索从 (2,2) 到 (1,1) 的路径。因此，我们可以称它为

genPath (2,2) (1,1) [(1,1)] 2 2 [(3,3),(1,1)] [(1,1)]

我们有结果

[[(2,2),(2,1),(1,1)],[(2,2),(2,1),(1,1)],[(2,2),(1,2),(1,1)],[(2,2),(1,2),(1,1)]]

所以我们有正确的路径。

现在我将找到点对之间的所有路径。在 Prolog 中这很容易，我对此没有任何问题。所以，也许我会向你展示我的算法和代码：

第一个谓词 - 当我们找到所有路径时，我们返回它：

genAllPaths([],A,A,_,_,_,_).

否则，我们必须递归地生成路径。因此，首先我们找到第一对之间的路径，然后我们可以搜索其他路径：

genAllPaths([(I1,J1),(I2,J2)|T],Acc,S,M,N,Input,Bufor) :-
    genPath((I1,J1),(I2,J2),[(I2,J2)],X,M,N,Input,[(I2,J2)|Bufor],NewBufor),
    genAllPaths(T,[X|Acc],S,M,N,Input,NewBufor).

如果您有不明白的地方，请问我。

因此，现在我将在 haskell 中执行此操作。我试过了，但我又遇到了很多问题。如果你知道怎么做并愿意帮助我 - 我将非常感激。

4

1 回答 1

1 
go m n (i,j) = 
   [ (i+1,j) | i<m ] ++
   [ (i-1,j) | i>1 ] ++
   [ (i,j+1) | j<n ] ++
   [ (i,j-1) | j>1 ] 

genPath p q acc m n input buf = g p q acc buf  -- return all solutions
  where
    g p q acc buf | p==q = [(acc,buf)]   -- return acc, buf
    g p q acc buf = [s |
                       r <- go m n q, notElem r buf, notElem r acc, 
                       notElem r input,
                       s <- g p r (r:acc) (r:buf)] ++
                    [s |
                       r <- go m n q, notElem r acc, 
                       r==p,
                       s <- g p r (r:acc) (r:buf)]

你的新代码：

genAllPaths([],A,A,_,_,_,_).

genAllPaths([(I1,J1),(I2,J2)|T],Acc,S,M,N,Input,Bufor) :-
  genPath((I1,J1),(I2,J2),[(I2,J2)],X,M,N,Input,[(I2,J2)|Bufor],NewBufor),
  genAllPaths(T,[X|Acc],S,M,N,Input,NewBufor).

直接翻译成 Haskell 的文本是：

genAllPaths points acc m n input buf = g points acc buf where
  g  []     acc  _  = [acc]
  g (p:q:t) acc buf = 
    let sols = genPath p q [q] m n input (q:buf) -- => [(x,newbuf)]
    in concat [g t (x:acc) newbuf | (x,newbuf) <- sols]

另一种写法是

genAllPaths points acc m n input buf = g points acc buf where
  g  []     acc  _  = [acc]
  g (p:q:t) acc buf = 
    genPath p q [q] m n input (q:buf) >>= (\ (x,newbuf) ->
    g t (x:acc) newbuf )

这使用列表 monad 中的绑定运算符。>>=还有do注解，

genAllPaths points acc m n input buf = g points acc buf where
  g  []     acc  _  = return acc    -- same as writing `[acc]`, for list monad
  g (p:q:t) acc buf = 
    do
      (x,newbuf) <- genPath p q [q] m n input (q:buf) 
      g t (x:acc) newbuf

它在没有显式使用bind的情况下表达相同的计算。List monad 通过将所有可能的选择表示为一个列表来表达非确定性计算。真正的表示将使用具有不可预测顺序的无序列表；普通的 Haskell 列表会产生顺序，但 Prolog 的从左到右从上到下的策略也是如此。

由于 Haskell 是惰性的，所以一一产生结果解相当于 Prolog 的回溯搜索，take 1可以用来模拟cut.

于 2013-06-22T10:20:57.717 回答