Используя алгоритм поиска A *, чтобы решить 3x3 трехмерную коробочную загадку?

Question

Я работаю над трехмерной коробкой-головоломкой 3х3 в своей домашней работе.Я буду кодировать с C.

Есть 26 полей, и первое место пусто.Сдвигая коробки, я должен расположить их в правильном порядке.Красные цифры показывают правильный порядок, и 27-е место должно быть наконец пустым.Я не хочу, чтобы вы дали мне код;Я искал на форумах, и мне кажется, что я должен использовать алгоритм поиска A * , но как?

Можете ли вы дать мне советы о том, как я могу использовать алгоритм A * в этой проблеме?Какой тип структуры данных мне следует использовать?

Answer 1

Определите вашу проблему в виде графика состояний:
G=(V,E), где V=S={(x_1,x_2,...,x_54) | all possible states the 3d board can be in} [каждое число представляет один 'квадрат' на 3d-доске].
и определите E={(v1,v2)| it is possible to move from state v1 to state v2 with a single step} альтернативное определение [идентично] для E с помощью функции successors(v):
Для каждого v в V: successors(v)={all possible boards you can get, with 1 step from v}

Вам также понадобится допустимая эвристическая функция , довольно неплохой для этой задачи может быть: h(state)=Sigma(manhattan_distance(x_i)) where i in range [1,54]) в основном, это сумма манхэттенских расстояний для каждого числа от его цели.* Теперь, когда мы получили эти данные, мы можем запустить A * на определенном графе G с определенной эвристикой.А поскольку наша эвристическая функция является допустимой [убедитесь сами, почему!], Она гарантирует, что решение, которое найдет A *, будет оптимальным благодаря допустимости и оптимальности A *.
Поиск фактического пути: A * закончится, когда вы разработаете целевое состояние.[x_i=i в терминах, которые мы использовали ранее].Вы найдете свой путь к нему, отступив от цели к источнику, используя поле parent в каждом узле.

Answer 2

Вы знаете, как работают графики и как A * находит кратчайшие пути на них, верно?

Основная идея состоит в том, что каждая конфигурация головоломки может рассматриваться как вершина в графе, а ребра представляют движения(путем соединения конфигураций до и после перемещения).

Поиск набора ходов, который ведет от исходной конфигурации к желаемой, можно рассматривать как проблему поиска пути.