Кратчайший путь коня [Haskell]

[MariaD]

Нужно найти кратчайший путь коня на шахматной доске от заданного поля до конечного. Нашла код, использующий поиск в ширину, но он не оптимизированный. При задании "mapM_ printMoves $ shortestPath (1,1) (5,5)" , например в WinHugs выдает ошибку ERROR - Garbage collection fails to reclaim sufficient space, а GHCi вообще виснет.

как оптимизировать, чтобы работало для доски размером 8*8?

import Data.List(intersperse)
 
move :: (Int,Int) -> [(Int,Int)]
move (x,y) = filter (\(a,b) -> 0 < a && a <= 8 && a < b && b <= 8) [
  (x+2,y+1),
  (x-2,y+1),
  (x+2,y-1),
  (x-2,y-1),
  (x+1,y+2),
  (x+1,y-2),
  (x-1,y+2),
  (x-1,y-2)]
 
type Path = [(Int,Int)]
 
step :: [Path] -> [Path]
step paths = do
  path@(pos:_) <- paths
  map (:path) $ move pos
 
initiate :: (Int,Int) -> [Path]
initiate pos = [[pos]]
 
shortestPath :: (Int,Int) -> (Int,Int) -> [Path]
shortestPath start destination = let
  steps = iterate step (initiate start) :: [[Path]]
  filterActual = map $ filter (\(last:prev) -> last == destination) :: [[Path]] -> [[Path]]
  in map reverse . head . filter (not.null) $ filterActual steps
 
printMoves :: Path -> IO ()
printMoves = putStrLn . concat . intersperse "-" . map show

[Poma][a]

Могу дать код на Паскале\С++, если надо..

[MariaD]

нет, спасибо. паскаль это императивный язык, а хаскел декларативный. у них разные принципы работы.

[Вадим Мошев]

Так алгоритм работы-то один и тот же, разве не так?

[FPaul]

MariaD, если оптимально - то это BFS (поиск в глубину). Можно реализовать на основе алгоритма Ли. Все отличия от алгоритма Ли - отсутствие непроходимых клеток, 8 (а не 4) "соседей", 8 других условий для "соседей".
На Розетте был пример поиска пути из лабиринта для Haskell.

Теперь у вас ещё один пример... Но зато вместе с идеей, что менять.

[MariaD]

Всем спасибо, все работает