User
Было-бы интересно услышать, какие еще алгоритмы можно применить, для быстрого поиска пути в большом лабиринте?
-- bootstrap.hs module Main where import Data.List import Control.Monad import Control.Monad.Trans.State import System.Environment import System.Random import Text.Printf randomsN :: (RandomGen g, Random a) => (g -> (a, g)) -> Int -> g -> ([a], g) randomsN rnd n = runState (replicateM n (state rnd)) bootstrap :: (RandomGen g) => (Int, Int) -> g -> (Double, g) bootstrap (sN, tN) gen = (successCount / realToFrac tN, newGen) where rnd = randomR (1, tN) (rs, newGen) = randomsN rnd tN gen successCount = genericLength $ filter (<=sN) rs minusMetric :: RandomGen g => (Int, Int) -> (Int, Int) -> g -> (Double, g) minusMetric test control g = (m1 - m2, g2) where (m1,g1) = bootstrap test g (m2,g2) = bootstrap control g1 createGen :: [String] -> IO StdGen createGen [] = getStdGen createGen [seed]= return $ mkStdGen $ read seed main :: IO () main = do gen <- getArgs >>= createGen let metric = minusMetric (34, 893) (28, 923) (ms,_) = randomsN metric 10000 gen os = sort ms lcl = (os !! 250) * 100 ucl = (os !! 9750) * 100 putStrLn $ printf "LCL=%g%%" lcl putStrLn $ printf "UCL=%g%%" ucl
$ ghc --make -O2 bootstrap.hs
$ ./bootstrap.exe LCL=-0.8913676736965855% UCL=2.4389770442796324% $ ./bootstrap.exe 42 LCL=-0.8840882316900799% UCL=2.5182016381170995% $ ./bootstrap.exe 2013 LCL=-0.8768087896835746% UCL=2.4535359282926428% $ ./bootstrap.exe 2013 LCL=-0.8768087896835746% UCL=2.4535359282926428%
A*, можно в сторону Jump Point Search посмотреть еще: Алгоритм поиска пути Jump Point Search
Mitaka Version 1.2.0 (May 26, 2008 Released)
Компилируем:
Запускаем: