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




Глава 13. Сведение задач к подзадачам.


    Глава 13. Сведение задач к подзадачам.
    Глава 13 СВЕДЕНИЕ ЗАДАЧ К ПОДЗАДАЧАМ. И / ИЛИ- ГРАФЫ Представление в виде И / ИЛИ-графов наиболее хорошо приспособлено для задач, которые естественным образом разбиваются на взаимно независимые по...
    Представление задач в виде и / или-графов
    Представление задач в виде И / ИЛИ-графов В главах 11 и 12, говоря о решении задач, мы сконцентрировали свое внимание на пространстве состояний как средстве представления этих задач. В соответстви...
    Поиск маршрута из а в z на карте дорог. Через реку
    Поиск маршрута из а в z на карте дорог. Через реку можно переправиться в городах f и g. И / ИЛИ-представление этой задачи показано на рис. 13.2. странстве состояний. Соответствующее пространство с...
    И / или-представление задачи поиска маршрута рис. 13.1.
    И / ИЛИ-представление задачи поиска маршрута рис. 13.1. Вершины соответствуют задачам или подзадачам, полукруглые дуги означают, что все (точнее, обе) подзадачи должны быть решены. Теперь каждую и...
    Решить р - это значит решить р1 или р2 или ... (б) решить q - это значит решить все: q1 и q2 и ... .
    (а) Решить Р - это значит решить Р1 или Р2 или ... (б) Решить Q - это значит решить все: Q1 и Q2 и ... . Итак, мы имеем две главных альтернативы для решения исходной задачи: (1) путь через f или (...
    Пример и / или-графа: d, g и h...
    (а) Пример И / ИЛИ-графа: d, g и h - целевые вершины; a - исходная задача. (b) и (с) Два решающих дерева, стоимости которых равны 9 и 8 соответственно. Здесь стоимость решающего дерева определена...
    Примеры и/или-представления задач
    Примеры И/ИЛИ-представления задач И / ИЛИ-представление задачи поиска маршрута 1. И / ИЛИ-представление задачи поиска маршрута Для задачи отыскания кратчайшего маршрута (рис. 13.1) И / ИЛИ-граф вм...
    Решающее дерево минимальной стоимости для задачи поиска маршрута рис. 13.1, сформулированной в терминах и / или- графа.
    Решающее дерево минимальной стоимости для задачи поиска маршрута рис. 13.1, сформулированной в терминах И / ИЛИ- графа. 13.5 показан решающий граф, имеющий стоимость 9. Это дерево соответствует пу...
    Задача о ханойской башне
    Задача о ханойской башне Порядок этот можно установить при помощи следующего рассуждения: самая трудная цель - это цель 3 (диск с - на колышек 3), потому что на диск с наложено больше всего ограни...
    Формулировка игровой задачи для...
    Формулировка игровой задачи для игры двух лиц в форме И / ИЛИ-дерева; участники игры: игрок и противник. та хода противника. Другими словами, игрок выигрывает в Qi, если он выигрывает во всех пози...
    Базовые процедуры поиска в и / или-графах
    Базовые процедуры поиска в И / ИЛИ-графах В этом разделе нас будет интересовать какое-нибудь решение задачи независимо от его стоимости, поэтому проигнорируем пока стоимости связей или вершин И /...
    Поиск в глубину для и / или-графов...
    Поиск в глубину для И / ИЛИ-графов. Эта программа может зацикливаться. Процедура решить находит решающее дерево, а процедура отобр показывает его пользователю. В процедуре отобр предполагается, чт...
    Упражнения
    Упражнения Закончите составление программы поиска в глубину (с ограничением) для И / ИЛИ-графов, намеченную в настоящем разделе. Определите на Прологе И / ИЛИ-пространство для задачи ханойская баш...
    Поиск с предпочтением в и / или-графах
    Поиск с предпочтением в И / ИЛИ-графах Эвристические оценки и алгоритм поиска 1. Эвристические оценки и алгоритм поиска Базовые процедуры поиска предыдущего раздела производят систематический и по...
    Получение оценки н трудности задач и / или-графа.
    Получение оценки Н трудности задач И / ИЛИ-графа. Обозначим через Н( В) оценку трудности вершины В. Для самой верхней вершины текущего дерева поиска H( В) просто совпадает с h( В). С другой сторон...
    Трассировка процесса поиска с предпочтением в и / или-графе ( h = 0) при решении задачи рис. 13.4.
    Трассировка процесса поиска с предпочтением в И / ИЛИ-графе ( h = 0) при решении задачи рис. 13.4. прекращается. В результате процесс поиска не успевает осознать, что h - это тоже целевая вершина...
    Представление дерева поиска.
    Представление дерева поиска. можностей имеется в виду. Это может быть одна из следующих комбинаций: лист решлист дер решдер Далее, в представление дерева входят все или некоторые из следующих объе...
    Программа поиска с предпочтением в и / или-графе.
    Программа поиска с предпочтением в И / ИЛИ-графе. Еще одна процедура собрать( ОстДер, НовДер, ЕстьРеш1, НовДеревья, ЕстьРеш) связывает между собой несколько объектов, с которыми работает расширспи...
    Упражнение
    Упражнение Напишите процедуру отобр2( РешДер) для отображения решающего дерева, найденного программой и_или рис. 13.12. Формат отображения пусть будет аналогичен тому, что применялся в процедуре о...
    Резюме
    Резюме И / ИЛИ-граф - это формальный аппарат для представления задач. Такое представление является наиболее естественным и удобным для задач, которые разбиваются на независимые подзадачи. Примером...
    Литература
    Литература И / ИЛИ-графы и связанные с ними алгоритмы поиска являются частью классических механизмов искусственного интеллекта для решения задач и реализации машинных игр. Ранним примером прикладн...








Начало    



Книжный магазин