4. Задание на лабораторную работу

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

1. объединение,

2. пересечение,

3. вычитание.

Запустите программу через компилятор Пролог. Введите примеры и объясните полученные результаты.

3. Лабораторная работа № 3

РЕАЛИЗАЦИЯ АЛГОРИТМОВ ПОИСКА В ГРАФАХ НА ПРОЛОГ

Цель занятия

Ознакомиться с основными принципами представления графов и осуществления поиска в них на языке Пролог.

Порядок выполнения работы

1 Изучить основные алгоритмы поиска в графах

2 Реализовать процедуры слепых методов поиска на языке Пролог

3 Оформить отчет

4 Ответить на контрольные вопросы

Содержание отчета

1. Иллюстрация графа и поискового дерева

2. Представление структуры графа на языке Пролог

3. Текст процедуры поиска в глубину

4. Текст процедуры поиска в ширину

5. Вопросы системе и результаты

Контрольные вопросы

1. Представление задачи в терминах пространства состояний

2. Слепые методы поиска

3. Эвристические методы поиска

4. Поиск оптимального пути. Применение недооценок

1. Представление задачи в терминах пространства состояний

Многие задачи искусственного интеллекта формализуются путем сведения к пространству состояний. Пространство состояний – это граф, вершины которого соответствуют ситуациям, встречающимся в задаче, а решение задачи сводится к поиску пути в этом графе. Конкретная задача определяется:

• Пространством состояний

• Стартовой вершиной

• Целевым условием (ограничения задачи). Целевыми будут являться вершины, удовлетворяющие этим условиям.

Выбор стратегии поиска в пространстве состояний определяет порядок выбора альтернатив решения задачи.

Простейшим пространством состояний является сеть для решения транспортной задачи. В процессе поиска по сети идет вопрос о двух стоимостях:

• Вычисление пути

• Путешествие по нему

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

Поисковое дерево – это семантическое дерево, в котором узлы обозначают пути, а ветви соединяют пути, отличающиеся на 1 шаг.

2. Слепые методы поиска

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

Поиск в глубину. Процесс расширения происходит слева направо, то есть движение идет вглубь по дереву.

Алгоритм поиска в глубину:

1. создать одноэлементную очередь, включающую путь нулевой длины, соответствующий корневому узлу дерева.

2. пока головной путь в очереди не оканчивается целью или пока очередь не пуста повторять:

• удалить головной путь из очереди

• создать новые пути, расширяя его

• удалить из новых путей все циклические

• добавить оставшиеся пути в голову очереди

если полный путь найден, показать его, иначе сообщить о неудаче.

Поиск в ширину расширяет все узлы одного уровня поискового дерева, только потом происходит переход к следующему уровню. Алгоритм аналогичен поиску в глубину, только новые пути добавляются в хвост очереди.

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