Подтвердить что ты не робот

Решение 8 головоломок с алгоритмом A *

Я хотел бы решить/реализовать проблему с 8 головоломками, используя алгоритм A * в Java. Я спрашиваю, может ли кто-нибудь помочь мне, объяснив мне шаги, которые я должен выполнить, чтобы решить эту проблему. Я прочитал в сети, как работает A *, но я не знаю, как начать реализацию на Java.

Буду очень благодарен, если вы, ребята, можете мне помочь и дать мне рекомендации, чтобы я мог реализовать его сам на Java. Я действительно хочу это сделать, чтобы понять это, поэтому мне просто нужно руководствоваться.

Я буду использовать очереди приоритетов и прочитаю исходную конфигурацию из текстового файла, который выглядит, например, следующим образом:

4  3  6
1  2  5
7  8

Указатели на другие сайты для получения дополнительных пояснений/руководств приветствуются.

4b9b3361

ОТВЕТЫ

Ответ 1

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

Есть учебник, который я подготовил много лет назад:

http://www.cs.rmit.edu.au/AI-Search/

Это далеко не окончательное слово в поиске пространства пространства, но это просто образовательный инструмент для тех, кто новичок в концепции.

Ответ 3

A * очень похож на алгоритм Джикстры, за исключением того, что он включает эвристику. Возможно, вы захотите прочитать wiki или прочитать об алгоритмах кратчайшего пути с одним источником в целом.

Многие основные вещи важны, но очевидны. Вам нужно будет представить плату и создать метод для генерации возможных следующих состояний.

Базовая оценка для любой позиции, очевидно, будет минимальным количеством фактических ходов для ее достижения. Для работы A * вам нужна эвристика, которая поможет вам выбрать лучший вариант возможных состояний. Одной эвристикой может быть количество штук в правильном положении.

Ответ 4

Вам нужно будет выбрать способ представления состояний игры. Состояние проблемы с 8-головоломкой может быть представлено сеткой 3x3, 9-элементным целым массивом, 9-элементным массивом char, строкой или просто целым числом (436125780 может представлять состояние в вашем примере), с пустая ячейка представляется как 0. Использование только целого числа будет наиболее эффективным по пространству и поддерживать очень эффективную установку вставки/членства (для реализации закрытого набора). Однако найти государства-преемники будет сложнее. Использование 9-элементного массива char упростит поиск состояний-преемников. Я предлагаю вам использовать оба варианта. Используйте представление массива char для поиска преемника и целочисленного представления с закрытым множеством.

Затем вам нужно будет выбрать эвристическую функцию. Для 8-головоломки можно использовать расстояние Манхэттена, которое является последовательной эвристикой и гарантирует оптимальность алгоритма поиска графика A *.

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

Я написал сообщение в алгоритме поиска A * и предоставил python реализацию N-головоломки с использованием A * и Манхэттенского расстояния в качестве эвристики здесь: A * описание поиска и N-головоломка python