Что случилось с этой реализацией алгоритма IDA * в Haskell? Плохой эвристический или просто плохой код?

Question

Я пытаюсь написать программу haskell, которая может решить кубик rubiks. Во-первых, я попробовал this, но не понял выхода, чтобы не писать много кодов, поэтому я попытался использовать IDA * поиск этой задачи.

Но я не знаю, какая эвристика здесь уместна: я попытался разделить проблему на подзадачи и измерить расстояние от находящегося в восстановленном состоянии, но результат разочаровывает: программа не может уменьшить куб, который состоит из трех ходов от стандартного куба в разумные сроки. Я попытался измерить части ребер, а затем либо суммировать их, либо использовать максимальные значения ... но ни одна из этих работ не работает, и результат почти идентичен.

Так что я хочу знать, в чем проблема с кодом: является ли эвристика используемой недопустимой? Или мой код вызывает несколько бесконечных циклов, которые я не обнаружил? Или оба? И как это исправить? Код (соответствующие части) происходит следующим образом:

--Some type declarations 
data Colors = R | B | W | Y | G | O 
type R3 = (Int, Int, Int) 
type Cube = R3 -> Colors 
points :: [R3] --list of coordinates of facelets of a cube; there are 48 of them. 
mU :: Cube -> Cube --and other 5 similar moves. 

type Actions = [Cube -> Cube] 

turn :: Cube -> Actions -> Cube --chains the actions and turns the cube. 

edges :: [R3] --The edges of cubes 

totheu1 :: Cube -> Int -- Measures how far away the cube is from having the cross of the first layer solved. 
totheu1 c = sum $ map (\d -> if d then 0 else 1) 
         [c (-2, 3, 0) == c (0, 3, 0), 
         c (2, 3, 0) == c (0, 3, 0), 
         c (0, 3, -2) == c (0, 3, 0), 
         c (0, 3, 2) == c (0, 3, 0), 
         c (0, 2, -3) == c (0, 0, -3), 
         c (-3, 2, 0) == c (-3, 0, 0), 
         c (0, 2, 3) == c (0, 0, 3), 
         c (3, 2, 0) == c (3, 0, 0)] 

expandnr :: (Cube -> Cube) -> Cube -> [(Cube, String)] -- Generates a list of tuples of cubes and strings, 

-- the result after applying a move, and the string represents that move, while avoiding moving on the same face as the last one, 

-- and avoiding repetitions caused by commuting moves, like U * D = D * U. 

type StateSpace = (Int, [String], Cube) -- Int -> f value, [String] = actions applied so far, Cube = result cube. 

fstst :: StateSpace -> Int 
fstst s@(x, y, z) = x 

stst :: StateSpace -> [String] 
stst s@(x, y, z) = y 

cbst :: StateSpace -> Cube 
cbst s@(x, y, z) = z 

stage1 :: Cube -> StateSpace 
stage1 c = (\(x, y, z) -> (x, [sconcat y], z)) t 
where 
bound = totheu1 c 
t = looping c bound 
looping c bound = do let re = search (c, [""]) (\j -> j) 0 bound 
         let found = totheu1 $ cbst re 
         if found == 0 then re else looping c found 
sconcat [] = "" 
sconcat (x:xs) = x ++ (sconcat xs) 

straction :: String -> Actions -- Converts strings to actions 

search :: (Cube, [String]) -> (Cube -> Cube) -> Int -> Int -> StateSpace 
search cs@(c, s) k g bound 
| f > bound = (f, s, c) 
| totheu1 c == 0 = (0, s, c) 
| otherwise = ms 
where 
f = g + totheu1 c 
olis = do 
     (succs, st) <- expandnr k c 
     let [newact] = straction st 
     let t = search (succs, s ++ [st]) newact (g + 1) bound 
     return t 
lis = map fstst olis 
mlis = minimum lis 
ms = olis !! (ind) 
Just ind = elemIndex mlis lis 

Я знаю, что эта эвристика является противоречивым, но я не уверен, если это действительно допустимо, может быть, проблема ее неприемлемости?

Любые идеи, подсказки и предложения приветствуются, спасибо заранее.

Answer 1

Ваша эвристика недопустима. Допустимая эвристика должна быть нижней границей реальной стоимости решения.

Вы пытаетесь использовать в качестве эвристики количество боковых частей первого слоя, которые являются неправильными, или, возможно, число грани боковых частей первого слоя, которые являются неправильными, что это то, что вы на самом деле писали. В любом случае эвристика недопустима.

Следующий куб только 1 отходит от решения, но 4 частей в первом слое находятся в неправильном положении, а 4 лиц имеют неправильный цвет. Или эвристика скажет, что эта головоломка займет не менее 4 ходов, чтобы решить, когда ее можно решить только в 1 двигаться. Эвристика недопустима, поскольку они не являются нижними границами реальной стоимости решения.