8 головоломка: Разрешимость и кратчайшее решение

Я коснусь только вопроса разрешимости. Некоторый фон в перестановках необходим.

Перестановка — это переупорядочивание упорядоченного множества. Например, 2134 — это переупорядочивание списка 1234, где 1 и 2 меняются местами. Перестановка имеет свойство четности; это относится к четности числа инверсий. Например, в следующей перестановке видно, что существует ровно 3 инверсии (23,24,34):

1234
1432

Это означает, что перестановка имеет нечетную четность. Следующая перестановка имеет четную четность (12, 34):

1234
2143

Естественно, тождественная перестановка (которая сохраняет порядок элементов) имеет четную четность.

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

Согласно предоставленной вами ссылке в Википедии, приведенные выше критерии достаточны и необходимы для решения данной головоломки.

Алгоритм A* гарантированно находит (одно, если имеется более одного одинакового короткого решения) кратчайшее решение, если ваша эвристика всегда недооценивает реальные затраты (в вашем случае реальное количество необходимых ходов для решения).

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

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

Первые идеи для такой эвристики:

1. Довольно простая, но верная эвристика, которая всплыла в моей голове, — это манхэттенское расстояние от пустого поля до конечного пункта назначения.
2. Сумма манхэттенского расстояния каждого поля до его конечного пункта назначения, деленная на максимальное количество полей, которые могут изменить положение за один ход. (Я думаю, что это довольно хорошая эвристика)

Для всех, кто придет, я попытаюсь объяснить, как ОП получил пары значений, а также как он определяет выделенные, то есть инверсии, поскольку мне потребовалось несколько часов, чтобы понять это. Сначала пары. Сначала возьмите целевое состояние и представьте его как одномерный массив (например, A) [1,2,3,8,0,4,7,5]. Каждое значение в этом массиве имеет свой собственный столбец в таблице (идущий вниз, что является первым значением пары). Затем переместитесь на 1 значение вправо в массиве (i + 1) и пройдите весь путь снова вниз, значение второй пары. например (состояние A): первый столбец, второе значение начнет [2,3,8,0,4,7,5] уменьшаться. второй столбец начнется [3,8,0,4,7,5] и т. д..

хорошо теперь для инверсий. для каждого из двух парных значений найдите их местоположение INDEX в начальном состоянии. если левый ИНДЕКС > правый ИНДЕКС, то это инверсия (выделено). первые четыре пары состояния A: (1,2),(1,3),(1,8),(1,0)
1 находится в индексе 3
2 находится в индексе 0
3 > 0, поэтому инверсия.

1 равно 3
3 равно 2
3 > 2, поэтому инверсия

1 – это 3
8 – это 1
3 > 2, поэтому инверсия

1 равно 3
0 равно 7
3 ‹ 7, поэтому нет инверсии

Сделайте это для каждой пары и подсчитайте общее количество инверсий. Если оба четные или оба нечетные (Манхэттенское расстояние белого пятна и общее количество инверсий), то это разрешимо. Надеюсь это поможет!