Используя алгоритм поиска A * для решения трехмерной головоломки?

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

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

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

Ответы

Ответ 1

Определите свою проблему как граф состояний:
G=(V,E) где V=S={(x_1,x_2,...,x_54) | all possible states the 3d board can be in} [каждое число представляет собой один квадрат на трехмерной доске].
и определите 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]) в основном, это суммирование расстояния manhattan для каждого номера из его цели.

Теперь, как только мы получим эти данные, мы можем запустить A * на определенном графе G с определенной эвристикой. И поскольку наша эвристическая функция допустима [убедите себя, почему!], Гарантируется, что найденное решение A * будет оптимальным, благодаря допустимости и оптимальности A *.
Поиск фактического пути: A * закончится при разработке целевого состояния. [ x_i=i в терминах, которые мы использовали ранее]. Вы найдете свой путь к нему, отступив от цели к источнику, используя поле parent в каждом node.

Ответ 2

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

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

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