Найти хорошую эвристику для* поиска

Question

Я пытаюсь найти оптимальное решение для небольшой игры головоломки под названием Twiddle (апплет с игрой можно найти здесь) Игра имеет матрицу 3x3 с номером от 1 до 9. Цель состоит в том, чтобы принести числа в правильном порядке, используя минимальное количество движений. В каждом движении вы можете повернуть 2x2 квадрат либо по часовой стрелке, либо против часовой стрелки.

Т.е. если у вас есть это состояние

6 3 9
8 7 5
1 2 4

и вы поворачиваете верхний левый 2х2 квадратный

8 6 9
7 3 5
1 2 4

Я использую поиск A*, чтобы найти оптимальное решение. Мой f () - это просто количество необходимых вращений. Моя эвристическая функция уже приводит к оптимальному решению (если я изменяю его, см. Уведомление в конце), но я не думаю, что это лучшее, что вы можете найти. Моя нынешняя эвристика берет каждый угол, смотрит на число на углу и вычисляет расстояние Манхаттена до положения, которое это число будет иметь в решительном состоянии (что дает мне количество вращения, необходимое для достижения числа в эту позицию) и суммируют все эти значения. Т.е. вы принимаете приведенный выше пример:

6 3 9
8 7 5
1 2 4

И это конечное состояние

1 2 3
4 5 6
7 8 9 

тогда эвристика делает следующее

6 is currently at index 0 and should by at index 5: 3 rotations needed
9 is currently at index 2 and should by at index 8: 2 rotations needed
1 is currently at index 6 and should by at index 0: 2 rotations needed
4 is currently at index 8 and should by at index 3: 3 rotations needed

h = 3 + 2 + 2 + 3 = 10

Кроме того, если H равно 0, но состояние не полностью упорядочено, чем h = 1.

Но есть проблема, что вы вращаете 4 элемента одновременно. Таким образом, есть редкие случаи, когда вы можете сделать две (больше) из тезисов, оцениваемых в одном ходе. Это означает, что эти эвристики переоценивает расстояние до решения.

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

Итак, мой вопрос: Какая самая лучшая эвристика вы можете придумать?

(Отказ от ответственности: это для университетского проекта, так что это немного домашняя работа. Но я могу использовать любой ресурс, если смогу придумать, так что можно спросить вас, ребята. Также я буду отдать должное Stackoverflow за помощь; )))

Answer 1

Простота часто наиболее эффективна. Рассмотрим девять цифр (в порядке рядов) как формирование одного целого числа. Решение представлено наименьшим возможным целым числом I (G) = 123456789. Следовательно, я предлагаю следующую эвристику H (S) = I (S) - I (G). Для вашего примера H (s) = 639875124 - 123456789.

Answer 2

Все элементы должны учитываться при расчете расстояния, а не только угловых элементов. Представьте, что все угловые элементы 1, 3, 7, 9 находятся в своем доме, но все остальные нет.

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

Answer 3

Вы можете получить допустимую (т.е., не переоценивая) эвристику от своего подхода, принимая во внимание все цифры и делясь на 4 и завернувшись к следующему целому числу.

Чтобы улучшить эвристику, вы можете посмотреть на пары чисел. Если, например, в верхней части слева, числа 1 и 2 заменены, вам нужно, по крайней мере, 3 вращения, чтобы исправить их оба, что является лучшим значением, чем 1+1, учитывая их отдельно. В конце концов, вам все еще нужно разделить на 4. Вы можете произвольно соединить цифры или даже попробовать все пары и найти лучшее разделение на пары.