Автор: Сотник С.Л.

ПРЕДСТАВЛЕНИЕ БИНАРНЫХ ДЕРЕВЬЕВ

Бинарное дерево определяется рекурсивно как имеющее левое поддерево, корень и правое поддерево. Левое и правое поддеревья са¬ми являются бинарными деревьями. На Рис. 14 показан пример би¬нарного дерева.

Рис. 14. Бинарное дерево.

Такие деревья можно представить термами вида

бд(Лд, К, Пд),

где Лд - левое поддерево, К - корень, а Пд - правое поддерево. Дл» обозначения пустого бинарного дерева будем использовать атом nil. Бинарное дерево на рис.5.2.1 имеет левое подде-рево

бд(бд(nil, d, nil), b, бд(nil, е, nil))

правое поддерево

бд(nil,с, nil)

и записывается целиком как

бд(бд(бд(nil,d, nil), b, бд(nil,е, nil)), а, бд(nil, с, nil)).

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

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

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

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

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

нет

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если множество из первых 1024 чисел описать с помощью сба¬лансированного бинарно-го дерева Т, то при ответе на запрос

?- принадлежит_дереву(3000, Т).

Пролог сравнит число 3000 не более чем с 11 элементами множества. прежде чем отве-тит:

нет

Конечно, если Т имеет линейное представление, то потребуется сравнение 3000 с 1024 элементами множества.

Построение бинарного дерева. Задача создания упорядоченного бинарного дерева при добавлении элемента Х к другому упорядочен¬ному бинарному дереву формулируется следую-щим образом:

Граничное условие:

Добавление Х к nil дает бд(nil, Х, nil).

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

При добавлении Х к бд(Лд, К, Пд) нужно рассмотреть два случая, чтобы быть уверен-ным, что результирующее дерево будет упорядо¬ченным.

1. Х меньше,чем К. В этом случае нужно добавить Х к Лд, чтобы получить левое подде-рево. Правое поддерево равно Пд, а значение корня результирующего дерева равно К.

2. Х больше, чем К. В таком случае нужно добавить Х к Пд, что¬бы получить правое поддерево. Левое поддерево равно Лд, а значе¬ние корня - К.

Такой формулировке задачи соответствует программа:

