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




Глава 9. Пролог в искусственном интеллекте


    Представление списков. Сортировка
    Представление списков. Сортировка Замечания в некоторых альтернативных способах представления списков 1. Замечания в некоторых альтернативных способах представления списков В главе 3 была введена...
    Упражнения
    Упражнения Определите отношение список( Объект) для распознавания случаев, когда Объект является стандартным прологовским списком. Посмотреть ответ Определите отношение принадлежности к списку, ис...
    Сортировка списка процедурой быстрсорт.
    Сортировка списка процедурой быстрсорт . встав( X, [Y | УпорСпис], [Y | УпорСпис1]):- больше( X, Y), !, встав( X, УпорСпис, УпорСпис1). встав( X, УпорСпис, [X | УпорСпис] ). Процедуры сортировки п...
    Быстрая сортировка.
    Быстрая сортировка. становится тривиальной операцией после применения разностного представления списков, введенного в гл. 8. Для того, чтобы использовать эту идею в нашей процедуре сортировки, нуж...
    Более эффективная реализация процедуры быстрсорт
    Более эффективная реализация процедуры быстрсорт с использованием разностного представления списков. Отношение разбиение( Х, Спис, Меньш, Больш) определено, как на рис. 9.2. быстрсорт2 . Здесь, ка...
    Упражнения
    Упражнения Напишите процедуру слияния двух упорядоченных списков в один третий список. Например: ?- слить( [2, 5, 6, 6, 8], [1, 3, 5, 9], L). L = [1, 2, 3, 5, 5, 6, 6, 8, 9] Программы сортировки,...
    Представление множеств двоичными деревьями
    Представление множеств двоичными деревьями Списки часто применяют для представления множеств. Такое использование списков имеет тот недостаток, что проверка принадлежности элемента множеству оказы...
    Двоичное дерево.
    Двоичное дерево. Существует более эффективный и более привычный способ представления двоичных деревьев: нам нужен специальный символ для обозначения пустого дерева и функтор для построения непусто...
    Представление двоичных деревьев.
    Представление двоичных деревьев. Эти правила непосредственно транслируются на Пролог следующим образом: внутри( X, дер( -, X, -) ). внутри( X, дер( L, -, -) ) :- внутри( X, L). внутри( X, дер( -,...
    Двоичный справочник. Элемент 6 найден после прохода по отмеченному пути 5-->8-->6.
    Двоичный справочник. Элемент 6 найден после прохода по отмеченному пути 5--8--6. Будем говорить, что непустое дерево дер( Лев, X, Прав) упорядочено слева направо, если (1) все вершины левого подде...
    Поиск элемента х в двоичном справочнике.
    Поиск элемента Х в двоичном справочнике....
    (а) дерево д, построенное как...
    (а) Дерево Д , построенное как результат достижения целей: внутри( 5, Д) , внутри( 3, Д) , внутри( 8, Д) . (b) Дерево, полученное при другом порядке целей: внутри( 5, Д) , внутри( 3, Д) , внутри(...
    Упражнения
    Упражнения Определите предикаты двдерево( Объект) справочник( Объект) распознающие, является ли Объект двоичным деревом или двоичным справочником соответственно. Используйте обозначения, введенные...
    Двоичные справочники: добавление и удаление элемента
    Двоичные справочники: добавление и удаление элемента Если мы имеем дело с динамически изменяемым множеством элементов данных, то нам может понадобиться внести в него новый элемент или удалить из н...
    Введение в двоичный справочник...
    Введение в двоичный справочник нового элемента на уровне листьев. Показанные деревья соответствуют следующей последовательности вставок: добавить( Д1, 6, Д2), добавить( Д2, 6, Д3), добавить( Д3, 6...
    Вставление в двоичный справочник нового элемента в качестве листа.
    Вставление в двоичный справочник нового элемента в качестве листа . Определим отношение добавить. Простейший способ: ввести новый элемент на самый нижний уровень дерева, так что он станет его лист...
    Удаление x из двоичного справочника. Возникает проблема наложения "заплаты" на место удаленного элемента x.
    Удаление X из двоичного справочника. Возникает проблема наложения заплаты на место удаленного элемента X. операции добавления листа: удлист( Д1, X, Д2) :- доблист( Д2, X, Д1). К сожалению, если Х...
    Заполнение пустого места после удаления x.
    Заполнение пустого места после удаления X. то можно использовать следующую идею (рис. 9.12): если самую левую вершину Y поддерева Прав переместить из ее текущего положения вверх и заполнить ею про...
    Удаление элемента из двоичного справочника.
    Удаление элемента из двоичного справочника. line(); Для того, чтобы добавить Х в двоичный справочник Д, необходимо одно из двух: добавить Х на место корня дерева (так, что Х станет новым корнем) и...
    Внесение х в двоичный справочник в качестве корня.
    Внесение Х в двоичный справочник в качестве корня. Ответ мы получим, если учтем следующие ограничения на L1, L2: L1 и L2 - двоичные справочники; множество всех вершин, содержащихся как в L1, так и...
    Внесение элемента на произвольный уровень двоичного справочника.
    Внесение элемента на произвольный уровень двоичного справочника. На рис. 9.15 показана программа для недетерминированного добавления элемента в двоичный справочник. Эта процедура обладает тем заме...
    Отображение деревьев
    Отображение деревьев Так же, как и любые объекты данных в Прологе, двоичное дерево Т может быть непосредственно выведено на печать при помощи встроенной процедуры write . Однако цель write( Т) хот...
    (а) обычное изображение дерева. (b) то же дерево,
    (а) Обычное изображение дерева. (b) То же дерево, отпечатанное процедурой отобр (дуги добавлены для ясности). Давайте определим процедуру отобр( Т) так, чтобы она отображала дерево в форме, показа...
    Отображение двоичного дерева.
    Отображение двоичного дерева....
    Упражнение
    Упражнение 9. 14. Наша процедура изображает дерево, ориентируя его необычным образом: корень находится слева, а листья - справа. Напишите (более сложную) процедуру для отображения дерева, ориентир...
    Графы
    Графы Представление графов 1. Представление графов Графы используются во многих приложениях, например для представления отношений, ситуаций или структур задач. Граф определяется как множество верш...
    (а) граф. (b) направленный граф. Каждой дуге приписана ее стоимость.
    (а) Граф. (b) Направленный граф. Каждой дуге приписана ее стоимость. Для представления направленного графа (рис. 9.18), применив функторы диграф и д (для дуг), получим G2 = диграф( [s, t, u, v], [...
    Поиск в графе граф ациклического пути путь из а в z.
    Поиск в графе Граф ациклического пути Путь из А в Z. На рис. 9.20 программа показана полностью. Здесь принадлежит - отношение принадлежности элемента списку. Отношение смеж( X, Y, G) означает, что...
    Поиск пути в графе: путь - путь между а и z в графе граф стоимостью ст.
    Поиск пути в графе: Путь - путь между А и Z в графе Граф стоимостью Ст. Эту процедуру можно использовать для нахождения пути минимальной стоимости. Мы можем построить путь минимальной стоимости ме...
    Построение остовного дерева: "декларативный подход".
    Построение остовного дерева: декларативный подход. Отношения вершина и смеж см. на рис. 9. 22....
    Упражнение
    Упражнение 9. 15. Рассмотрите остовные деревья в случае, когда каждому ребру графа приписана его стоимость. Пусть стоимость остовного дерева определена как сумма стоимостей составляющих его ребер....
    Резюме
    Резюме В данной главе мы изучали реализацию на Прологе некоторых часто используемых структур данных и соответствующих операций над ними. В том числе Списки: варианты представления списков сортиров...
    Литература
    Литература В этой главе мы занимались такими важными темами, как сортировка и работа со структурами данных для представления множеств. Общее описание структур данных, а также алгоритмов, запрограм...








Начало    



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