2

このトピック では: mxn テーブルでパスを見つける方法 2 つのポイント間のパスを生成する方法を見つけました。これがコードです。

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 )

これはlist モナドのバインド演算子を使用します。という表記>>=もありますが、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を明示的に使用せずに同じ計算を表現します。リストモナドは、すべての可能な選択肢をリストとして表すことにより、非決定論的な計算を表現します。真の表現では、順序が予測できない順序付けられていないリストが使用されます。通常の Haskell リストは順序を誘導しますが、Prolog は左から右、上から下の戦略で同じことを行います。

Haskell は怠惰なので、結果のソリューションを 1 つずつ生成することは、Prolog のバックトラッキング検索と同等であり、take 1エミュレートするために使用できますcut。

于 2013-06-22T10:20:57.717 に答える