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

Здесь есть возможность читать онлайн «Иван Братко - Программирование на языке Пролог для искусственного интеллекта» весь текст электронной книги совершенно бесплатно (целиком полную версию без сокращений). В некоторых случаях можно слушать аудио, скачать через торрент в формате fb2 и присутствует краткое содержание. Город: Москва, Год выпуска: 1990, ISBN: 1990, Издательство: Мир, Жанр: Программирование, на русском языке. Описание произведения, (предисловие) а так же отзывы посетителей доступны на портале библиотеки ЛибКат.

Программирование на языке Пролог для искусственного интеллекта: краткое содержание, описание и аннотация

Предлагаем к чтению аннотацию, описание, краткое содержание или предисловие (зависит от того, что написал сам автор книги «Программирование на языке Пролог для искусственного интеллекта»). Если вы не нашли необходимую информацию о книге — напишите в комментариях, мы постараемся отыскать её.

Книга известного специалиста по программированию (Югославия), содержащая основы языка Пролог и его приложения для решения задач искусственного интеллекта. Изложение отличается методическими достоинствами — книга написана в хорошем стиле, живым языком. Книга дополняет имеющуюся на русском языке литературу по языку Пролог.
Для программистов разной квалификации, специалистов по искусственному интеллекту, для всех изучающих программирование.

Программирование на языке Пролог для искусственного интеллекта — читать онлайн бесплатно полную книгу (весь текст) целиком

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

Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

13.2. Определите на Прологе И/ИЛИ-пространство для задачи "ханойская башня" и примените к нему процедуры поиска настоящего раздела.

13.3. Рассмотрите какую-нибудь простую детерминированную игру двух лиц с полной информацией и дайте определение ее И/ИЛИ-представления. Используйте программу поиска в И/ИЛИ-графах для построения выигрывающих стратегий в форме И/ИЛИ-деревьев.

13.4. Поиск с предпочтением в И/ИЛИ-графах

13.4.1. Эвристические оценки и алгоритм поиска

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

Начнем с того, что сформулируем критерий оптимальности, основанный на стоимостях дуг И/ИЛИ-графа. Во-первых, мы расширим наше представление И/ИЛИ-графов, дополнив его стоимостями дуг. Например, И/ИЛИ-граф рис. 13.4 можно представить следующими предложениями:

а ---> или : [b/1, с/3].

b ---> и : [d/1, e/1].

с ---> и : [f/2, g/1].

e ---> или : [h/6].

f ---> или : [h/2, i/3].

цель( d). цель( g). цель( h).

Стоимость решающего дерева мы определим как сумму стоимостей его дуг. Цель оптимизации - найти решающее дерево минимальной стоимости. Как и раньше, иллюстрацией служит рис. 13.4.

Будет полезным определить стоимость вершины И/ИЛИ-графа как стоимость оптимального решающего дерева для этой вершины. Стоимость вершины, определенная таким образом, соответствует "трудности" соответствующей задачи.

Мы будем предполагать, что стоимости вершин И/ИЛИ-графа можно оценить (не зная соответствующих решающих деревьев) при помощи эвристической функции h . Эти оценки будут использоваться для управления поиском. Наша программа поиска начнет свою работу со стартовой вершины и, распространяя поиск из уже просмотренных вершин на их преемников, будет постепенно наращивать дерево поиска. Этот процесс будет строить дерево даже в том случае, когда сам И/ИЛИ-граф не является деревом; при этом граф будет разворачиваться в дерево за счет дублирования своих отдельных частей.

Для продолжения поиска будет всегда выбираться "наиболее перспективное" решающее дерево-кандидат. Каким же образом используется функция h для оценки степени перспективности решающего дерева-кандидата или, точнее, вершины-кандидата — корня этого дерева?

Рис 139 Получение оценки H трудности задач ИИЛИграфа Обозначим через HВ - фото 94

Рис. 13.9. Получение оценки H трудности задач И/ИЛИ-графа.

Обозначим через H(В) оценку трудности вершины В . Для самой верхней вершины текущего дерева поиска H(В) просто совпадает с h(В) . С другой стороны, для оценки внутренней вершины дерева поиска нам не обязательно использовать непосредственно значение h , поскольку у нас есть некоторая дополнительная информация об этой вершине: мы знаем ее преемников. Следовательно, как показано на рис. 13.9, мы можем приближенно оценить трудность внутренней ИЛИ-вершины как

где с(В, В i) — стоимость дуги, ведущей из В в В i . Взятие минимума в этой формуле оправдано тем обстоятельством, что для того, чтобы решить задачу В , нам нужно решить только одну из ее задач-преемников. Трудность И-вершины В можно приближенно оценить так:

Будем называть H оценку внутренней вершины возвращенной backedup оценкой - фото 95

Будем называть H -оценку внутренней вершины "возвращенной" (backed-up) оценкой.

Более практичной с точки зрения использования в нашей программе поиска является другая величина F , которую можно определить в терминах H следующим образом. Пусть В1 — вершина-предшественник вершины В в дереве поиска, причем стоимость дуги, ведущей из В1 в В , равна с(В1, В) , тогда положим

Читать дальше
Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

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

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


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

Обсуждение, отзывы о книге «Программирование на языке Пролог для искусственного интеллекта» и просто собственные мнения читателей. Оставьте ваши комментарии, напишите, что Вы думаете о произведении, его смысле или главных героях. Укажите что конкретно понравилось, а что нет, и почему Вы так считаете.

x