Очень доброжелательный и компетентный автор. Всегда был на связи, все разъяснил, предоставил несколько вариантов программы. Рекомендую.
Информация о работе
Подробнее о работе
Структуры и стратегии поиска в пространстве состояний. Игра «Пятнашки» (SWI Prolog)
- 18 страниц
- 2019 год
- 62 просмотра
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
ВВЕДЕНИЕ 2
1 Структуры и стратегии поиска в пространстве состояний 3
2 Игра «Пятнашки» 6
3 Реализация игры 7
3.1 Описание принципов работы программы 7
3.2 Описание предикатов 7
4 Пример работы программы 10
ЗАКЛЮЧЕНИЕ 11
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 12
ПРИЛОЖЕНИЕ 13
3.1 Описание принципов работы программы
В данной работе используется эвристика h(t), которая определяется суммой расстояний от каждой фишки до ее «конечной» клетки и значения оценки упорядоченности, умноженного на 4 (поскольку поле размером 4*4).
Оценка упорядоченности соответствует сумме оценок фишек. Оценка фишки, за которой следует допустимый преемник, равна 0. К примеру, если за фишкой «1» следует фишка «2», то оценка фишки «1» равна 0, а если фишка «3», то оценка будет равна 1. Для каждой фишки допустимым приемником является фишка с номером на единицу больше.
Реализованная программа будет осуществлять поиск возможных преемников вершины, упорядочивать их, выбирать оптимальное и выявлять поддерево этого преемника. Поиск приемников будет происходить пока не будет выполнено одно из следующих условий:
• значение другого поддерева станет меньше,
• поиск достиг предела,
• достигнут тупиковый конец,
• найдено искомое конечное решение.
...
3.2 Описание предикатов
В таблице 3.2.1 представлено описание предикатов, фактов, процедур и некоторых фактов, использованных в работе.
Таблица 3.2.1 – Описание предикатов, фактов, процедур, фактов
Наименование
Описание
Факт start
Начальная позиция фишки
Предикат decision (Start, Decision)
Получает начальные значения (Start) и выдаёт полученное решение (Decision)
Терм l(N, F/G)
Узел дерева (лист), где
N — узел в пространстве состояний,
G — стоимость пути, пройденного от начального узла до N,
F — значение функции f (N) = G + h(N)
Терм t(N, F/G, Subt)
Дерево с непустыми поддеревьями, где
N — корень дерева,
Subt — список поддеревьев,
G — значение функции g (N),
F — f-значение наиболее перспективного преемника N
Процедура expandtree(Way, Tree, Node, Tree1, Decided, Decision)
Разворачивает текущее дерево (поддерево), при условии, что f-значение этого дерева остается меньше или равно значению Tie. Когда цель найдена, то Decision является путём решения, а Decided = yes.
...
4 Пример работы программы
На рисунках 4.1-4.2 представлена работа предикатов start (установка начальных позиций), decision (решение задачи), showdecision (представление решения). Код программы представлен в приложении.
Рисунок 4.1 – Начало работы программы игры «Пятнашки»
Рисунок 4.2 – Результат работы программы игры «Пятнашки»
ЗАКЛЮЧЕНИЕ
В рамках данной курсовой работы была разработана игра «Пятнашки» на языке Prolog с использованием структур и стратегий поиска в пространстве состояний. В результате работы игры построено и описано дерево решений.
Были изучены и проанализированы структуры и стратегии поиска в пространстве. В частности, это поиск в глубину, поиск в ширину и итеративное углубление.
Пространством состояний является граф, чьи вершины определяют состояния, встречающиеся в задаче. Решением такой задачи является поиск верного пути в графе. В процессе решения задачи может возникнуть проблема обработки альтернативных путей поиска.
...
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Семинарские занятия Коломееца А.О. (дата обращения: 27.11.19).
2. Братко И. Программирование на языке пролог. - М.: Мир, 1990. - 560 с.
3. Братко И. Алгоритмы искусственного интеллекта на языке Prolog. – М.: Вильямс, 2004. – 640 с.
4. Люгер, Джордж, Ф. Искусственный интеллект: стратегии и методы решения сложных проблем. – Пер. с англ. – М.: Вильямс, 2003. -864 с.
5. Студопедия [Электронный ресурс] – URL: https://studopedia.su/1_8085_strukturi-i-strategii-poiska-v-prostranstve-sostoyaniy.html (дата обращения: 27.11.2019).
ПРИЛОЖЕНИЕ
Код программы
% d(Node,SonNode,Cost)
% Устанавливает узел, его преемника и стоимость дуги
d([Empty|Chips], [Chip|Chips1], 1):- % Все дуги имеют стоимость 1
exchange(Empty, Chip, Chips, Chips1). % Меняет местами пустая фишка Free и фишка Chip, получается Chips
exchange(Empty, Chip, [Chip|Subtrees], [Empty|Subtrees]):-
manhattandist(Empty, Chip, 1).
...
1. Семинарские занятия Коломееца А.О. (дата обращения: 27.11.19).
2. Братко И. Программирование на языке пролог. - М.: Мир, 1990. - 560 с.
3. Братко И. Алгоритмы искусственного интеллекта на языке Prolog. – М.: Вильямс, 2004. – 640 с.
4. Люгер, Джордж, Ф. Искусственный интеллект: стратегии и методы решения сложных проблем. – Пер. с англ. – М.: Вильямс, 2003. -864 с.
5. Студопедия [Электронный ресурс] – URL: https://studopedia.su/1_8085_strukturi-i-strategii-poiska-v-prostranstve-sostoyaniy.html (дата обращения: 27.11.2019).
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
