时间戳

首页 > 解决方案 > 谓词有效但不能自动填空

prolog - 谓词有效但不能自动填空

问题描述

我写了一个谓词，它接受两个列表，一个带有links，一个使用link有效顺序的 s。链接被写成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，以防万一）并且永远不会吐出任何东西。这是一些无限循环还是只是错误的逻辑？（或者是其他东西？）

标签： prolog

解决方案

让我们检查一下跟踪：

?- 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谓词，或者你对它的使用；对于长度为 3 的列表，我得到了 192 个解决方案，但只有 120 个独特的解决方案，这看起来更像是我希望看到的阶乘/组合数字之一，而不是 192。

推荐阅读