Решение 8 задач с помощью алгоритма *

Question

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

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

---

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

4  3  6
1  2  5
7  8  

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

Answer 1

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

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

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

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

Answer 2

Check http://olympiad.cs.uct.ac.za/presentations/camp1_2004/heuristics.pdf описывает способы решения этой самой проблемы.

Answer 3

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

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

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

Answer 4

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

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

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

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