транзитивное замыкание над симметричным отношением в прологе

Я новичок в прологе и хочу создать "братские" отношения.

Отношения должны быть симметричными, как если бы брат (alin, alex) истинно, брат (alex, alin) тоже должно быть.

Оно также должно быть транзитивным, как если бы брат (алин, алекс) и брат (алекс, клаудиу) истинны, брат (алин, клаудиу) Так и должно быть.

Комбинируя свойства to, если brother (alex, alin) и brother (alex, claudiu) истинны, brother (alin, claudiu) следует тоже быть правдой.

Вот мой код:

r_brother(alin, alex).
r_brother(alin, ciprian).
r_brother(alex, claudiu).

s_brother(X, Y) :- r_brother(X, Y).
s_brother(X, Y) :- r_brother(Y, X).

brother(L1, L2) :-
    t_brother(L1, L2, []).

t_brother(L1, L2, _) :-
    s_brother(L1, L2).

t_brother(L1, L2, IntermediateNodes) :-
    s_brother(L1, L3),
    \+ member(L3, IntermediateNodes),
    t_brother(L3, L2, [L3 | IntermediateNodes]).

r_brother - основное отношение

s_brother - симметричное братское отношение (это хорошо работает)

t_brother - это должно быть транзитивное и симметричное отношение, я сохраняю промежуточные узлы, поэтому у меня не будет цикла

Проблема в том, что ответ на:

?- brother(X, alin).

is:

X = alex ;
X = ciprian ;
X = alin ;
X = alin ;
X = alin ;
X = alin ;
X = alex ;
X = alex ;
X = alex ;
X = alex ;
X = ciprian ;
X = ciprian ;
X = claudiu ;
X = claudiu ;
false.

Я просмотрел след и понимаю, в чем проблема, но не знаю, как ее решить.

alin не может быть возможным ответом, а остальные должны появиться один раз.


prolog transitive-closure
person colegu    schedule 08.05.2014    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Я думаю, что основная проблема заключается в том, что вы не проверяете, найден ли уже L2 в первом предложении t_brother / 3. И начальный L1 нужно добавить в список в brother / 2:

brother(L1, L2) :-
  t_brother(L1, L2, [L1]).                   % <-- [L1] instead of []

t_brother(L1, L2, IntermediateNodes) :-
  s_brother(L1, L2),
  \+ member(L2, IntermediateNodes).          % <-- added this check

t_brother(L1, L2, IntermediateNodes) :-      % <-- this clause is unchanged
  s_brother(L1, L3),
  \+ member(L3, IntermediateNodes),
  t_brother(L3, L2, [L3 | IntermediateNodes]).

Вы все еще можете сократить решение, используя дизъюнкцию:

t_brother(L1, L2, IntermediateNodes) :-
  s_brother(L1, L3),
  \+ member(L3, IntermediateNodes),
  ( L2=L3
  ; t_brother(L3, L2, [L3 | IntermediateNodes])).
person danielp    schedule 08.05.2014
comment
Насколько я понимаю, в (L2 = L3; t_brother (L3, L2, [L3 | IntermediateNodes])) - означает ли это, что если первое условие (L2 = L3) верно, то не нужно проверять второе состояние? - person colegu; 08.05.2014
comment
Нет, это простая дизъюнкция (AlternativeA;AlternativeB). Либо L2 является следующим братом L3, либо мы находим L2, рекурсивно вызывая t_brother. Может быть, вы перепутали его с заявлением (Condition -> Then ; Else), которое подразумевает локальное сокращение? - person danielp; 08.05.2014

arrow_upward
1
arrow_downward

Вы можете записать отношение брата таким образом (точно так же, как транзитивное определение)

s_brother(X, Y) :- r_brother(X, Y);r_brother(Y, X).

brother(X,Y) :- s_brother(X, Y).
brother(X,Y) :- s_brother(X, Z),s_brother(Z, Y),X\=Y.

что означает, что X является братом Y, если он симметричный брат, или у них есть общий брат, и добавляет условие, что они разные.

попробуйте добавить X \ = Y в свой код, чтобы избавиться от «alin» как от решения.

person Siham    schedule 08.05.2014
comment
спасибо, это намного короче :), но проблема в том, что если вы добавите еще один факт, например r_brother (claudiu, jack). вы не получите в ответ валет. Для работы это должно быть рекурсивным. - person colegu; 08.05.2014