@Inside1995

Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка).
Определение. Перестано́вочные головоло́мки — головоломки, состоящие из множества подвижных элементов, которые могут занимать определённые места в головоломке и переводиться с места на место по определённым правилам. Подвижными элементами могут быть разноцветные шарики, кубики, фишки с буквами или цифрами, диски(ссылка из Википедии).
В общем на вход дается матрица:
Например: 8 4 3
5 0 6
1 2 7
где 0- это пустая клетка.
На выходе необходимо получить матрицу вида:
1 2 3
4 5 6
7 8 0

Насколько я понял в качестве эвристической функции необходимо использовать так называемый метод Манхеттена, где для каждого диска необходимо вычислить расстояние до его "настоящего" места.
Этот метод я смог реализовать, но так и не могу понять как реализовать сам алгоритм. Где начальная точка и что вообще нужно делать. Почитал разные статьи про этот алгоритм, но там в основном описывают этот метод на примере поиска кратчайшего пути в лабиринте (как он работает в этом примере, я разобрался), а вот как его перенести на эту задачу, понять не могу.
Заранее спасибо!

0

@Inside1995

Если кому-то может понадобиться эта информация, я смог определить метод по которому должен строиться алгоритм в этом случае.
Может я допущу какие- либо ошибки, так как это лишь мое понимание и может кому- то оно должно быть полезно.
Первым делом стоит определить что из себя представляет сам алгоритм А*. На самом деле это нечто схожее с алгоритмом Дейкстры, но добавлено еще некоторое условие, а именно эвристическая функция(f()). f() = g + h, где g - это стоимость достижения текущего узла, а h - это расстояние от текущего узла до нашей конечной цели.
за h в этом примере принято использовать метод манхеттена.
Метод Манхеттена. В этом методе необходимо найти каждую цифру, стоящую не на своем месте, посчитать сколько шагов нужно найти для достижения ее конечной позиции, и сложить все получившиеся результаты (результаты каждой цифры стоящей не на своем месте).
Например.
1 2 3
4 5 6
8 7 0
Если наш конечный результат должен выглядеть так:
1 2 3
4 5 6
7 8 0, то g у нас равно 2. Так как 7 у нас находится не на своем месте и 8 находится не на своем месте. 1 + 1 = 2.
Когда мы научились находить g для какой - либо расстановки возникает вопрос интерпретации самой доски, т.е. как доску хранить и всю информацию которая касается текущей доски.
Предлагается хранить все это в классе или структуре, где поля будут иметь следующий вид:
доска - может иметь вид матрицы или обычного массива
переменная g - для каждой промежуточной доски будет иметь свое значение
переменная h - аналогично с g
переменная f - хранит значение, возвращаемое функцией
переменная, которая хранит местоположение нуля в текущей таблице. Это важно, чуть ниже опишу почему.
указатель на родителя - необходимо для отслеживания конечного пути до цели.

Надеюсь пока все понятно.
Теперь собственно к самому алгоритму.
Алгоритм подразумевает хранение двух контейнеров:
openset - в книгах по ИИ это то, что называется переферией. То есть узлы, до которых можно дойти из текущего узла. В нашем случае узлы - это доски.
closedset - это узлы которые мы уже посетили.
openset советуется хранить в priorityqueue, так как начинать перебирать узлы нужно с узла, имеющего самый низкий показатель эвристической функции. А это ни что иное, как minheap.

Теперь нужно разобраться с тем, что же представляют из себя промежуточные доски.
Давайте представим следующую картину.
Наша входящая доска имеет вид
1 4 6
8 0 5
2 3 7
Какие варианты досок мы можем получить из текущей доски? Ответ очевиден. Это 4 разных доски, где нуль меняется с числом стоящим справа от него, слева от него, снизу от него и сверху от него. Выходит что в openset у нас попадают все "дети" текущей доски. А сама текущая доска помечается как посещенная(т.е. добавляется в closedset)
Это как раз тот случай, когда нам необходимо знать, где находится нуль. К слову если бы нуль находился в правом верхнем углу, то имелось бы всего два ребенка этой доски, так как нуль может поменяться местами лишь с числами стоящими слева от него и снизу от него.

Алгоритм А*
1)В openset помещается стартовая доска.
2)Начинаем цикл, который будет работать до тех пор, пока в openset есть какие-либо объекты
3)Извлекаем из openset элемент и сравниваем его с нашей целью. Если совпал, то отлично. Нет? Идем дальше
4)Помечаем текущую доску, как посещенную
5)Находим всех "детей" этой доски и помещаем их в openset, конечно если такой доски нет в closedset
6)Переходим к пункту 2

P.S. для того чтобы можно было вывести весь путь от старта до финиша нужно использовать ссылки на родителя, о которых я упоминал вначале.

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

P.S.S. В этой задаче могут попасться доски, для которых НЕТ РЕШЕНИЯ. В самом коде можно предусмотреть этот факт и сразу вывести ответ.

0