使用CLP(FD)对任意长度子列表的约束

Question

我正试着把头包裹在CLP(FD)周围.这是一个简单的例子,我不确定最常用的方法.假设我们有一个数字列表(L),其中一些数字已经填充,就像这样.

L = [_, _, _, 3, _, _, _, 4, _, _, 2, _]

我想说的是,固定的数字左右两边的数字必须总结这个数字.上述可能的解决方案是:

L = [0, 0, 1, 3, 0, 1, 1, 4, 2, 0, 2, 0]

当然,还有其他解决方案.我的第一种方法是:

1. 搜索第一个数据透视号码;
2. 获取枢轴的左右子列表;
3. Append 两个名单;
4. 使用谓词sum/3,将结果列表约束#=为数据透视表.

这会是意识形态的吗？我错过了一些更明显的东西吗？

---

2级.我认为谓词sum/3完成了大部分工作.让我们稍微改变一下这个问题:

枢轴左侧和右侧的连续弦1必须与枢轴相加.

所以这个:

L = [_, _, _, 3, _, _, _, 5, _, _, 2, _]

一个可能的解决方案是:

L = [0, 0, 0, 3, 1, 1, 1, 5, 1, 1, 2, 0]

而现在它更棘手......我想说的是,沿着N轴的附加左右子列表必须包含1的长度为N的子列表.这有意义吗？我怎么用CLP(FD)说这些话？

Answer 1

"本来可以解决的问题"

你的推理是完全正确的,并且会起作用.

然而,它在一个关键方面不足:您的描述目前非常必要,如果您按照您描述的方式实现,那么您将能够解决给定的实例,但您将无法使用相同的程序生成这样的拼图实例.

让我更详细地解释一下我的意思.

干净的代表

我们从这些谜题的表现开始.您目前正在使用:

L = [_, _, _, 3, _, _, _, 4, _, _, 2, _]

这称为默认表示,因为您无法清楚地区分不同的情况.如果你从逻辑上思考,并认为这是这个难题的"实例",那么这个术语的任何更特殊的情况都必须被视为实例的更具体的情况,例如部分或完整的解决方案.但在这种表示,这并非如此,因为实例化的参数之一还突然把它变成一个完全不同的实例,而不是唯一的一个更具体的体现.

所以,这里是这种谜题的清晰表示:

example([?,?,?,p(3),?,?,?,p(4),?,?,p(2),?]).

在这里,我用不同的术语来区分这两种可能的情况.我在用:

• 未知整数的原子 ?
• p(P)用于表示枢轴元素  的形式的术语P.

许多其他表示是可能的,如果您需要表达变量共享,您可以使用例如i(I)表示未知整数  I.关键是你可以通过模式匹配来区分案例,而不是测试实例化的非单调构造.这是可以在所有方向上使用的一般解决方案的关键.

声明性任务描述

让我们重新考虑你给出的命令性描述:

• " 搜索第一个数据透视号码"
• " 获取枢轴的左右子列表"
• " 附加两个列表"

现在让我们以声明的方式表达.我们必须避免迫切需要像"搜索","get"和"追加",因为这些都意味着一个特定的方向使用.

声明性描述可能如下所示:我们正在描述形式的三元组Lefts - Pivot- Rights,其中包含以下内容:

整数之Lefts和Rights是等于 Pivot.

如果我们设法编写一个Prolog程序来描述这样的三元组并从任务实例到这样的三元组绘制一个合适的连接,那么我们已经完成并且可以在所有方向上使用它.

转换为三元组

处理干净的表示很有趣,我们可以轻松地将它们转换为其他形式,因为我们可以很容易地区分这些情况.因此,让我们现在将实例转换为三元组,我们可以更容易地对其进行推理.

让我们反映任务表示:它是一个元素列表.经常在Prolog中描述列表时,DCG表示法(dcg)会派上用场.所以,让我们描述任务,同时描述任务描述和三元组之间的关系:

is_p_is([Ls|Rest]) -->
        is(Ls),
        is_p_is_(Rest).

is_p_is_([Pivot,Rs]) --> [p(Pivot)], is(Rs).
is_p_is_([Pivot,Rs,Rs|IPIs]) -->
        [p(Pivot)],
        is(Rs),
        is_p_is_(IPIs).

is([])     --> [].
is([_|Is]) --> [?], is(Is).

这个DCG是整个答案的关键点.

以下是如何使用它,看看它描述的内容:

?- example(Es),
   phrase(is_p_is(Ls), Es).
Es = [?, ?, ?, p(3), ?, ?, ?, p(4), ?, ?, p(2), ?],
Ls = [[_G902, _G905, _G908], 3, [_G920, _G923, _G926], [_G920, _G923, _G926], 4, [_G938, _G941], [_G938, _G941], 2, [_G950]] ;
false.

从这一点来看,你看到我已经消除了"搜索什么是在哪里以及在多远"的复杂推理.相反,它是实例和表单列表之间的简单而一般的关系:

[Left0,Pivot0,Right0,Left1,Pivot1,Right1,Left2,...]

"三元组"是隐含的,可以按如下方式分组:

[(Left0,Pivot0,Right0),(Left1,Pivot1,Right1),...]

并且进一步地,Right_Ñ是相同的作为Left_{n + 1个}.

发布约束

鉴于此类列表,发布CLP(FD)约束是直截了当的:

