1

重複としてマークする前に注意深くお読みください!

私は行列を持っています:
0 0 0 x 0
0 0 0 0 0 0
0 0
0 x 0 0 0
0 0 0 0

マトリックス内を斜めに移動することはできません!

2 つの「x」の間のすべての可能なパスを見つけたいと考えています。唯一の条件は、パスがそれ自体を横切ることができないことです (したがって、サイクルはありません)。どうやら、DSF アルゴリズムはすべてのパスを見つけるわけではありません (理由を理解するには、このペーパーを参照してください: http://www.algolist.net/Algorithms/Graph/Undirected/Depth-first_search )。

では、他にどのアルゴリズムを使用する必要がありますか?

4

3 に答える 3

0

私の専門！

Haskell コード:

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 に答える