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

Question

Я написал предикат, который принимает два списка, один с link с и один, использующий эти link с в правильном порядке.Ссылки пишутся как link(a, b), где их части могут быть в любом порядке, и результат должен быть одинаковым.Действительный заказ для ссылок будет [link(a, b), link(b, c), link(c, a)].Это формирует кольцо из link s, которое соединяется хотя бы с одним элементом.

% Can two links be adjacent?
adjacent(link(Elem, _), link(Elem, _)).
adjacent(link(_, Elem), link(Elem, _)).
adjacent(link(_, Elem), link(_, Elem)).
adjacent(link(Elem, _), link(_, Elem)).

% Swap the parts in a link.
swapped(link(A, B), link(B, A)).

% Is each item unique in the list?
unique(List) :- \+ (select(Elem, List, Res), memberchk(Elem, Res)).

% Can the list form a loop using only the provided links?
ring(List, Ring) :-
    length(Ring, Length),
    Length > 2, % List is at least of length 3.
    Ring = [First|_],
    last(Ring, Last),
    adjacent(First, Last), % First and last have to be able to be adjacent.
    unique(Ring), % No repeated items.
    linked(List, Ring). % Are the middle links adjacent?

% Are any of the two elements in a list?
member_or(Elem, _, List) :- member(Elem, List).
member_or(_, Elem, List) :- member(Elem, List).

% Is the list able to be linked using only the provided links?

linked(_, []).
linked(List, [Elem]) :-
    swapped(Elem, Alt),
    member_or(Elem, Alt, List). % Is the item valid?
linked(List, [First|Ring]) :-
    swapped(First, Alt),
    member_or(First, Alt, List), % Is the first item valid?
    Ring = [Second|_],
    adjacent(First, Second), % Can the next item be adjacent?
    linked(List, Ring). % Is the same operation true with one less item?

При использовании его как ring([link(a, b), link(b, c), link(a, c), link(f, r)], [link(a, b), link(b, c), link(c, a)]). (с указанием всех аргументов), он всегда возвращает правильный логический (в данном случае, правда).В идеале я хотел бы написать ring([link(a, b), link(b, c), link(c, a), link(f, r)], Ring)., и все возможные Ring s были бы даны, но это останавливает интерпретатор (я использую SWI-Prolog, на всякий случай) и никогда не выплевывает что-либо.Это какой-то бесконечный цикл или просто неисправная логика?(Или что-то еще?)

Answer 1

Давайте рассмотрим след:

?- trace, ring([link(a, b), link(b, c), link(c, a), link(f, r)], Ring).
   Call: (9) ring([link(a, b), link(b, c), link(c, a), link(f, r)], _452) ? creep
   Call: (10) length(_452, _828) ? creep
   Exit: (10) length([], 0) ? creep
   Call: (10) 0>2 ? creep
   Fail: (10) 0>2 ? creep
   Redo: (10) length(_452, _828) ? creep
   Exit: (10) length([_812], 1) ? creep
   Call: (10) 1>2 ? creep
   Fail: (10) 1>2 ? creep
   Redo: (10) length([_812|_814], _840) ? creep
   Exit: (10) length([_812, _824], 2) ? creep
   Call: (10) 2>2 ? creep
   Fail: (10) 2>2 ? creep

