Чтение онлайн

на главную

Жанры

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

Братко Иван

Шрифт:

Пути \== Z

Проверьте, что случится при поиске в пространстве состояний рис. 11.9, если эту цель опустить. Различие в выполнении программы, возникнет только при попытке найти новые решения в ситуации, когда не осталось больше ни одного решения.

11.6. Как программы настоящего раздела можно использовать для поиска, начинающегося от стартового множества вершин, вместо одной стартовой вершины?

11.7. Как программы этой главы можно использовать для поиска в обратном направлении, т.е. от целевой вершины к стартовой вершине (или к одной из стартовых

вершин, если их несколько). Указание: переопределите отношение
после
. В каких ситуациях обратный поиск будет иметь преимущества перед прямым поиском?

11.8. Иногда выгодно сделать поиск двунаправленным, т.е. продвигаться одновременно с двух сторон от стартовой и целевой вершин. Поиск заканчивается, когда оба пути "встречаются". Определите пространство поиска (отношение

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

11.9. Проведите эксперименты с различными методами поиска применительно к задаче планирования в "мире кубиков".

11.4. Замечания относительно поиска в графах, оптимальности к сложности

Сейчас уместно сделать ряд замечаний относительно программ поиска, разработанных к настоящему моменту: во-первых, о поиске в графах, во-вторых, об оптимальности полученных решений и, в-третьих, о сложности поиска.

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

Наши программы поиска в ширину порождают решающие пути один за другим в порядке увеличения их длин — самые короткие решения идут первыми. Это является важным обстоятельством, если нам необходима оптимальность (в отношении длины решения). Стратегия поиска в ширину гарантирует получение кратчайшего решения первым. Разумеется, это неверно для поиска в глубину.

Рис. 11.14. (а) Пространство состояний; а — стартовая вершина. (b) Дерево всех возможных ациклических путей, ведущих из а, порожденное программой поиска в ширину.

Наши программы, однако, не учитывают стоимости, приписанные дугам в пространстве состояний. Если критерием оптимальности является минимум стоимости решающего пути (а не его длина), то в этом случае поиска в ширину недостаточно. Поиск с предпочтением из гл. 12 будет направлен на оптимизацию стоимости.

Еще одна типичная проблема, связанная с задачей поиска, — это проблема комбинаторной сложности. Для нетривиальных предметных областей число альтернатив столь велико, что проблема сложности часто принимает критический характер. Легко понять, почему это происходит: если каждая вершина имеет b преемников, то число путей длины l, ведущих из стартовой вершины, равно bl (в предположении, что циклов нет). Таким образом, вместе с увеличением

длин путей наблюдается экспоненциальный рост объема множества путей-кандидатов, что приводит к ситуации, называемой комбинаторным взрывом. Стратегии поиска в глубину и ширину недостаточно "умны" для борьбы с такой степенью комбинаторной сложности: отсутствие селективности приводит к тому, что все пути рассматриваются как одинаково перспективные.

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

Резюме

• Пространство состояний есть формализм для представления задач.

• Пространство состояний — это направленный граф, вершины которого соответствуют проблемным ситуациям, а дуги — возможным ходам. Конкретная задача определяется стартовой вершиной и целевым условием. Решению задачи соответствует путь в графе. Таким образом, решение задачи сводится к поиску пути в графе.

• Оптимизационные задачи моделируются приписыванием каждой дуге пространства состояний некоторой стоимости.

• Имеются две основных стратегии поиска в пространстве состояний — поиск в глубину и поиск в ширину.

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

• Реализация поиска в ширину более сложна, поскольку требуется сохранять множество кандидатов. Это множество может быть с легкостью представлено списком списков, но более экономное представление — в виде дерева.

• Поиск в ширину всегда первым обнаруживает самое короткое решение, что не верно в отношении стратегии поиска в глубину.

• В случае обширных пространств состояний существует опасность комбинаторного взрыва. Обе стратегии плохо приспособлены для борьбы с этой трудностью. В таких случаях необходимо руководствоваться эвристиками.

• В этой главе были введены следующие понятия:

пространство состояний

стартовая вершина, целевое условие,

решающий путь

стратегия поиска

поиск в глубину, поиск в ширину

эвристический поиск.

Литература

Поиск в глубину и поиск в ширину — базовые стратегии поиска, они описаны в любом учебнике по искусственному интеллекту, см., например, Nilsson (1971, 1980) или Winston (1984). P. Ковальский в своей книге Kowalski (1980) показывает, как можно использовать аппарат математической логики для реализации этих принципов.

Kowalski R. (1980). Logic for Problem Solving. North-Holland.

Поделиться:
Популярные книги

Идущий в тени 5

Амврелий Марк
5. Идущий в тени
Фантастика:
фэнтези
рпг
5.50
рейтинг книги
Идущий в тени 5

Герой

Бубела Олег Николаевич
4. Совсем не герой
Фантастика:
фэнтези
попаданцы
9.26
рейтинг книги
Герой

Девятый

Каменистый Артем
1. Девятый
Фантастика:
боевая фантастика
попаданцы
9.15
рейтинг книги
Девятый

70 Рублей

Кожевников Павел
1. 70 Рублей
Фантастика:
фэнтези
боевая фантастика
попаданцы
постапокалипсис
6.00
рейтинг книги
70 Рублей

Возмездие

Злобин Михаил
4. О чем молчат могилы
Фантастика:
фэнтези
7.47
рейтинг книги
Возмездие

Школа. Первый пояс

Игнатов Михаил Павлович
2. Путь
Фантастика:
фэнтези
7.67
рейтинг книги
Школа. Первый пояс

Я снова не князь! Книга XVII

Дрейк Сириус
17. Дорогой барон!
Фантастика:
юмористическое фэнтези
попаданцы
аниме
5.00
рейтинг книги
Я снова не князь! Книга XVII

Газлайтер. Том 9

Володин Григорий
9. История Телепата
Фантастика:
фэнтези
попаданцы
5.00
рейтинг книги
Газлайтер. Том 9

Дайте поспать! Том II

Матисов Павел
2. Вечный Сон
Фантастика:
фэнтези
постапокалипсис
рпг
5.00
рейтинг книги
Дайте поспать! Том II

Корсар

Русич Антон
Вселенная EVE Online
Фантастика:
боевая фантастика
космическая фантастика
6.29
рейтинг книги
Корсар

Менталист. Революция

Еслер Андрей
3. Выиграть у времени
Фантастика:
боевая фантастика
5.48
рейтинг книги
Менталист. Революция

Убивать, чтобы жить

Бор Жорж
1. УЧЖ
Фантастика:
героическая фантастика
боевая фантастика
рпг
5.00
рейтинг книги
Убивать, чтобы жить

СД. Восемнадцатый том. Часть 1

Клеванский Кирилл Сергеевич
31. Сердце дракона
Фантастика:
фэнтези
героическая фантастика
боевая фантастика
6.93
рейтинг книги
СД. Восемнадцатый том. Часть 1

Прометей: каменный век

Рави Ивар
1. Прометей
Фантастика:
альтернативная история
6.82
рейтинг книги
Прометей: каменный век