Поиск хорошей эвристики для поиска A *

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

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

6 3 9
8 7 5
1 2 4

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

8 6 9
7 3 5
1 2 4

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

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 для помогая мне;))

Ответ 1

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

Ответ 2

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

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

Ответ 3

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

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