constraints([]).
constraints([Left,Pivot,Right|Rest]) :-
        Left ins 0..sup,
        Right ins 0..sup,
        sum(Left, #=, SL),
        sum(Right, #=, SR),
        Pivot #= SL + SR,
        constraints(Rest).

如果你愿意,你可以append/3在这里使用,但为什么甚至打扰？使用append/3会带来一些引入非终止的风险,而CLP(FD)约束(理想情况下)总是会终止,所以我使用了两个sum/3 约束.

提取变量

提取变量也很简单:

variables([]) --> [].
variables([Left,_,Right|Rest]) -->
        seq(Left),
        seq(Right),
        variables(Rest).

seq([]) --> [].
seq([L|Ls]) --> [L], seq(Ls).

示例查询和答案

这是一个示例查询和一些答案:

?- example(Es),
   phrase(is_p_is(Ls), Es),
   constraints(Ls),
   phrase(variables(Ls), Vs),
   label(Vs).
Es = [?, ?, ?, p(3), ?, ?, ?, p(4), ?, ?, p(2), ?],
Ls = [[0, 0, 0], 3, [0, 0, 3], [0, 0, 3], 4, [0, 1], [0, 1], 2, [1]],
Vs = [0, 0, 0, 0, 0, 3, 0, 0, 3, 0, 1, 0, 1, 1] ;
Es = [?, ?, ?, p(3), ?, ?, ?, p(4), ?, ?, p(2), ?],
Ls = [[0, 0, 0], 3, [0, 0, 3], [0, 0, 3], 4, [1, 0], [1, 0], 2, [1]],
Vs = [0, 0, 0, 0, 0, 3, 0, 0, 3, 1, 0, 1, 0, 1] ;
Es = [?, ?, ?, p(3), ?, ?, ?, p(4), ?, ?, p(2), ?],
Ls = [[0, 0, 0], 3, [0, 1, 2], [0, 1, 2], 4, [0, 1], [0, 1], 2, [1]],
Vs = [0, 0, 0, 0, 1, 2, 0, 1, 2, 0, 1, 0, 1, 1] ;
etc.

我强调了"三重"表示.

胜利的一般性

现在关键点:所有这些都是完全一般的,我们可以用它来自己生成实例!

例:

?- length(Es, _), phrase(is_p_is(Ls), Es).
Es = [p(_G874)],
Ls = [[], _G874, []] ;
Es = [p(_G877), ?],
Ls = [[], _G877, [_G885]] ;
Es = [p(_G877), p(_G888)],
Ls = [[], _G877, [], [], _G888, []] ;
Es = [?, p(_G880)],
Ls = [[_G877], _G880, []] ;
Es = [p(_G880), ?, ?],
Ls = [[], _G880, [_G888, _G891]] .

这是关系思维和使用简洁表示的自然副产品.

我将更具体的第二个问题作为第一个练习留给你.我希望上面提到的原理可以帮助您找到一个干净而通用的解决方案,让您从逻辑编程中获取最大的优势.

作为第二个练习,我将重写以上内容以使用i(_) 未知整数的表示.通过这样的表示,我们可以摆脱上面的几个缺点.例如,提取变量会变得更方便:

variables([]) --> [].
variables([L|Ls]) -->
        variable_(L),
        variables(Ls).

variable_(i(I)) --> [I].
variable_(p(_)) --> [].

例:

?- phrase(variables([i(X),p(3),i(Y)]), Vs).
Vs = [X, Y].

此外,我们不会不必要地复制此类列表中的其余变量.

进一步,检查出来:

?- length(Ls, _), phrase(variables(Ls), Vs).
Ls = Vs, Vs = [] ;
Ls = [i(_2066)],
Vs = [_2066] ;
Ls = [p(_2066)],
Vs = [] ;
Ls = [i(_2072), i(_2082)],
Vs = [_2072, _2082] ;
Ls = [i(_2072), p(_2082)],
Vs = [_2072] ;
Ls = [p(_2072), i(_2076)],
Vs = [_2076] .

这种纯粹的关系如何与使用不纯的谓词相比exclude/3？你能用它生成所有可能的案例吗？有关更多信息,请参阅logical-purity.

艰难的部分

作为第三个也是最后一个练习,我离开了最艰难的一个:重读我写的内容并通过使用命令式措辞找到我所处的所有实例,而不是对实际实现的内容进行公正处理,并重新编写它以反映实际情况.

我举一个例子:我说"提取变量",什么可能更自然,对吧？但我实际上已经实现了变量和三元组之间的完整关系,您可以使用它来:

• 从三元组中提取变量
• 测试这些变量是否对应于给定的三元组
• 生成变量和三元组
• 等等

例如,我们可以使用最通用的查询:

?- phrase(variables(Ts), Vs).
Ts = Vs, Vs = [] ;
Ts = [[], _1960, []],
Vs = [] ;
Ts = [[], _1960, [], [], _1978, []],
Vs = [] ;
Ts = [[], _1960, [], [], _1978, [], [], _1996, []],
Vs = [] .

这当然不是一个非常公平的枚举,但它远远超出了提取的东西,因为在查询中甚至没有给出任何东西.

你是如何惯用的!

所以,回答你的问题:在我看来,我们认为最具惯用性的 Prolog那些解决方案最令人印象深刻地展示了我们期望从逻辑程序的关系和独特优势中获得的声明性属性,例如:

• 可以在各个方向使用
• 承认阅读更具体或更一般
• 使用反映关系普遍性的名称.

优雅,惯用的Prolog解决方案通常以实例的清晰表示和描述性谓词名称开头.