Не интересно, пока мы не дойдем до этого места:

   Redo: (10) length([_812, _824|_826], _852) ? creep
   Exit: (10) length([_812, _824, _836], 3) ? creep
   Call: (10) 3>2 ? creep
   Exit: (10) 3>2 ? creep
   Call: (10) [_812, _824, _836]=[_848|_850] ? creep
   Exit: (10) [_812, _824, _836]=[_812, _824, _836] ? creep
   Call: (10) lists:last([_812, _824, _836], _870) ? creep
   Exit: (10) lists:last([_812, _824, _836], _836) ? creep
   Call: (10) adjacent(_812, _836) ? creep
   Exit: (10) adjacent(link(_854, _856), link(_854, _862)) ? creep
   Call: (10) unique([link(_854, _856), _824, link(_854, _862)]) ? creep
   Call: (11) lists:select(_880, [link(_854, _856), _824, link(_854, _862)], _884) ? creep
   Exit: (11) lists:select(link(_854, _856), [link(_854, _856), _824, link(_854, _862)], [_824, link(_854, _862)]) ? creep
   Call: (11) memberchk(link(_854, _856), [_824, link(_854, _862)]) ? creep
   Exit: (11) memberchk(link(_854, _856), [link(_854, _856), link(_854, _862)]) ? creep
   Fail: (10) unique([link(_854, _856), _824, link(_854, _862)]) ? creep
   Redo: (10) adjacent(_812, _836) ? creep
   Exit: (10) adjacent(link(_854, _856), link(_856, _862)) ? creep
   Call: (10) unique([link(_854, _856), _824, link(_856, _862)]) ? creep
   Call: (11) lists:select(_880, [link(_854, _856), _824, link(_856, _862)], _884) ? creep
   Exit: (11) lists:select(link(_854, _856), [link(_854, _856), _824, link(_856, _862)], [_824, link(_856, _862)]) ? creep
   Call: (11) memberchk(link(_854, _856), [_824, link(_856, _862)]) ? creep
   Exit: (11) memberchk(link(_854, _856), [link(_854, _856), link(_856, _862)]) ? creep
   Fail: (10) unique([link(_854, _856), _824, link(_856, _862)]) ? creep
   Redo: (10) adjacent(_812, _836) ? creep
   Exit: (10) adjacent(link(_854, _856), link(_860, _856)) ? creep
   Call: (10) unique([link(_854, _856), _824, link(_860, _856)]) ? creep
   Call: (11) lists:select(_880, [link(_854, _856), _824, link(_860, _856)], _884) ? creep
   Exit: (11) lists:select(link(_854, _856), [link(_854, _856), _824, link(_860, _856)], [_824, link(_860, _856)]) ? creep
   Call: (11) memberchk(link(_854, _856), [_824, link(_860, _856)]) ? creep
   Exit: (11) memberchk(link(_854, _856), [link(_854, _856), link(_860, _856)]) ? creep
   Fail: (10) unique([link(_854, _856), _824, link(_860, _856)]) ? creep
   Redo: (10) adjacent(_812, _836) ? creep
   Exit: (10) adjacent(link(_854, _856), link(_860, _854)) ? creep
   Call: (10) unique([link(_854, _856), _824, link(_860, _854)]) ? creep
   Call: (11) lists:select(_880, [link(_854, _856), _824, link(_860, _854)], _884) ? creep
   Exit: (11) lists:select(link(_854, _856), [link(_854, _856), _824, link(_860, _854)], [_824, link(_860, _854)]) ? creep
   Call: (11) memberchk(link(_854, _856), [_824, link(_860, _854)]) ? creep
   Exit: (11) memberchk(link(_854, _856), [link(_854, _856), link(_860, _854)]) ? creep
   Fail: (10) unique([link(_854, _856), _824, link(_860, _854)]) ? creep
   Redo: (10) length([_812, _824, _836|_838], _864) ? creep
   Exit: (10) length([_812, _824, _836, _848], 4) ? creep
   Call: (10) 4>2 ? creep
   Exit: (10) 4>2 ? creep
   Call: (10) [_812, _824, _836, _848]=[_860|_862] ? creep
   Exit: (10) [_812, _824, _836, _848]=[_812, _824, _836, _848] ? 

Здесь есть два существенных факта, которые стоит заметить:

1. Вы действительно переходите к спискам длины 4, так что у вас здесь есть какая-то логическая ошибка.
2. Мне кажется, что вы генерируете одни и те же возможности несколько раз, так что вы работаете довольнотрудно не генерировать ответы.На первый взгляд, похоже, что adjacent/2 помогает вам создать четыре версии одного и того же расположения переменных для проверки.Это кажется неэффективным.

Чего не хватает в следе?linked/2.Зачем?Потому что мы никогда успешно не объединились unique/1!На самом деле, это почти всегда терпит неудачу:

?- unique([A,B]).
false.

?- unique([A,B,C]).
false.

?- unique([A]).
true.

Я бы поставил приличные шансы, что это ваша проблема прямо здесь.Есть лучшие, хотя и менее портативные, способы сделать это, используя dif/2.Интересно, что кто-то еще недавно спрашивал об этом, и @false связался с этим ответом , который показывает хорошую реализацию, которая действительно работает для случаев, подобных вашему.Давайте заменим это определение и посмотрим, что произойдет:

unique([]).
unique([E|Es]) :-
   maplist(dif(E), Es),
   unique(Es).

?- ring([link(a, b), link(b, c), link(c, a), link(f, r)], Ring).
Ring = [link(a, b), link(b, c), link(a, c)] ;
Ring = [link(a, b), link(b, a), link(a, c)] ;
Ring = [link(a, b), link(c, b), link(a, c)] ;
Ring = [link(a, b), link(c, a), link(a, c)] ;
Ring = [link(a, b), link(c, a), link(a, c)] ;
Ring = [link(a, b), link(b, a), link(a, c)] ;
Ring = [link(b, c), link(c, a), link(b, a)] ;

Кажется справедливым сказать, что это решило вашу первую проблему.Я вижу множество дублирующих решений, поэтому я не думаю, что вы еще совсем не в лесу, я думаю, вам все еще нужно пересмотреть свой предикат adjacent/2 или его использование;Я получил 192 решения для списка длины 3, но только 120 уникальных, что больше похоже на одно из тех чисел факториала / комбинаторики, которое я ожидаю увидеть, чем 192.