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

• Сбалансированные или приближенно сбалансированные деревья гарантируют эффективное выполнение трех основных операций над деревьями: поиск, добавление и удаление элемента. Время выполнения этих операций пропорционально log n, где n — число вершин дерева.

Литература

2-3 деревья детально описаны, например, в Aho, Hopcroft and Ullman (1974, 1983). В книге этих авторов, вышедшей в 1983 г., дается также реализация соответствующих алгоритмов на языке Паскаль. H.Вирт (см. Wirth (1976)) приводит программу на Паскале для работы с AVL-деревьями. 2-3 деревья являются частным случаем более общего понятия В-деревьев. В-деревья, а также несколько других вариантов структур данных, имеющих отношение к 2-3 деревьям в AVL-деревьям, рассматриваются в книге Gonnet (1984). В этой книге, кроме того, даны результаты анализа поведения этих структур.

Программа вставления элемента в AVL-дерево, использующая только величину "перекоса" дерева (т.е. значение разности глубин поддеревьев, равной -1, 0 или 1, вместо самой глубины) опубликована ван Эмденом (1981).

Aho А. V., Hopcroft J. E. and Ullman J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. [Имеется перевод: Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. Пер. с англ. — М.: Мир, 1979.]

Aho А. V., Hopcroft J. E. and Ullman J. D. (1983). Data Structures and Algorithms. Addison-Wesley.

Gonnet G. H. (1984). Handbook of Algorithms + Data Structures. Addison-Wesley.

van Emden M. (1981). Logic Programming Newsletter 2.

Wirth N. (1976). Algorithms + Data Structures = Programs. Prentice-Hall. [Имеется перевод: Вирт H. Алгоритмы + структуры данных = программы. — M.: Мир, 1985.] 

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

В данной главе мы сосредоточим свое внимание на одной общей схеме для представления задач, называемой пространством состояний. Пространство состояний — это граф, вершины которого соответствуют ситуациям, встречающимся в задаче ("проблемные ситуации"), а решение задачи сводится к поиску пути в этом графе. Мы изучим на примерах, как формулируются задачи в терминах пространства состояний, а также обсудим общие методы решения задач, представленных в рамках этого формализма. Процесс решения задачи включает в себя поиск в графе, при этом, как правило, возникает проблема, как обрабатывать альтернативные пути поиска. В этой главе будут представлены две основные стратегии перебора альтернатив, а именно поиск в глубину и поиск в ширину.

11.1. Предварительные понятия и примеры

Рассмотрим пример, представленный на рис. 11.1. Задача состоит в выработке плана переупорядочивания кубиков, поставленных друг на друга, как показано на рисунке. На каждом шагу разрешается переставлять только один кубик. Кубик можно взять только тогда, когда его верхняя поверхность свободна. Кубик можно поставить либо на стол, либо на другой кубик. Для того, чтобы построить требуемый план, мы должны отыскать последовательность ходов, реализующую заданную трансформацию.

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

• поставить А на стол или

• поставить А на С, или

• поставить С на А.

Рис. 11.1. Задача перестановки кубиков.

Ясно, что альтернативу "поставить С на стол" не имело смысла рассматривать всерьез, так как этот ход никак не влияет на ситуацию.

Как показывает рассмотренный пример, с задачами такого рода связано два типа понятий:

(1) Проблемные ситуации.

(2) Разрешенные ходы или действия, преобразующие одни проблемные ситуации в другие.

Проблемные ситуации вместе с возможными ходами образуют направленный граф, называемый пространством состояний. Пространство состояний для только что рассмотренного примера дано на рис. 11.2. Вершины графа соответствуют проблемным ситуациям, дуги — разрешенным переходам из одних состояний в другие. Задача отыскания плана решения задачи эквивалентна задаче построения пути между заданной начальной ситуацией ("стартовой" вершиной) и некоторой указанной заранее конечной ситуацией, называемой также целевой вершиной.