Я изучаю Пролог с использованием SWI Prolog, и у меня есть некоторые сомнения в том, как работать с этой реализацией словаря 2-в Прологе.Некоторые сомнения в реализации Пролога 2-3 Словаря
Я знаю теорию 2-3 словаря, что деревья, чьи внутренние узлы могут генерировать 2 или 3 поддеревьев, обладающих следующими свойствами:
1) Все предметы хранятся в листьях и являются упорядоченный от меньшего к большим
2) всех листьев на том же уровне
3) внутренние узлы не мошенники tains вставленного элемента, но содержит метку, которые задают минимальные элементы поддерев следующим образом:
- Если внутренний узел имеет 2 поддерев, метка в этом внутреннем узле содержит минимальный элемент его правого поддерева (поэтому, если я ищу элемент X, который меньше, чем метка, я уверен, что он находится в левом поддереве)
- Если внутренний узел имеет 3 поддеревья, метка в этом внутреннем узле содержит 2 значения: M2 и M3, где M1 - МИНИМАЛЬНОЕ ЗНАЧЕНИЕ, которое присутствует в SUBTREE CENTER, а M3 - МИНИМАЛЬНОЕ ЗНАЧЕНИЕ, которое является правильным поддеревом
Так что поиск, если предмет существует в этом словаре, довольно прост.
Вложение сложнее, я понимаю теорию этого, но у меня есть только некоторые проблемы с интерпретацией Prolog.
Это моя программа (взять из Ивана Братко книги: Программирование искусственного интеллекта):
/* in(Item, Tree) predicate is TRUE if the searched Item is in the specified Tree */
% BASE CASE: Item found in a leaf, so end
in(Item, l(Item)).
/* CASE 1: I am searching Item in an internal node having a single label value
so this internal node have 2 subtrees
*/
in(Item, n2(T1,M,T2)) :- gt(M,Item), % IF M label value lexicographically follows the searched Item value
!,
in(Item,T1) % THEN search Item in the left subtree
; % (; is an OR)
in(Item,T2). % Otherwise search Item in the right subtree
/* CASE 2: I am searching Intem in an internal node having 2 label values so this
internal node have 3 subtrees
*/
in(Item, n3(T1,M2,T2,M3,T3)) :- gt(M2,Item), % IF M2 label value lexicographically follows the searched Item value
!,
in(Item,T1) % THEN search Item in the left subtree
; % (; is an OR)
/* IF M3 label value lexicographically follows the searched Item value
BUT this is NOT TRUE that M2>Item
*/
gt(M3,Item),
!,
in(Item,T2) % THEN search Item in the central subtree
; % (; is an OR)
in(Item,T3). % ELSE (it is TRUE that Item>M3) search in the right subtree
/*
*/
% Insertion in the 2-3 dictionary
/* Add X to Tree giving Tree1
CASE 1: After the insertion of X into Tree, Tree1 does not grow upwards (so it means that an internal nodes
having 2 subtrees child, now have 3 subtrees child, so the original tree has grown in width)
*/
add23(Tree, X, Tree1) :- ins(Tree, X, Tree1).
/* CASE 2: Tree grows upwards: It means that if after the insertion of X the height of the new tree is
increased so the ins/5 predicate determines the two subtrees T1 and T2 which are then combined
into a bigger tree
*/
add23(Tree, X, n2(T1, M2, T2)) :- ins(Tree, X, T1, M2, T2).
del23(Tree, X, Tree1) :- add23(Tree1, X, Tree). % Delete X from Tree giving Tree1
/* BASE CASE: Inserting the X item into a voil (nil) tree means to obtain a tree
consisting of the single new leaf l(X)
*/
ins(nil, X, l(X)).
/* BASE CASES: related to inserting a new item X into a tree composed by
a single leaf
*/
ins(l(A), X, l(A), X, l(X)) :- gt(X, A).
ins(l(A), X, l(X), A, l(A)) :- gt(A, X).
/* Tree = n2(T1, M , T2) so Tree is a tree having 2 subtrees T1 and T2
M: is the MINIMAL ELEMENT OF T2
IF it is TRUE that M>X (the minimal element in T2 is > the new X item)
I have to insert X in the LEFT subtrees (into T1 that becomes NT1 and
now have 2 leaves)
*/
ins(n2(T1, M , T2), X, n2(NT1, M, T2)) :- gt(M, X),
ins(T1, X, NT1).
/* Tree = n2(T1, M , T2) so Tree is a tree having 2 subtrees T1 and T2
M: is the MINIMAL ELEMENT OF T2.
IF it is TRUE that M>X (the minimal element in T2 is > the new X item) and
IF I can insert
*/
ins(n2(T1, M, T2), X, n3(NT1a, Mb, NT1b, M, T2)) :- gt(M, X),
ins(T1, X, NT1a, Mb, NT1b).
ins(n2(T1, M, T2), X, n2(T1, M, NT2)) :- gt(X, M),
ins(T2, X, NT2).
ins(n2(T1, M, T2), X, n3(T1, M, NT2a, Mb, NT2b)) :-
gt(X, M),
ins(T2, X, NT2a, Mb, NT2b).
ins(n3(T1, M2, T2, M3, T3), X, n3(NT1, M2, T2, M3, T3)) :-
gt(M2, X),
ins(T1, X, NT1).
/* Tree = n3(T1, M2, T2, M3, T3) so Tree is a tree having 3 subtree: T1,T2 and T2
and the ROOT of Tree is the node (M2,M3)
M2: MINIMAL ELEMENT of T2 subtree
M3: MINIMAL ELEMENT of T3 subtree
If I had the item X then Tree have to grow in height
IF it is TRUE that M2 > X I could try to insert the X item into T1 subtree
IF it is TRUE that X is added in T1 and T1 is splitted in NT1a and NT1b having root Mb
so the new tree is: n2(NT1a, Mb, NT1b), M2, n2(T2, M3, T3)
*/
ins(n3(T1, M2, T2, M3, T3), X, n2(NT1a, Mb, NT1b), M2, n2(T2, M3, T3)) :-
gt(M2, X),
ins(T1, X, NT1a, Mb, NT1b).
ins(n3(T1, M2, T2, M3, T3), X, n3(T1, M2, NT2, M3, T3)) :-
gt(X, M2), gt(M3, X),
ins(T2, X, NT2).
ins(n3(T1, M2, T2, M3, T3), X, n2(T1, M2, NT2a), Mb, n2(NT2b, M3, T3)) :-
gt(X, M2), gt(M3, X),
ins(T2, X, NT2a, Mb, NT2b).
ins(n3(T1, M2, T2, M3, T3), X, n3(T1, M2, T2, M3, NT3)) :-
gt(X, M3),
ins(T3, X, NT3).
ins(n3(T1, M2, T2, M3, T3), X, n2(T1, M2, T2), M3, n2(NT3a, Mb, NT3b)) :-
gt(X, M3),
ins(T3, X, NT3a, Mb, NT3b).
В этой реализации у меня есть что:
- л (X) rappresent в item настоящее время в моем дереве
- n2 (T1, M, T2) представляет дерево с 2 подстроками ess T1 и T2, где M - минимальный элемент в T2
- n3 (T1, M2, T2, M3, T3) ** представляет дерево с тремя поддеревьями: T1, T2, T3, где M2 - минимальный элемент в T2 и M3 является минимальным элементом в T3
Первое сомнение связано с отношением, которые существуют между add23 и Ins предиката этим:
/* Add X to Tree giving Tree1
CASE 1: After the insertion of X into Tree, Tree1 does not grow upwoards (so it means that an internal nodes
having 2 subtrees child, now have 3 subtrees child, so the original tree has grown in width)
*/
add23(Tree, X, Tree1) :- ins(Tree, X, Tree1).
/* CASE 2: Tree grows upwards: It meaans that if after the insertion of X the height of the new tree is
increased so the ins/5 predicate determines the two subtrees T1 and T2 wich are then combined
into a bigger tree
*/
add23(Tree, X, n2(T1, M2, T2)) :- ins(Tree, X, T1, M2, T2).
Как пишут в комментариях I думают, что первая связана с случаем, когда новое дерево не растет вверх ds (так, например, у меня было дерево с двумя поддеревьями и вставка нового элемента. Я создаю новое поддерево, у которого есть его листья на том же уровне, что и все остальные (и, следовательно, внутренний узел теперь будет иметь 2 метки). Правильно ли это ?
Таким образом, в логике я могу читать его как: если модули (дерево, X, Дерево1) предикат истинен тогда я добавить X в дерево генерации нового Дерево1, которые имеют ту же высоту старого дерева, но который содержит X (так что у него должен быть внутренний узел, имеющий 3 ребенка)
Второй случай связан в случае с wicht. У меня есть дерево, и мне нужно вставить новый элемент в узел, у которого уже есть 3 поддерева, так что Мне нужно разбить старое дерево на 2 дерева, так как корень имеет как ярлык, так и одну метку, берущую из двух ярлыков старого исходного узла. Поэтому я могу вставить новый элемент в виде листа и как новый корень нового дерева.
Таким образом, в логике можно прочитать как:
Если предикатные модули (дерево, X, T1, М2, Т2) истинно, то это означает, что это значение TRUE предикат: add23 (Дерево , Х, п2 (Т1, М2, Т2))
Это тот случай, в которым я разделить исходное дерево дерево, которые имеют 3 поддеревьев, в двух различных деревьев: T1 и T2, которые как корень есть узел с единственной минимальной меткой берет из старого корня исходного дерева Tree.
Так получилось, что у меня наверняка будет одно из этих деревьев, которое будет иметь два поддеревья, а другое - одно поддерево, поэтому я могу добавить новый вставленный элемент в это поддерево, а также использовать его как новый корень из newtree, который увеличивается в высоту на один уровень.
Правильно ли это? Я не уверен в этом ...
В книге я нашел объяснения от трех конкретных случая ин предикатных и у меня возникли большие сомнения относительно того, как это работает:
Случай 1:
ins(n2(T1, M , T2), X, n2(NT1, M, T2)) :- gt(M, X),
ins(T1, X, NT1).
в этом случае говорят мне, что оригинальное дерево дерево является: n2 (T1, M, T2) и вставить X в дерево, дерево, имеющее только 2 поддеревья: T1 и T2.
М является МИНИМАЛЬНОГО ЭЛЕМЕНТОМ правого поддерева
Таким образом, если GT (М, X) ИСТИНЫ это означает, что М> Х так, то это означает, что Х может быть левым поддеревом, который стал NT1 (почему? Возможно, это зависит от того, что старый T1 имеет только один лист в одном из своих поддеревьев?) И так, в конце концов, исходное дерево стало n2 (NT1, M, T2)
Я думаю, что этот случай просто
СЛУЧАЙ 2:
ins(n2(T1, M, T2), X, n3(NT1a, Mb, NT1b, M, T2)) :- gt(M, X),
ins(T1, X, NT1a, Mb, NT1b).
Также в этом случае скажите мне, что исходное дерево дерева : n2 (T1, M, T2) и я вставляю X в Дерево, являющееся деревом, имеющим только 2 поддеревья: T1 an d T2.
М является МИНИМАЛЬНОГО ЭЛЕМЕНТОМ правого поддерева
если оно истинно, что М> Х и это верно предикат: модулей (T1, X, NT1a, Mb, NT1b)
это означает, что я разделить T1 в 2 поддерева NT1a и NT1b добавление третьего ребенка к origincal дерева, которое стало n3 (NT1a, Мб, NT1b, М, Т2)
Хорошо это довольно ясно, но моя проблема заключается в следующем: в полном коде, что такое предикат, который должен удовлетворять? Я делаю путаницы ...
СЛУЧАЙ 3:
ins(n3(T1, M2, T2, M3, T3), X, n2(NT1a, Mb, NT1b), M2, n2(T2, M3, T3)) :-
gt(M2, X),
ins(T1, X, NT1a, Mb, NT1b).
Этот случай является случай, в котором оригинальное дерево Дерево имеет 3 поддеревьев, и когда я должен вставить его, я должен разделить оригинал дерево в два дерева (n3 (T1, M2, T2, M3, T3) и n2 (NT1a, Mb, NT1b)), вставьте новый элемент X в одно из этих поддеревьев и используйте минимальные элементы второго поддерева с правами root левое поддерево, как корень нового дерева (теперь выше уровня)
Мое сомнение: в предыдущем случае NewTree является п2 (NT1a, Mb, NT1b), М2, П2 (Т2, М3, Т3)
так М2 (минимальный элемент правого поддерева) является новым корнем, потому что это значение TRUE, что М2 > X?
Можете ли вы дать мне несколько советов, чтобы лучше понять эту вещь?