Философские аспекты проблемы систем ИИ



         

ПРЕДСТАВЛЕНИЕ МНОЖЕСТВ С ПОМОЩЬЮ БИНАРНЫХ ДЕРЕВЬЕВ


Описание множеств в виде списков позволяет использовать для множеств целевое утверждение принадлежит, определенное ранее для списков.

Однако для множеств, состоящих из большого числа элементов, списковые целевые утверждения становятся неэффективными. Рассмотрим, например, как целевое утверждение принадлежит (см. предыдущий разд.) позволяет моделировать принадлежность множеству. Пусть L - список, описывающий множество из первых 1024 натуральных чисел. Тогда при ответе на запрос

?- принадлежит(3000, b).

Прологу придется проверить все 1024 числа, прежде чем заключить, что такого числа нет:

нет

Представление множества бинарным деревом позволяет добиться лучшего результата. При этом бинарное дерево должно быть упорядочено таким образом, чтобы любой элемент в левом поддереве был меньше, чем значение корня, а любой элемент в правом поддереве — больше. Поскольку мы определили поддерево как бинарное дерево, такое упорядочение применяется по всем поддеревьям. На Рис. 3 приведен пример упорядоченного бинарного дерева.

Дерево на Рис. 2 является неупорядоченным.



Рис. 3 - Упорядоченное бинарное дерево.

Обратите внимание, что упорядочение приводит не к единственному варианту представления множества с помощью дерева. Например, на Рис. 4 изображено то же множество, что и на Рис. 3.

Будем называть линейным представление такого вида, как на Рис. 4, и сбалансированным - такое, как на Рис. 3.



Рис. 4 - Линейное представление.

Моделирование принадлежности множеству. Имея множество, описанное бинарным деревом, мы можем моделировать принадлежность множеству с помощью целевого утверждения принадлежит_дереву. При этом используется оператор @<, выражающий отношение “меньше, чем”, и оператор @>, выражающий отношение “больше, чем”.

/* Граничное условие: Х принадлежит

/* дереву, если Х является корнем.

принадлежит_дереву(Х, бд(Лд, Х, Пд)),

/* Рекурсивные условия

/* Х принадлежит дереву, если Х больше

/* значении корня и находится в правом

/* поддереве:

принадлсжит_дереву(Х, бд(Лд, У, Пд)) :- X@Y,




Содержание  Назад  Вперед