Решение головоломки 8 с помощью алгоритма *
Я хотел бы решить / реализовать задачу 8 головоломок, используя алгоритм A* в Java. Я спрашиваю, может ли кто-нибудь помочь мне, объясняя мне шаги, которые я должен выполнить, чтобы решить это. Я прочитал в сети, как работает A*, но я не знаю, как начать реализацию в Java.
Я буду очень признателен, если вы, ребята, поможете мне и дадите мне рекомендации, чтобы я сам смог реализовать это на Java. Я действительно хочу сделать это, чтобы иметь возможность понять это, поэтому мне просто нужно руководство, чтобы начать.
Я буду использовать приоритетные очереди и буду читать исходную конфигурацию из текстового файла, который выглядит, например, так:
4 3 6
1 2 5
7 8
Указатели на другие сайты для получения дополнительной информации / учебники приветствуются.
4 ответа
Я бы начал с того, чтобы решить, как вы хотите представлять состояния игрового поля, а затем реализовать операторов (например, переместить (пусто) плитку вверх, переместить (пусто) плитку вниз,...). Как правило, у вас будет структура данных для представления открытого списка (т. Е. Тех состояний, которые были обнаружены, но еще не исследованы (т. Е. Сравниваются с состоянием цели), и другой для закрытого списка (т. Е. Тех состояний, которые были обнаружены и исследованы и признаны не являющимися состояние цели). Вы заполняете открытый список начальным состоянием и неоднократно берете "следующее" состояние, которое нужно исследовать из открытого списка, применяете к нему операторы для создания новых возможных состояний и так далее...
Есть учебник, который я подготовил много лет назад на:
http://www.cs.rmit.edu.au/AI-Search/
Это далеко от окончательного слова о поиске пространства состояний, хотя это просто образовательный инструмент для тех, кто не знаком с этой концепцией.
Проверьте http://olympiad.cs.uct.ac.za/presentations/camp1_2004/heuristics.pdf он описывает способы решения этой самой проблемы.
A* очень похож на алгоритм Джикстры, за исключением того, что он включает эвристику. Вы можете прочитать эту вики или прочитать об алгоритмах кратчайшего пути из одного источника в целом.
Многие основные вещи важны, но очевидны. Вам нужно будет представить доску и создать метод для генерации возможных следующих состояний.
Базовая оценка для любой позиции, очевидно, будет минимальным количеством фактических ходов, чтобы достичь ее. Чтобы A* работал, вам нужна эвристика, которая поможет вам выбрать лучший вариант из возможных следующих состояний. Одной эвристикой может быть количество фигур в правильном положении.
Вам нужно будет выбрать способ представления состояний игры. Состояние задачи из 8 задач может быть представлено сеткой 3x3, целочисленным массивом из 9 элементов, массивом из 9 элементов, строкой или просто целым числом (состояние 436125780 может представлять состояние в вашем примере) с пустым ячейка, представленная как 0. Использование только целого числа будет наиболее эффективным с точки зрения пространства и будет поддерживать очень эффективную проверку вставки / проверки набора (для реализации закрытого набора). Однако найти государства-преемника будет сложнее. Использование 9-элементного массива char облегчит поиск состояний преемника. Я предлагаю вам использовать оба. Используйте представление массива char для поиска преемника и целочисленного представления с закрытым множеством.
Затем вам нужно будет выбрать эвристическую функцию. Для 8 задач можно использовать манхэттенское расстояние, которое является последовательной эвристикой и гарантирует оптимальность алгоритма поиска A* графа.
Решение проблемы с A* требует поиска способа представления состояний, генерации преемников состояний и выбора эвристической функции. Остальная часть алгоритма может рассматриваться как черный ящик.
Я написал пост об алгоритме поиска A* и представил реализацию Python для решения задачи N-головоломки, используя A* и расстояние Манхэттена в качестве эвристики: объяснение поиска * и реализация Python для N-головоломки