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

Question

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

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

6 3 9
8 7 5
1 2 4

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

8 6 9
7 3 5
1 2 4

Я использую поиск A *, чтобы найти оптимальное решение. My 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

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

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

Answer 3

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

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