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

X = а; X = b; X = с; X = d

Теперь рассмотрим вопрос об эффективности. Цель

внутри( а, T)

достигается сразу же после применения первого предложения процедуры внутри. С другой стороны, цель

внутри( d, T)

будет успешно достигнута только после нескольких рекурсивных обращений. Аналогично цель

внутри( e, T)

потерпит неудачу только после того, как будет просмотрено все дерево в результате рекурсивного применения процедуры внутрико всем поддеревьям дерева T.

В этом последнем случае мы видим такую же неэффективность, как если бы мы представили множество просто списком. Положение можно улучшить, если между элементами множества существует отношение порядка. Тогда можно упорядочить данные в дереве слева направо в соответствии с этим отношением.

Рис. 9.6. Двоичный справочник. Элемент 6 найден после прохода по отмеченному пути 5→8→6.

Будем говорить, что непустое дерево дер( Лев, X, Прав)упорядочено слева направо, если

(1) все вершины левого поддерева Левменьше X;

(2) все вершины правого поддерева Правбольше X;

(3) оба поддерева упорядочены.

Будем называть такое двоичное дерево двоичным справочником . Пример показан на рис. 9.6.

Преимущество упорядочивания состоит в том, что для поиска некоторого объекта в двоичном справочнике всегда достаточно просмотреть не более одного поддерева. Экономия при поиске объекта X достигается за счет того, что, сравнив X с корнем, мы можем сразу же отбросить одно из поддеревьев. Например, пусть мы ищем элемент 6 в дереве, изображенной на рис. 9.6. Мы начинаем с корня 5, сравниваем 6 с 5, получаем 6 > 5. Поскольку все элементы данных в левом поддереве должны быть меньше, чем 5, единственная область, в которой еще осталась возможность найти элемент 6, — это правое поддерево. Продолжаем поиск в правом поддереве, переходя к вершине 8, и т.д.

Общий метод поиска в двоичном справочнике состоит в следующем:

Для того, чтобы найти элемент X в справочнике Д, необходимо:

• если X — это корень справочника Д, то считать, что X уже найден, иначе

• если X меньше, чем корень, то искать X в левом поддереве, иначе

• искать X в правом поддереве;

• если справочник Д пуст, то поиск терпит неудачу.

Эти правила запрограммированы в виде процедуры, показанной на рис. 9.7. Отношение больше( X, Y), означает, что X больше, чем Y. Если элементы, хранимые в дереве, — это числа, то под "больше, чем" имеется в виду просто X > Y.

Существует способ использовать процедуру внутритакже и для построения двоичного справочника. Например, справочник Д, содержащий элементы 5, 3, 8, будет построен при помощи следующей последовательности целей:

?- внутри( 5, Д), внутри( 3, Д), внутри( 8, Д).

Д = дер( дер( Д1, 3, Д2), 5, дер( Д3, 8, Д4) ).

Переменные Д1, Д2, Д3 и Д4 соответствуют четырем неопределенным поддеревьям. Какими бы они ни были, все равно дерево Д будет содержать заданные элементы 3, 5 и 8. Структура построенного дерева зависит от того порядка, в котором указываются цели (рис. 9.8).

внутри( X, дер( _, X, _ ).

внутри( X, дер( Лев, Корень, Прав) ) :-

больше( Корень, X), % Корень больше, чем X

внутри( X, Лев). % Поиск в левом поддереве

внутри( X, дер( Лев, Корень, Прав) ) :-

больше( X, Корень), % X больше, чем корень

внутри( X, Прав). % Поиск в правом поддереве

Рис. 9.7. Поиск элемента X в двоичном справочнике.

Рис. 9.8. (а) Дерево Д, построенное как результат достижения целей: внутри( 5, Д), внутри( 3, Д), внутри( 8, Д). (b) Дерево, полученное при другом порядке целей: внутри( 5, Д), внутри( 3, Д), внутри( 8, Д).

Здесь уместно сделать несколько замечаний относительно эффективности поиска в справочниках. Вообще говоря, поиск элемента в справочнике эффективнее, чем поиск в списке. Но насколько? Пусть n — число элементов множества. Если множество представлено списком, то ожидаемое время поиска будет пропорционально его длине n . В среднем нам придется просмотреть примерно половину списка. Если множество представлено двоичным деревом, то время поиска будет пропорционально глубине дерева. Глубина дерева — это длина самого длинного пути между корнем и листом дерева. Однако следует помнить, что глубина дерева зависит от его формы.