1

这是我的代码：

maxX=8; maxY=8; 
maxSteps=60 -- If I change maxSteps=55 I get an answer
move :: [(Int, Int)] -> [( Int, Int)]
move list 
   | lastX>maxX || lastY>maxY || lastX<=0 || lastY<=0 = []
   | lastMove `elem` (init list) = []
   | length list == maxSteps = list
   | length m1 == maxSteps = m1
   | length m2 == maxSteps = m2
   | length m3 == maxSteps = m3
   | length m4 == maxSteps = m4
   | length m5 == maxSteps = m5
   | length m6 == maxSteps = m6
   | length m7 == maxSteps = m7
   | length m8 == maxSteps = m8
   | otherwise = []
   where lastMove = last list
         lastX = fst lastMove
         lastY = snd lastMove
         m1 = move (list ++ [(lastX+1,lastY+2)])
         m2 = move (list ++ [(lastX+2,lastY+1)])
         m3 = move (list ++ [(lastX-1,lastY+2)])
         m4 = move (list ++ [(lastX-2,lastY+1)])
         m5 = move (list ++ [(lastX+1,lastY-2)])
         m6 = move (list ++ [(lastX+2,lastY-1)])
         m7 = move (list ++ [(lastX-1,lastY+2)])
         m8 = move (list ++ [(lastX-2,lastY-1)])
y = move [(1,1)]
main = print $ y

你知道为什么它永远不会完成吗（也许我可以再等一下......）？您是否有其他解决方案来实现相同的蛮力算法但会更快？

4

1 回答 1

2

它确实终止了（它在我的计算机上运行了大约 1 分钟）并产生了正确的答案。

一种加快速度的简单方法是在列表的前面添加一个新的移动（并在打印之前反转结果）。添加第一个元素需要恒定的时间，而将元素附加到列表的后面是线性的。

您的代码中还有一个错误：m3并且m7是相同的。在修复了这个 bug 并将新的移动添加到列表的前面之后，代码会在一秒钟内运行：

maxX = 8
maxY = 8
maxSteps = 60

move :: [(Int, Int)] -> [( Int, Int)]
move list 
   | lastX > maxX || lastY > maxY || lastX <= 0 || lastY <= 0 = []
   | lastMove `elem` (tail list) = []
   | length list == maxSteps = list
   | length m1 == maxSteps = m1
   | length m2 == maxSteps = m2
   | length m3 == maxSteps = m3
   | length m4 == maxSteps = m4
   | length m5 == maxSteps = m5
   | length m6 == maxSteps = m6
   | length m7 == maxSteps = m7
   | length m8 == maxSteps = m8
   | otherwise = []
   where lastMove = head list
         lastX = fst lastMove
         lastY = snd lastMove
         m1 = move ((lastX + 1, lastY + 2) : list)
         m2 = move ((lastX + 2, lastY + 1) : list)
         m3 = move ((lastX - 1, lastY + 2) : list)
         m4 = move ((lastX - 2, lastY + 1) : list)
         m5 = move ((lastX + 1, lastY - 2) : list)
         m6 = move ((lastX + 2, lastY - 1) : list)
         m7 = move ((lastX - 1, lastY - 2) : list)
         m8 = move ((lastX - 2, lastY - 1) : list)
y = move [(1, 1)]
main = print $ reverse y

我又做了一些改动。首先，我摆脱了“手动”在每一步添加 8 个可能的动作。我们可以使用一个列表来做到这一点。这种方法有助于避免这样的错误。事实证明，执行时间取决于检查新动作的顺序。这个版本在大约一分钟内找到了一个开放的游览（而且，在我看来，它比原始代码更具可读性）：

maxX = 8
maxY = 8
maxSteps = 64
shifts = [-1, 1, -2, 2]

move :: [(Int, Int)] -> [(Int, Int)]
move path
   | lastX > maxX || lastY > maxY || lastX <= 0 || lastY <= 0 = []
   | lastMove `elem` tail path = []
   | length path == maxSteps = path
   | not (null validNewPaths) = head validNewPaths
   | otherwise = []
   where lastMove@(lastX, lastY) = head path
         newPaths = [(lastX + x, lastY + y) : path | x <- shifts, y <- shifts, abs x /= abs y]
         validNewPaths = filter (\xs -> length xs == maxSteps) (map move newPaths) 

main = print $ reverse (move [(1, 1)])
于 2016-11-06T13:03:58.500 回答