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 分間実行されます)、正しい答えが返されます。

それを高速化する簡単な方法の 1 つは、リストの先頭に新しい手を追加することです (そして、結果を印刷する前に反転させます)。最初の要素の追加には一定の時間がかかりますが、リストの後ろに要素を追加すると、そのサイズは線形になります。

コードにもバグがあります:m3とm7は同じです。このバグを修正し、リストの先頭に新しい動きを追加した後、コードは 1 秒未満で実行されます。

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 つの可能な手を追加する「手動」を取り除きました。リストを使用してそれを行うことができます。このアプローチは、このようなバグを回避するのに役立ちます。また、実行時間は、新しい手を調べる順序に依存することもわかりました。このバージョンでは、約 1 分でオープン ツアーが見つかります (そして、私の意見では、元のコードよりも読みやすくなっています)。

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