5

我正在尝试在“纯” Prolog 中编写可逆关系（不is，剪切或类似的东西。是的，这是家庭作业），我必须承认我不知道如何。我没有看到任何创建这样的东西的过程。

我们得到了“不纯”但可逆的算术关系（add、mult、equal、less...），我们必须使用它来创建这些关系。

现在，我正在尝试通过创建关系来了解如何创建可逆函数，tree(List,Tree)如果List是二叉树的叶子列表，则该关系为真Tree。

为了实现这样的事情，我试图创建当有叶子tree_size(Tree,N)时为真的关系。这是我天真的、不可逆的关系：TreeN

tree_len(n(_,leaf,leaf),1).
tree_len(n(op,G,D),N) :-
    tree_len(G,TG),
    tree_len(D,TD),
    add(TG,TD,N).

我可以做查询tree_len(some tree, N)，但不能，说，tree_len(X,3)所以它是不可逆的。到目前为止，我已经尝试了一些事情，但我必须承认我感到沮丧，因为我不知道在哪里寻找什么。实际上有办法做到这一点吗？

4

2 回答 2

9

不终止的原因

首先，让我们试着理解为什么你的定义是不可逆的。我将使用故障切片来更好地解释它。所以考虑查询tree_len(X,1).乍一看，一切都很完美，你甚至会得到一个很好的答案！

?- tree_len(T,1).
T = n(_G267, leaf, leaf)

但永远不要要求另一个答案，因为它会循环：

?- tree_len(T,1).
T = n(_G267, leaf, leaf) ;
** LOOPS **

所以我们得到的答案有点让人分心。乍一看似乎一切正常，但只有在回溯时才遇到真正的问题。这是在 Prolog 中习惯的东西。显然，您使用 3 的查询得到了更好的选择。但那是运气。

一般来说，有一种简单的方法可以确保这一点。只需将额外的目标添加false到查询中。添加false意味着我们不再对任何答案感兴趣，因为它不再成功。这样一来，所有的干扰都被消除了，我们直接面对问题：

?- tree_len(T,1), false.
** LOOPS **

那么，这个循环是从哪里来的呢？

在纯粹的、单调的 Prolog 程序（例如这个）中，我们可以通过false在我们的程序中添加一些目标来定位不终止的原因。如果生成的程序（称为failure-slice）没有终止，那么原始程序也不会终止。这是我们查询的最小故障片：

?- tree_len(T,1), false。

tree_len(n(_,leaf,leaf),1) :-假。
tree_len(n(op,G,D),N) :-
    tree_len(G,TG), false ,
     tree_len(D,TD) ,
     N 是 TG+TD。

我们的程序所剩无几！正是这个微小的片段负责不终止。如果我们想解决这个问题，我们必须在那个微小的部分做点什么。其他一切都是徒劳的。

所以我们需要做的是以某种方式改变程序，使这个片段不再循环。

实际上，我们有两个选择，我们可以使用后继算法或约束，如 clpfd。前者在任何 Prolog 系统中都可用，后者仅在 SWI、YAP、SICStus、GNU、B 等某些系统中提供。

使用后继算法

现在，3 由 表示s(s(s(0)))。

tree_lensx(T, s(N)) :-
   树_lendiff（T，N，0）。

tree_lendiff(n(_,leaf,leaf), N,N)。
tree_lendiff(n(op,G,D), s(N0),N) :-
   tree_lendiff(G, N0,N1),
   tree_lendiff(D, N1,N)。

我在这里使用了几种常见的编码技术。

差异

实际的关系tree_lendiff/3不是用一个参数而是用两个来表示一个自然数。实际数字是两者之间的差异。以这种方式，可以保持定义可逆。

避免左递归

另一种技术是避免左递归。实际描述的tree_lendiff/3长度是长度减一。还记得我们首先得到的故障片吗？同样的故障片也会出现在这里！然而，通过将长度“移动”一，递归规则的头部现在确保终止。

使用library(clpfd)

最初，有限域上的约束是为了解决组合问题而开发的。但是您也可以使用它们来获得可逆算术。SWI 和 YAP 中的实现甚至可以编译成代码，其效率通常与传统的不可逆代码相当，(is)/2但仍然是可逆的。

:- use_module(library(clpfd)).

tree_fdlen(n(_,leaf,leaf),1).
tree_fdlen(n(op,G,D),N) :-
   N #= TG+TD,
   TG #>= 1,
   TD #>= 1,
   tree_fdlen(G,TG),
   tree_fdlen(D,TD).

该程序更接近于您的原始定义。尽管如此，请注意这两个目标TG #>= 1并TD #>= 1添加了冗余信息以确保该程序的终止。

我们现在可以像这样枚举一定范围内的所有树：

?- Size in 0..4, tree_fdlen(T, Size).
Size = 1, T = n(_A,leaf,leaf) ;
Size = 2, T = n(op,n(_A,leaf,leaf),n(_B,leaf,leaf)) ;
Size = 3, T = n(op,n(_A,leaf,leaf),n(op,n(_B,leaf,leaf),n(_C,leaf,leaf))) ;
Size = 4, ... ;
Size = 4, ... ;
Size = 3, ... ;
Size = 4, ... ;
Size = 4, ... ;
Size = 4, ... ;
false.

注意答案替换的确切顺序！它不仅仅是 1,2,3,4！相反，答案是按某种顺序找到的。哪一种都无所谓，只要我们只对寻找所有解决方案感兴趣！

于 2012-12-31T02:18:43.723 回答
1

有趣的问题。

这就是我要做的。基本上，您的关系是不可逆的，因为 add/3 不是。我本质上所做的是，用与叶子数量相对应的大小列表来代替数字计数 - 这是可逆的（好吧，追加/ 3和长度/ 2是可逆的）。

这是你需要的吗？发布的代码可在 YAP 下运行。

PS：这可能不是最简洁的解决方案，但它来自我的脑海。如果您还有其他问题，我会尽力提供帮助。

:-  use_module(library(lists)).

do_tree_len(n(_,leaf,leaf), [X]).
do_tree_len(n(op,G,D), [X1,X2|T]) :-
    append(TG, TD, [X1,X2|T]),
    TG \= [X1,X2|T], % To prevent infinite loops, when TG or TD is []
    TD \= [X1,X2|T],
    do_tree_len(G, TG),
    do_tree_len(D, TD).

tree_len(Tree, N):-
    length(L, N),
    do_tree_len(Tree, L).
于 2012-12-31T00:44:46.003 回答