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

• в3( Д1, M2, Д2, М3, Д3) представляет дерево с тремя поддеревьями Д1, Д2 и Д3; M2 — минимальный элемент из Д2; М3 — минимальный элемент из Д3; Д1, Д2 и Д3 — 2-3 деревья.

Между доб23 и встав существует следующая связь: если после вставления нового элемента дерево не "вырастает", то

доб23( Дер, X, НовДер) :-
 встав( Дер, X, НовДер).

Однако если после вставления элемента глубина дерева увеличивается, то встав порождает два поддерева Д1 и Д2, а затем составляет из них дерево большей глубины:

доб23( Дер, X, в2( Д1, М, Д2) ) :-
 встав( Дер, X, Д1, М, Д2).

Отношение встав устроено более сложным образом, поскольку ему приходится иметь дело со многими случаями, а именно вставление в пустое дерево, в дерево, состоящее из одного листа, и в деревья типов в2 и в3. Возникают также дополнительные подслучаи, так как новый элемент можно вставить в первое, либо во второе, либо в третье поддерево. В связи с этим мы определим встав как набор правил таким образом, чтобы каждое предложение процедуры встав имело дело с одним из этих случаев. На рис. 10.5 показаны некоторые из возможных случаев. На Пролог они транслируются следующим образом:

Случай а

 встав( в2( Д1, M, Д2), X, в2( НД1, M, Д2) ) :-
 больше( M, X), % M больше, чем X
 встав( Д1, X, НД1).

Случай b

 встав( в2( Д1, M, Д2), X, в3( НД1а, Мб, НД1б, M, Д2) ) :-
 больше( M, X),
 встав( Д1, X, НД1а, Мб, НД1б).

Случай с

 встав( в3( Д1, M2, Д2, М3, Д3), X,
 в2( НД1а, Мб, НД1б), M2, в2(Д2, М3, Д3) ) :-
 больше( M2, X),
 встав( Д1, X, НД1а, Мб, НД1б).

Рис. 10.5. Некоторые из случаев работы отношения встав. (a) встав( в2( Д1, М, Д2), X, в2( НД1, М, Д2) ); (b) встав( в2( Д1, М, Д2), X, в3( НД1а, Мб, НД1б, М, Д2) ); (c) встав( в3( Д1, M2, Д2, М3, Д3), X, в2( НД1а, Мб, НД1б), M2, в2( Д2, М3, Д3) ). 

% Вставление элемента в 2-3 справочник
доб23( Дер, X, Дер1) :- % Вставить X в Дер, получить Дер1
 встав( Дер, X, Дер1). % Дерево растет вширь
доб23( Дер, X, в2( Д1, M2, Д2) ) :-
 встав( Дер, X, Д1, M2, Д2). % Дерево растет вглубь
доб23( nil, X, л( X) ).

встав( л( А), X, л( А), X, л( X) ) :-
 больше( X, А).
встав( л( А), X, л( X), А, л( А) ) :-
 больше( А, X).
встав( в2( Д1, М, Д2), X, в2( НД1, М, Д2) ) :-
 больше( М, X),
 встав( Д1, X, НД1).
встав( в2( Д1, М, Д2), X, в3( НД1а, Мб, НД1б, М, Д2) ) :-
 больше( М, X),
встав( Д1, X, НД1а, Мб, НД1б).
встав( в2( Д1, М, Д2), X, в2( Д1, М, НД2) ) :-
 больше( X, М),
 встав( Д2, X, НД2).
встав( в2( Д1, М, Д2), X, в3( Д1, М, НД2а, Мб, НД2б) ) :-
 больше( X, М),
 встав( Д2, X, НД2а, Мб, НД2б).
встав( в3( Д1, M2, Д2, М3, Д3), X,
 в3( НД1, M2, Д2, М3, Д3) :-
 больше( M2, X),
 встав( Д1, X, НД1).
встав( в3( Д1, M2, Д2, М3, Д3), X,
 в2( НД1а, Мб, НД1б), M2, в2( Д2, М3, Д3) ) :-
 больше( M2, X),
 встав( Д1, X, НД1а, Мб, НД1б).
встав( в3( Д1, M2, Д2, М3, Д3), X,
 в3( Д1, M2, НД2, М3, Д3) ) :-
 больше( X, M2), больше( М3, X),
 встав( Д2, X, НД2).
встав( в3( Д1, M2, Д2, М3, Д3), X,
 в2( Д1, M2, НД2а), Мб, в2( НД2б, М3, Д3) ) :-
 больше( X, M2), больше( М3, X),
 встав( Д2, X, НД2а, Мб, НД2б).
встав( в3( Д1, M2, Д2, М3, Д3), X,
 в3( Д1, M2, Д2, М3, НД3) ) :-
 больше( X, М3),
 встав( Д3, X, НД3).
встав( в3( Д1, M2, Д2, М3, Д3), X,
 в2( Д1, M2, Д2), М3, в2( НД3а, Мб, НД3б) ) :-
 больше( X, М3),
 встав( Д3, X, НД3а, Мб, НД3б).

Рис. 10.6. Вставление элемента в 2-3 справочник. В этой программе предусмотрено, что попытка повторного вставления элемента терпит неудачу.

Программа для вставления нового элемента в 2-3 справочник показана полностью на рис. 10.6. На рис. 10.7 показана программа вывода на печать 2-3 деревьев.

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

встав2( Дер, X, Деревья)

где Деревья — список, состоящий либо из одного, либо из трех аргументов:

 Деревья = [ НовДер], если встав( Дер, X, НовДер)

Деревья = [ НДа, Мб, НДб], 

 если встав( Дер, X, НДа, Мб, НДб)

Теперь отношение доб23 можно переопределить так:

доб23( Д, X, Д1) :-
 встав( Д, X, Деревья),
 соединить( Деревья, Д1).

Отношение соединить формирует одно дерево Д1 из деревьев, находящихся в списке Деревья.