Я публикую этот вопрос из codereview поскольку я обнаружил, что он не отвечает.
Эта проблема доступна на hackerrank ai. Я не прошу решений, а пытаюсь найти, что не так с моей стратегией или кодом.
Я пытаюсь решить проблему, которая, как мне кажется, TSP on a 2-D grid
. Итак, я пытаюсь получить лучший результат, который я могу. Однако заглядывание вперед на 1 шаг дает лучшие результаты, чем заглядывание вперед на 2 шага.
Проблема в том, что я должен очистить грязные блоки на 2-D сетке за минимальное количество движений либо UP, DOWN, LEFT, RIGHT, CLEAN
.
Еще одна важная вещь заключается в том, что я делаю ход, а затем обрабатываю restarted
с новым состоянием сетки и моей новой позицией. поэтому мне нужно снова запустить алгоритм. Это также означает, что я должен избегать цикла, которого легко избежать в случае одного процесса, но алгоритм должен гарантировать его в случае нескольких экземпляров процесса.
Короче говоря, мне нужно сделать только next_move
в моем процессе.
поэтому основная стратегия состоит в том, чтобы найти ближайшую грязную ячейку к моей текущей позиции.
Чтобы посмотреть вперед на 1 шаг, я бы сделал: для каждой грязной ячейки и нашел ближайшую грязную ячейку к взятой грязной ячейке. Для шага 2 для каждой грязной ячейки выполните поиск шага 1 и найдите лучший ход. Аналогично для нескольких шагов.
Тем не менее, я получаю более высокий балл, когда выполняю поиск только в 1 шаг, но меньше баллов за поиск в 2 шага. оценка рассчитывается по (200 - steps_taken)
. Итак, я думаю, что что-то не так в моем коде/стратегии.
Формат ввода:
b
представляет бота в сетке. -
— чистая ячейка. d
- грязная ячейка.
Первая строка — пара целых чисел позиции бота. Это делает b
в сетке избыточным. Если бот в данный момент стоит в грязной ячейке, d
будет присутствовать в этой ячейке сетки.
Вторая строка - размерность сетки.
Третий вход представляет собой сетку в виде строк. См. пример ввода ниже.
Мой код на Haskell:
module Main where
import 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 IO
getList :: 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 board
getAllDirtyCells :: (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) -> String
getDir (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 coordinates
manhattanDis :: (Int, Int) -> (Int, Int) -> Int
manhattanDis (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)] -> Int
findCost 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] = x
smallestCostMove (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] -> String
next_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 deep
main :: 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
я могу работать с переменной deep
.
Образец платы:
0 0
5 5
b---d
-d--d
--dd-
--d--
----d
Ответов может быть три:
Вывод :
RIGHT or DOWN or LEFT
Важно: снова будет вызываться новый процесс с new board
и my bot new position
, пока я не очистю все грязные ячейки.
Что я делаю неправильно ?
(read (head s)) :: Int
можно заменить наread $ head s
, это не шепелявость, и сигнатура типа избыточна). Вы должны преобразовать свои направления в тип данных вместо использования строк. Ваш код выходит за правую часть страницы, немного разбейте его. Введите несколько новых функций в необходимыхwhere
блоках, чтобы сделать ваш код более понятным. Это поможет вам понять ваш код точно так же, как и другим. Если вы лучше понимаете свой код, вам будет легче решать проблемы. - person bheklilr   schedule 25.02.2015data Square=Clean|Dirty
. И задокументируйте, что делает каждая функция. И объясните где-нибудь, как представлена доска и почему вы выбрали именно это представление. И ссылку на первоисточник проблемы. И объясните проблему лучше. В нынешнем виде ваш код практически нечитаем. - person dfeuer   schedule 26.02.2015