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




Глава 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). Р. Коваль...








Начало