Пролог Рекурсия - удовлетворение обоих направлений (простой) - PullRequest
Новая
       31

Пролог Рекурсия - удовлетворение обоих направлений (простой)

3 голосов
/ 23 февраля 2012

Я очень новичок в Прологе, и мне дали это задание.

Мой код выглядит следующим образом: 

relatives(cindy,tanya).
relatives(tanya,alan).
relatives(alan,mike).
relatives(kerry,jay).
relatives(jay,alan).

isRelated(X,Y):-
    relatives(X,Y).
isRelated(X,Y):-
    relatives(X,Z),
    isRelated(Z,Y).

Достаточно просто.Это показывает, что если: 

?- isRelated(cindy,mike).

Пролог вернет true.Теперь я застрял на том, как заставить его возвращать значение true, если: 

?- isRelated(mike,cindy).

Я пытался придумать идеи, например, если isRelated (Z, Y) возвращает false, затем переключить X и Yи снова запустите isRelated.Но я не уверен, что Пролог допускает такую ​​идею.Любые советы или рекомендации будут с благодарностью.Спасибо!

ОБНОВЛЕНИЕ: ************************************

Итак, я добавил: 

isRelated(X,Y):-
    relatives(X,Y);
    relatives(Y,X).

Это удовлетворит "прямые" отношения, но достаточно просто, я обнаружил, что это не удовлетворяет косвенным отношениям.

Я действительно хочу сделать что-то вроде, если первоначальный запрос: 

isRelated(mike,cindy)

не пройден, попробуйте и посмотритеесли обратное верно при переключении X и Y: 

isRelated(cindy,mike)

Это определенно вернет true.Я просто не знаю, как сделать это синтаксически в Прологе.

Ответы [ 3 ]

1 голос
/ 23 февраля 2012

Таким образом, чтобы ответить на ваш последний вопрос, вы не переключаете значения из X и Y в Прологе, как если бы вы называли swap(x,y) в C, скажем.Значение, содержащееся в логической переменной, не может быть изменено явно, только отслеживается в обратном направлении.Но вы можете легко использовать Y там, где вы будете использовать X, и наоборот: 

somePred(X,Y):- is_it(X,Y).
somePred(X,Y):- is_it(Y,X).

Это определяет предикат somePred как логическую дизъюнкцию, "ИЛИ" ,Это также может быть написано явно, как 

somePred(X,Y):- is_it(X,Y) ; is_it(Y,X).

Обратите внимание на точку с запятой там.Запятая , между предикатами OTOH определяет конъюнкцию, «И» (запятая внутри составного термина просто служит для разграничения «аргументов» термина).

1 голос
/ 23 февраля 2012

Вы почти там, вы просто пытаетесь, я думаю, втиснуть слишком много материала в один предикат.

Напишите формулировку проблемы на английском языке и поработайте над этим:

Существует связь между двумя людьми, X и Y

  • , если X и Y напрямую связаны, или
  • если любой прямой родственник X, P связан с Y.

Тогда это становится легко.Я подхожу к этому так:

Во-первых, у вас есть набор фактов о родственниках. 

related( cindy, tanya ).
...
related( james, alan ).

Затем предикат, описывающий прямые отношения, - это термины этих фактов: 

directly_related( X , Y ) :- % a direct relationship exists 
  related(X,Y)               %   if X is related to Y
  .                          % ... OR ...
directly_related( X , Y ) :- % a direct relationship exists
  related(Y,X)               %   if Y is related to X
  .                          %

Наконец, предикат, описывающий любые отношения: 

is_related(X,Y) :-        % a relationship exists between X and Y
  directly_related(X,Y)   %   if a direct relationship exists between them
  .                       % ... OR ...
is_related(X,Y) :-        % a relationship exists between X and Y
  directly_related(X,P) , %   if a direct relationship exists between X and some other person P
  is_related(P,Y)         %   and [recursively] a relationship exists between P and Y.
  .                       %

Решение на самом деле более сложное, чем это:

  1. Факты об отношениях описываютодин или несколько графиков .Больше на графиках в http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/Graphs.html. Что вы делаете, это нахождение пути от узла X к узлу Y на графике.

  2. Если графики описаны фактами об отношенияхЕсли между X и Y имеется один или несколько путей, приведенное выше решение может (и будет) выполнено несколько раз (при возврате), один раз для каждого такого пути.Решение должно быть детерминированным .Нормально, установив, что два человека связаны, мы закончили: только то, что у меня есть два двоюродных брата, не означает, что я связан с моей тетей дважды.

  3. Если графикотношения содержат циклов (почти наверняка верно), так что существует "круговой" путь: A → B → C → A …, решение подвержено неограниченной рекурсии.Это означает, что решение должно обнаруживать циклы и иметь дело с ними.Как это может быть достигнуто?

1 голос
/ 23 февраля 2012

Дополнительный намек на комментарии в комментариях, поскольку я пока не могу оставлять комментарии: с вашим оригинальным набором правил и фактов isRelated(cindy,tanya) - это правда, а isRelated(tanya,cindy) - нет, поэтому вам нужно сделать isRelated(X,Y)симметричны;Какое простое дополнение к isRelated позволит этого достичь?

Кроме того, вы можете попробовать нарисовать график отношения relatives(X,Y) со стрелкой от X до Y для всех ваших базовых фактов и посмотреть, поможет ли этовы думаете о том, как интерпретатор Prolog попытается удовлетворить запрос.

...