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





Глава 11. Основные стратегии решения задач


    Глава 11. Основные стратегии решения задач
    ОСНОВНЫЕ СТРАТЕГИИ РЕШЕНИЯ ЗАДАЧ В данной главе мы сосредоточим свое внимание на одной общей схеме для представления задач, называемой пространством состояний. Пространство состояний - это граф, в...
Предварительные понятия и примеры
Предварительные понятия и примеры Рассмотрим пример, представленный на рис. 11.1. Задача состоит в выработке плана переупорядочивания кубиков, поставленных друг на друга, как показано на рисунке....Задача перестановки кубиков.
Задача перестановки кубиков. Ясно, что альтернативу поставить С на стол не имело смысла рассматривать всерьез, так как этот ход никак не влияет на ситуацию. Как показывает рассмотренный пример, с..."игра в восемь" и ее представление в форме графа.
Игра в восемь и ее представление в форме графа. нять козу от волка и капусту от козы. С описанной парадигмой согласуются также многие задачи, имеющие практическое значение. Среди них - задача о ко...Стратегия поиска в глубину
Стратегия поиска в глубину Существует много различных подходов к проблеме поиска решающего пути для задач, сформулированных в терминах пространства состояний. Основные две стратегии поиска - это п...Пример простого пространства состояний: а - стартовая
Пример простого пространства состояний: а - стартовая вершина, f и j - целевые вершины. Порядок, в которой происходит проход по вершинам пространства состояний при поиске в глубину: а, b, d, h, e,...Начинаясь в а, поиск вглубину заканчивается бесконечным циклом между d и h: a, b, d, h, d, h, d ... .
Начинаясь в а, поиск вглубину заканчивается бесконечным циклом между d и h: a, b, d, h, d, h, d ... . Очевидное усовершенствование нашей программы поиска в глубину - добавление к ней механизма обн...Отношение вглубину( путь, в, решение).
Отношение вглубину( Путь, В, Решение) . Для облегчения программирования вершины в списках, представляющих пути, будут расставляться в обратном порядке. Аргумент Путь нужен для того, (1) чтобы не р...Программа поиска в глубину без зацикливания.
Программа поиска в глубину без зацикливания. Теперь наметим один вариант этой программы. Аргументы Путь и Верш процедуры вглубину можно объединить в один список [Верш | Путь] . Тогда, вместо верши...Программа поиска в глубину с ограничением по глубине.
Программа поиска в глубину с ограничением по глубине. Для того, чтобы предотвратить бесцельное блуждание по бесконечным ветвям, мы можем добавить в базовую процедуру поиска в глубину еще одно усов...Упражнения
Упражнения Напишите процедуру поиска в глубину (с обнаружением циклов) вглубину1( ПутьКандидат, Решение) отыскивающую решающий путь Решение как продолжение пути ПутьКандидат . Оба пути представляй...Поиск в ширину
Поиск в ширину В противоположность поиску в глубину стратегия поиска в ширину предусматривает переход в первую очередь к вершинам, ближайший к стартовой вершине. В результате процесс поиска имеет...Простое пространство состояний: а - стартовая вершина,
Простое пространство состояний: а - стартовая вершина, f и j - целевые вершины. Применение стратегии поиска в ширину дает следующий порядок прохода по вершинам: а, b, c, d, e, f. Более короткое ре...Реализации поиска в ширину.
Реализации поиска в ширину. путей-кандидатов. Само множество будет списком путей, а каждый путь - списком вершин, перечисленных в обратном порядке, т. е. головой списка будет самая последняя из по...Программа поиска в ширину более эффективная, чем
Программа поиска в ширину более эффективная, чем программа рис.11.10. Усовершенствование основано на разностном представлении списка путей-кандидатов. (1) Начинаем с начального множества кандидато...Отношение paсширить( путь, дер, дер1, естьреш, решение):
Отношение paсширить( Путь, Дер, Дер1, ЕстьРеш, Решение) : s - стартовая вершина, g - целевая вершина. Решение - это Путь , продолженный вплоть до g . Дер1 - результат расширения дерева Дер на один...Реализация поиска в ширину с использованием
Реализация поиска в ширину с использованием древовидного представления множества путей-кандидатов. Мы разработали эту более сложную реализацию поиска в ширину не только для того, чтобы получать пр...Упражнения
Упражнения Перепишите программу поиска в ширину рис. 11.10, используя разностное представление для списка путей-кандидатов и покажите, что в результате получится программа, приведенная на рис. 11....Замечания относительно поиска в графах, оптимальности к сложности
Замечания относительно поиска в графах, оптимальности к сложности Сейчас уместно сделать ряд замечаний относительно программ поиска, разработанных к настоящему моменту: во-первых, о поиске в графа...Пространство состояний; а - стартовая вершина.
(а) Пространство состояний; а - стартовая вершина. (b) Дерево всех возможных ациклических путей, ведущих из а , порожденное программой поиска в ширину. длин - самые короткие решения идут первыми....Резюме
Резюме Пространство состояний есть формализм для представления задач. Пространство состояний - это направленный граф, вершины которого соответствуют проблемным ситуациям, а дуги - возможным ходам....Литература
Литература Поиск в глубину и поиск в ширину - базовые стратегии поиска, они описаны в любом учебнике по искусственному интеллекту, см., например, Nilsson (1971, 1980) или Winston (1984). Р. Коваль...







Содержаие