/* Граничное условие:

включ_бд(nil, Х, бд(nil, Х, nil)).

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

/*(1)

включ_бд(бд(Лд, К, Пд), Х, бд(Лднов, К, Пд)) :-

Х@К,

включ_бд(Лд,Х,Лднов).

/*(2)

включ_бд(бд(Лд, К, Пд), Х, бд(Лд, К, Пднов)) :-

Х@К,

включ_бд(Пд, Х, Пднов).

На запрос

?- включ_бд(nil, d, Т1), включ_бд(Т1, а, Т2).

будут получены значения

Т1=бд(nil, d, nil)

Т2=бд(бд(nil, а, nil), d, nil)

Процедуру включ_бд() можно использовать для построения упо¬рядоченного дерева из списка:

/* Граничное условие:

список_в_дерево([], nil).

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

список_в_дерево([Н | Т], Бд) :-

список_в_дерево(Т, Бд2),

включ_бд(Н, Бд2, Бд).

Заметим, что включ_бд не обеспечивает построения сбалансиро¬ванного дерева. Однако существуют алгоритмы, гарантирующие та¬кое построение.

Механизм возврата и процедурная семантика

При согласовании целевого утверждения в Прологе используется метод, известный под названием механизма возврата. В этой главе мы показываем, в каких случаях применяется ме-ханизм возврата, как он работает и как им пользоваться. Описывается декларативная и проце-дурная семантика процедур Пролога. Завершается глава об¬суждением вопросов эффективности.

Механизм возврата

При попытке согласования целевого утверждения Пролог выби¬рает первое из тех ут-верждений, голова которых сопоставима с целе¬вым утверждением. Если удастся согласовать тело утверждения, то целевое утверждение согласовано. Если нет, то Пролог переходит к сле-дующему утверждению, голова которого сопоставима с целевым утверждением, и так далее до тех пор, пока целевое утверждение не будет согласовано или не будет доказано, что оно не со-гласуется с ба¬зой данных.

В качестве примера рассмотрим утверждения:

меньше(X.Y) :-

XY, write(X),

write ('меньше, чем'),write(Y).

меньше(Х.У) :-

XY, write(Y),

write ('меньше, 4CM'),write(X).

Целевое утверждение

?- меньше (5, 2).

сопоставляется с головой первого утверждения при Х=5 и У=2. Одна¬ко не удается со-гласовать первый член конъюнкции в теле утвержде¬ния X ?-меньше (2, 2).

сопоставляется с головой первого утверждения, но тело утверждения согласовать не удается. Затем происходит сопоставление с головой второго утверждения, но согласовать тело опять-таки оказывается невозможно. Поэтому попытка доказательства целевого утвержде¬ния меньше(2, 2) заканчивается неудачей.

Такой процесс согласования целевого утверждения путем прямого продвижения по про-грамме мы называем прямой трассировкой (forward tracking). Даже если целевое утверждение согласовано, с помощью прямой трассировки мы можем попытаться получить другие варианты его доказательства, т.е. вновь согласовать целевое утверждение.

Пролог производит доказательство конъюнкции целевых утверж¬дений слева направо. При этом может встретиться целевое утвержде¬ние, согласовать которое не удается. Если такое случается, то проис¬ходит смещение влево до тех пор, пока не будет найдено целевое ут¬верждение, которое может быть вновь согласовано, или не будут ис черпаны все предшествую-щие целевые утверждения. Если слева нет целевых утверждений, то конъюнкцию целевых ут-верждений согласовать нельзя. Однако, если предшествующее целевое утверждениг может быть согласовано вновь, Пролог возобновляет процесс доказа¬тельства целевых утверждений слева направо, начиная со следующе¬го справа целевого утверждения. Описанный процесс смещения вле¬во для повторного согласования целевого утверждения и возвраще¬ния вправо носит название механизма возврата.

Пример: задача поиска пути в лабиринте

В качестве примера использования механизма возврата напишем процедуру для поиска пути в лабиринте. Лабиринт представлен фак¬тами вида:

стена(I, J) для позиции в I-м ряду и J-й колонке, где есть стена

отсутств_стена(I, J) для позиции в I-м ряду и J-й колонке, где нет стены

выход (I, J) для позиции в 1-м ряду и J-й колонке, являющейся выходом

Рассмотрим небольшой лабиринт:

Последний ряд лабиринта описывается фактами:

стена(4,1).

стена(4,3).

стена(4,4).

отсутств_стена(4,2).

Если задана исходная позиция, путь к выходу можно найти сле¬дующим образом.

Граничное условие:

Если исходная позиция является выходом, то путь найден.

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

Ищем путь из исходной позиции в северном направлении. Если пути нет, идем на юг. Если пути нет, идем на запад. Если нельзя, идем на восток. Если соседняя позиция на севере (юге, западе, восто¬ке) является стеной, то нет смысла искать путь из начальной пози¬ции к выхо-ду. Чтобы не ходить кругами, будем вести список пози¬ций, в которых мы побывали.

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

/* Терм a(I, J) представляет позицию в

/* I-м ряду и J-й колонке.

/* Нашли путь ?

путь(а(I, J),[а(I, J)], Были) :- выход(I, J).

/* Пытаемся идти на север

путь(а(I, J),[а(I, J) | Р], Были) :-

К is I-1,

можем_идти(a (K, J), Были),

путь(а(I, J) ,Р, [a(K, J) | Были]).

/* Пытаемся идти на юг

путь(а(I, J),[а(I, J) | Р], Были) :-

К is I+1,

можем_идти(a (K, J), Были),

путь(а(I, J) ,Р, [a(K, J) | Были]).

/* Пытаемся идти на запад

путь(а (I, J), [a (I, J) | P], Были) :-

L is J-1,

можем_идти(а(I, L), Были),

путь(а(I, L), Р, [а(I, L)| Были]).

/* Пытаемся идти на восток

путь(а (I, J), [a (I, J) | P], Были) :-

L is J+1,

можем_идти(а(I, L), Были),

путь(а(I, L), Р, [а(I, L)| Были]).

/* в позицию a(I, J) можно попасть при

/* условии, что там нет стены и мы

/* не побывали в ней прежде

можем_идти(а(I, J)), Были) :-

отсутств_стена(I, J),

not (принадлежит (a (I, J), Были)).

Для того чтобы понять, каким образом процедура ищет путь к выходу, рассмотрим про-цесс согласования запроса с описанием лаби¬ринта, описанного выше:

?-путь(а(4,2), Р, [а(4.2)]).

Выходом из лабиринта является позиция выход (3,1).

Выбор первого утверждения не приводит к согласованию целево¬го утверждения, по-скольку а (4,2) - не выход. Во втором утверждении делается попытка найти путь в северном на-правлении, т.е. согласовать целевое утверждение

путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]).

Целевое утверждение не удается согласовать с первым утвержде¬нием

путь(а(3, 2), Р2, [а(3, 2), а(4, 2)])

так как а (3,2) не является выходом. Во втором утверждении пред¬принимается попытка найти путь, двигаясь на север, т.е. согласовать целевое утверждение

путь(а(2,2), РЗ, [а(2, 2), а(3, 2), а(4, 2)]).

Ни одно из утверждений не может согласовать

путь(а(2, 2), РЗ, [а(2, 2), а(3, 2), а(4, 2)]).

Первое утверждение - потому, что а (2, 2) не является выходом, вто¬рое - потому, что се-верная позиция является стеной, третье утверждение - потому, что в южной позиции мы уже побывали, а четвертое и пятое утверждения - потому, что западная и восточная границы - это стены.

Неудача в согласовании

путь(а(2, 2), РЗ, [а(2, 2), а(3, 2), а(4, 2)])

заставляет Пролог-систему вернуться в ту точку, где было выбрано второе утверждение при попытке согласовать

путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]).

Решение пересматривается и выбирается третье утверждение.

В третьем утверждении осуществляется попытка найти путь, двигаясь на юг, но она ока-зывается неудачной, поскольку мы уже по¬бывали в позиции а (4, 2). Тогда, чтобы согласовать

путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]),

выбирается четвертое утверждение. Мы успешно находим путь, дви¬гаясь в западном направлении к позиции а(3,1), которая и является выходом. Рекурсия сворачивается, и в резуль-тате полу¬чается путь

Р=[а(4, 2),а(3, 2), а(3,1)]

другие решения(да/нет)? да

Других решений нет

Альтернативный путь

[a(4,2), a(3,2), a(2,2), a(3,2), a(3,1)]

мы получить не можем, потому что не разрешается дважды бывать в одной и той же по-зиции.

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

Элементы нечеткой логики

Как известно, классическая логика оперирует только с двумя значениями: истина и ложь. Однако этими двумя значениями довольно сложно представить (можно, но громоздко) большое количество реальных задач. Поэтому для их решения был разработан специальный ма-тематический аппарат, называемый нечеткой логикой. Основным отличием нечеткой логики от классической, как явствует из названия, является наличие не только двух классических состоя-ний (значений), но и промежуточных: