我在codereview上发布了这个问题，因为我发现那里没有回应，所以我在这里重复发布这个问题。
这个问题可以在hackerrank ai上找到。我不是在寻求解决方案，而是在试图找出我的策略或代码中有什么问题。
我试图解决一个我认为是2-D网格上的TSP的问题。因此，我试图获得我能得到的最佳结果。然而，前瞻一步比前瞻两步产生更好的结果。
问题是我必须在2-D网格上以最少的移动次数清理脏块，移动可以是UP, DOWN, LEFT, RIGHT, CLEAN。
另一个重要的事情是我做出一个移动后，过程会以网格的新状态和我的新位置重新开始，所以我必须再次运行算法。这也意味着我必须避免陷入循环，这在单一进程的情况下很容易避免，但在多实例进程的情况下需要算法来保证。
简而言之，我在我的进程中只需要做出next_move。
所以基本策略是找到离我当前位置最近的脏单元格。
为了前瞻一步，我会这样做：对于每个脏单元格，找到离所选脏单元格最近的脏单元格。对于两步，对于每个脏单元格，进行一步查找并找到最佳移动。对于多步也是如此操作。
然而，当我只进行一步查找时，我得到的分数更高，而进行两步查找时分数较低。分数的计算方式是(200 - steps_taken)。所以，我认为我的代码/策略中有些地方出了问题。
输入格式 :
b代表网格中的机器人。-是干净的单元格。d是脏单元格。
第一行是机器人位置的整数对。这使得网格中的b变得多余。如果机器人当前站在一个脏单元格上，那么网格中那个单元格上会有一个d。
第二行是网格的维度。
第三个输入是网格的行形式。请查看下面的示例输入。
我的Haskell代码是 :
module Main whereimport Data.List import Data.Function (on)import Data.Ord-- slits up a string -- ** only used in IO. split sep = takeWhile (not . null) . unfoldr (Just . span (/= sep) . dropWhile (== sep))-- ** only used in IOgetList :: Int -> IO [String]getList n = if n==0 then return [] else do i <- getLine; is <- getList(n-1); return (i:is)-- find positions of all dirty cells in the boardgetAllDirtyCells :: (Int, Int) -> [String] -> [(Int, Int)]getAllDirtyCells (h, w) board = [(x, y) | x <- [0..(h-1)], y <- [0..(w - 1)] , ((board !! x) !! y) == 'd']-- finally get the direction to print ;-- first argument is my-position and second arg is next-position.getDir :: (Int, Int) -> (Int, Int) -> StringgetDir (x, y) (a, b) | a == x && y == b = "CLEAN" | a < x = "UP" | x == a && y < b = "RIGHT" | x == a = "LEFT" | otherwise = "DOWN"-- only used in IO for converting strin gto coordinate.getPos :: String -> (Int, Int)getPos pos = let a = map (\x -> read x :: Int) (words pos) in ((a !! 0) , (a !! 1))-- manhattan Distance : sum of difference of x and y coordinatesmanhattanDis :: (Int, Int) -> (Int, Int) -> IntmanhattanDis (a, b) (x, y) = (abs (a - x) + (abs (b - y)))-- sort the positions from (botX, botY) position on manhattan-distance.-- does not returns the cost.getSortedPos :: (Int, Int) -> [(Int, Int)] -> [(Int, Int)]getSortedPos (botX, botY) points = map (\x -> (snd x)) $ sortBy (comparing fst) -- compare on the basis of cost. [(cost, (a, b)) | (a, b) <- points, cost <- [manhattanDis (a,b) (botX, botY)]]-- exclude the point `v` from the list `p`excludePoint :: (Ord a) => [a] -> a -> [a]excludePoint [] _ = []excludePoint p v = [x | x <- p , x /= v]-- playGame uses the nearest-node-policy. -- we start playing game when we are not going more deep. -- more about that in findBestMove-- game is to reduce the nodes to one node with the total cost ;-- reduction : take the next shortest node from the current-node.playGame :: (Int, Int) -> [(Int, Int)] -> [(Int, Int)]playGame pos [] = [pos]playGame startPos points = let nextPos = (head (getSortedPos startPos points)) in (nextPos : playGame nextPos (excludePoint points nextPos))-- sum up cost of all the points as they occur.findCost :: [(Int, Int)] -> IntfindCost seq = sum $ map (\x -> (manhattanDis (fst x) (snd x))) $ zip seq (tail seq)-- find the position which gives the smallest overall cost.smallestCostMove :: [(Int, (Int, Int))] -> (Int, (Int, Int))smallestCostMove [] = (0, (100, 100))smallestCostMove [x] = xsmallestCostMove (x:y:xs) | (fst x) <= (fst y) = smallestCostMove (x : xs) | otherwise = smallestCostMove (y : xs) -- This is actual move-finder. It does the lookups upto `level` deep.-- from startpoint, take each point and think it as starting pos and play the game with it.-- this helps us in looking up one step.-- when level is 0, just use basic `playGame` strategy. findBestMove :: (Int, Int) -> [(Int, Int)] -> Int -> (Int, (Int, Int))findBestMove startPos points level -- returns the move that takes the smallest cost i.e. total distances. | level == 0 = smallestCostMove $ -- return pair of (cost-with-node-x-playGame, x) map (\x -> (findCost (startPos : (x : (playGame x (excludePoint points x)))), x)) points | otherwise = smallestCostMove $ map (\x -> -- return pair of (cost-with-node-x, x) ( (findCost (startPos : [x])) + -- findBestMove returns the pair of (cost, next-move-from-x) (fst (findBestMove x (excludePoint points x) (level - 1))), x)) points-- next_move is our entry point. go only 2 level deep for now, as it can be time-expensive.next_move :: (Int, Int) -> (Int, Int) -> [String] -> Stringnext_move pos dim board = let boardPoints = (getAllDirtyCells dim board) numPoints = (length boardPoints) -- ** Important : This is my question : -- change the below `deep` to 1 for better results. deep = if (numPoints > 3) then 2 else if (numPoints == 1) then 1 else (numPoints - 1) in if pos `elem` boardPoints then getDir pos pos else getDir pos $ snd $ findBestMove pos boardPoints deepmain :: IO()main = do -- Take input b <- getLine i <- getLine -- bot contains (Int, Int) : my-coordinates. like (0,0) let botPos = (read $ head s::Int,read $ head $ tail s::Int) where s = split (' ') b -- dimOfBoard contains dimension of board like (5,5) let dimOfBoard = (read $ head s::Int, read $ head $ tail s::Int) where s = split (' ') i board <- getList (fst dimOfBoard) putStrLn $ next_move botPos dimOfBoard board我通过变量deep来控制我可以深入的程度。
示例板面是：
0 05 5b---d-d--d--dd---d------d可以有三个答案：
输出：
RIGHT or DOWN or LEFT重要：再次强调，新进程将使用新的板面和我的机器人的新位置被调用，直到我清理完所有脏单元格。
我做错了什么？
回答：
