Некоторые сомнения по поводу реализации Пролога 2-3 словаря
Я изучаю Пролог с использованием SWI Prolog, и у меня есть некоторые сомнения относительно того, как работает эта реализация словаря 2-3 в Прологе.
Я знаю теорию 2-3 словарей, которые являются деревьями, чьи внутренние узлы могут генерировать 2 или 3 поддерева, имеющие следующие свойства:
1) Все предметы хранятся в листьях и упорядочены от меньшего к большему
2) Все листья находятся на одном уровне
3) Внутренние узлы не содержат вставленный элемент, но содержат метку, которая задает минимальные элементы поддеревьев следующим образом:
- Если у внутреннего узла есть 2 поддерева, метка в этом внутреннем узле содержит МИНИМАЛЬНЫЙ ЭЛЕМЕНТ его ПРАВОГО поддерева (поэтому, если я ищу элемент X, который меньше, чем метка, я уверен, что он находится в левом поддереве)
- Если внутренний узел имеет 3 поддерева, метка в этом внутреннем узле содержит 2 значения: M2 и M3, где M1 - МИНИМАЛЬНОЕ ЗНАЧЕНИЕ, которое присутствует в СУБЪЕКТЕ ЦЕНТРА, а M3 - МИНИМАЛЬНОЕ ЗНАЧЕНИЕ, которое является правым поддеревом.
Поэтому поиск, существует ли какой-либо элемент в этом словаре, довольно прост.
Вставка более сложная, я понимаю ее теорию, но у меня есть только некоторые проблемы с интерпретацией Пролога.
Это моя программа (из книги Ивана Братко: Программирование для искусственного интеллекта):
/* 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).
В этой реализации у меня есть что:
- l (X) представляет элемент, присутствующий в моем дереве
- n2(T1,M,T2) представляет дерево с 2 подтрессами T1 и T2, где M - минимальный элемент в T2
- n3 (T1, M2, T2, M3, T3) ** представляет дерево с 3 поддеревьями: 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).
Как пишут в комментариях, я думаю, что первый связан со случаем, в котором новое дерево не растет вверх (поэтому, например, у меня было дерево, которое имеет 2 поддерева, и вставляя новый элемент, я создаю новое поддерево, которое имеют свои листья на том же уровне, что и все остальные листья (и поэтому внутренний узел теперь будет иметь 2 метки) Это правильно?
Таким образом, в логике я могу прочитать это следующим образом: если предикат ins(Tree, X, Tree1) равен TRUE, я должен добавить X в Tree, генерируя новое Tree1, имеющее ту же высоту старого дерева, но содержащее элемент X (поэтому оно должно есть внутренний узел, имеющий 3 дочерних)
Второй случай связан со случаем, в котором у меня есть дерево, и я должен вставить новый элемент в узел, который уже имеет 3 поддерева, поэтому я должен разделить старое дерево на 2 дерева, которые как корень имеют оба в качестве метки a одну метку берут из 2 меток старого оригинального узла. Таким образом, я могу вставить новый элемент как лист и как новый корень нового дерева.
Так что по логике я могу прочитать это как:
Если предикат ins(Tree, X, T1, M2, T2) равен TRUE, то это означает, что он TRUE предикат: add23 (Tree, X, n2 (T1, M2, T2))
Это тот случай, когда я разделил исходное дерево Tree, которое имеет 3 поддерева, на два разных дерева: T1 и T2, которые в качестве корня имеют узел с единственной минимальной меткой, взятой из старого корня исходного дерева Tree.
Так что случается так, что у меня наверняка будет одно из этих деревьев будет иметь два поддерева, а другое - одно поддерево, так что я могу добавить новый вставленный элемент в это поддерево, а также использовать его в качестве нового корня нового увеличенного дерева. в высоту на один уровень.
Это правильно? Я не уверен в этом...
В книге я нашел объяснение трех конкретных случаев предиката ins, и у меня много сомнений в том, как это работает:
СЛУЧАЙ 1:
ins(n2(T1, M , T2), X, n2(NT1, M, T2)) :- gt(M, X),
ins(T1, X, NT1).
В этом случае скажите мне, что исходное дерево Tree: n2(T1,M,T2), и я вставляю X в Tree, то есть дерево, имеющее только 2 поддерева: T1 и T2.
М - МИНИМАЛЬНЫЙ ЭЛЕМЕНТ ПРАВОЙ СУЩЕСТВА
Таким образом, если gt(M, X) TRUE, это означает, что M>X, поэтому это означает, что X может быть ЛЕВОЙ СУДОШКОЙ, которая стала NT1 (почему? Это может зависеть от того факта, что старый T1 имеет только 1 лист в одном из своих поддерево?) и так, в конце концов, исходное дерево стало 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).
Также в этом случае скажите мне, что исходное дерево Tree: n2(T1,M,T2), и я вставляю X в Tree, то есть дерево, имеющее только 2 поддерева: T1 и T2.
М - МИНИМАЛЬНЫЙ ЭЛЕМЕНТ ПРАВОЙ СУЩЕСТВА
ЕСЛИ это ИСТИНА, что М> Х, и это ИСТИНА, предикат: ins (T1, X, NT1a, Mb, NT1b)
это означает, что я разделил T1 на 2 поддерева NT1a и NT1b, добавив третьего потомка к исходному дереву, которое стало n3(NT1a, Mb, NT1b, M, T2)
Хорошо, это довольно ясно, но моя проблема: в полном коде, что должен удовлетворять этот предикат? Я делаю путаницу...
ДЕЛО 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 в одно из этих поддеревьев и используйте минимальные элементы второго поддерева в качестве корня левого поддерева в качестве корня нового дерева (которое теперь выше уровня)
Я сомневаюсь: в предыдущем случае NewTree - это n2(NT1a, Mb, NT1b), M2, n2(T2, M3, T3)
поэтому M2 (минимальный элемент правого поддерева) является новым корнем, потому что это ИСТИНА, что M2>X?
Можете ли вы дать мне несколько советов, чтобы лучше понять эти вещи?
1 ответ
Сначала пара стилевых очков. Вам не нужно иметь отдельные конструкторы для n2 а также n3, так как арты с этим справятся за вас. Во-вторых, вы должны с подозрением относиться к любому предикату, в котором есть сокращения, особенно к красным, которые вы используете в /2. Как правило, лучше (и быстрее) проводить явный анализ случаев. Также, если можете, укажите в первом аргументе то, что вы сравниваете, так как он индексируется по умолчанию.
Я бы переписал в / 2 как
in(leaf(Item), Item).
in(node(Left, M, Right), Item):-
compare(Order, Item, M),
in_2(Order, Item, node(Left, M, Right).
in(node(Left, M1, Mid, M2, Right), Item):-
compare(Order, Item, M1),
in_3(Order, Item, node(Left, M1, Mid, M2, Right)).
in_2(<, Item, node(Left, _, _)):-
in(Left, Item).
in_2(=, Item, node(_, _, Right)):-
in(Right, Item).
in_2(>, Item, node(_, _, Right)):-
in(Right, Item).
in_3(<, Item, node(Left, _, _, _, _)):-
in(Left, Item).
in_3(=, Item, node(_, _, Mid, _, _)):-
in(Mid, Item).
in_3(>, Item, node(Left, M1, Mid, M2, Right)):-
compare(Order, Item, M2),
in_3a(Order, Item, node(Left, M1, Mid, M2, Right)).
in_3a(<, Item, node(_, _, Mid, _, _)):-
in(Mid, Item).
in_3a(=, Item, node(_, _, _, _, Right)):-
in(Right, Item).
in_3a(>, Item, node(_, _, _, _, Right)):-
in(Right, Item).
Что касается вставки дерева, это немного сложнее, чем я думаю, вы поняли.
Одной из ключевых особенностей 2-3 деревьев является то, что все листья находятся на одной глубине. Это означает, что когда вы вставляете элемент, вы должны пройти по дереву, чтобы найти место среди листьев, в которое нужно вставить его, а затем распространить изменения обратно вверх по дереву, чтобы убедиться, что он остается сбалансированным. Эти слайды из лекции по структурам данных описывают алгоритм. Попробуйте просто перевести их на пролог. На слайдах четко представлены различные случаи. Пример кода, который я привел выше, должен помочь вам на первом этапе алгоритма вставки (поиск правильного узла нижнего уровня для вставки нового листа). Используйте тот же подход, когда вы работаете с деревом.