使用 CLP(FD) 约束任意长度的子列表
Constraints over arbitrary length sublists using CLP(FD)
我正在努力思考 CLP(FD)。这是一个我不确定最惯用方法的简单示例。假设我们有一个数字列表 (L)，其中已经填充了一些数字，如下所示。
L = [_, _, _, 3, _, _, _, 4, _, _, 2, _]
我想说的是，一个固定数的左右两边的数字必须相加。上述问题的可能解决方案是：
L = [0, 0, 1, 3, 0, 1, 1, 4, 2, 0, 2, 0]
当然还有其他解决方案。我的第一种方法是这样的：
- 搜索第一个 pivot 数字；
- 获取pivot的左右子列表；
Append 两个列表；- 使用谓词
sum/3，将结果列表约束为 #= 到主元。
这会是理想主义吗？我错过了更明显的东西吗？
级别 2. 我认为谓词 sum/3 完成了大部分工作。让我们稍微改变一下问题：
主元左边和右边的连续 1 串必须和主元相加。
鉴于此：
L = [_, _, _, 3, _, _, _, 5, _, _, 2, _]
可能的解决方案是：
L = [0, 0, 0, 3, 1, 1, 1, 5, 1, 1, 2, 0]
现在更棘手了...我想说的是，主元 N 的附加左右子列表必须包含长度为 N 的 1 子列表。这有意义吗？我如何使用 CLP(FD) 来表达这些内容？
"The solution that could have been"
您的推理是完全正确的，并且会奏效。
不过，它在一个关键方面有不足：您的描述目前非常强制性，如果按照您描述的方式实现，那么您将能够解决给定 个实例，但您不能 能够使用相同的 程序来生成 个这样的拼图实例。
让我更详细地解释一下我的意思。
干净的表示
我们从 表示 此类谜题开始。您目前正在使用：
L = [_, _, _, 3, _, _, _, 4, _, _, 2, _]
这称为 默认 表示，因为您无法清楚地区分不同的情况。如果你从逻辑上思考，并且认为这是一个 "instance" 的谜题，那么任何 更特殊的 这个术语 的情况必须 被视为实例的更具体案例，例如部分或完整的解决方案。但在这种表示中，不是这种情况，因为实例化其中一个参数 further 突然将它变成一个完全不同的实例，而不仅仅是一个更多的实例具体表现。
因此，这是此类谜题的干净表示：
example([?,?,?,p(3),?,?,?,p(4),?,?,p(2),?]).
在这里，我用不同的术语来区分这两种可能的情况。我正在使用：
- 未知的原子
?整数
- 形式为
p(P) 的术语表示 pivot 元素 P.
很多其他的表示都是可能的，如果你需要表达变量 sharing，你可以使用 i(I) 来表示一个未知的整数 I .关键是您可以通过 模式匹配 而不是测试 实例化 的非单调构造来区分案例。这是通用解决方案的关键，可用于所有方向。
声明式任务描述
让我们重新考虑一下您给出的命令式描述：
- "搜索 第一个主元数"
- "获取枢轴的左右子列表"
- "附加两个列表"
现在让我们声明性地表达这个。我们必须避免 命令式[=231=]，例如 "search"、"get" 和 "append"，因为这些都暗示着特定的 方向使用。
声明性描述可能如下所示：我们正在描述形式为 Lefts-Pivot-Rights 的 三元组 ，其中以下持有：
The sum of integers Lefts and Rights is equal to Pivot.
如果我们设法编写一个 Prolog 程序来描述 此类三元组并绘制从任务实例到此类三元组的合适连接，那么我们就完成了并且可以在所有方向。
转换为三元组
处理干净的表示很有趣，我们可以轻松地将它们转换为其他形式，因为我们可以很容易地区分大小写。因此，让我们现在将实例转换为三元组，我们可以更容易地推理。
让我们反映一下任务表示：它是一个 list 元素。在 Prolog 中 describing 列表时，DCG notation (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.
由此可见，我把"searching what is where and how far"的复杂推理去掉了。相反，它是实例和表单列表之间的简单通用 关系 ：
[Left0,Pivot0,Right0,Left1,Pivot1,Right1,Left2,...]
其中 "triples" 是隐式的，可以按如下方式分组：
[(Left0,Pivot0,Right0),(Left1,Pivot1,Right1),...]
此外，Rightn 与 Leftn+ 相同 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.
我已经突出显示了 "triple" 表示。
胜利的普遍性
现在关键点：所有这些都是完全通用，我们可以用它来生成实例本身！
示例：
?- 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]] .
这是自然思考关系并使用清晰表示[=]的副产品230=].
我将更具体的第二个问题作为第一个练习留给您。我希望上面显示的原则可以帮助您找到一个 clean 和 general 的解决方案，让您发挥逻辑编程的最大优势。
作为第二个练习，我将重写上面的代码以使用 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。
困难的部分
作为第三个也是最后一个练习，我留下了最难的一个：重读我写的东西并找到我所在的所有实例，使用命令式[=231=]措辞，没有公正地对待实际实施的内容的普遍性，改写它以反映实际情况。
我举个例子：我说"Extracting the variables"，还有什么更自然的，对吧？但我实际上已经实现了一个完整的变量和三元组之间的关系，你可以用它来：
- 从三元组中提取变量
- 测试这些变量是否对应给定的三元组
- 生成变量和三元组
- 等等
例如，我们可以使用最一般的查询:
?- phrase(variables(Ts), Vs).
Ts = Vs, Vs = [] ;
Ts = [[], _1960, []],
Vs = [] ;
Ts = [[], _1960, [], [], _1978, []],
Vs = [] ;
Ts = [[], _1960, [], [], _1978, [], [], _1996, []],
Vs = [] .
这当然不是一个非常公平的枚举，但它远远超出了提取的范围，因为nothing at all 甚至在查询中给出。
你怎么地道！
所以，回答你的问题：在我看来，我们认为 最惯用的 Prolog 那些最令人印象深刻地展示了声明性属性的解决方案 我们期望从 关系 和逻辑程序的独特优势，例如：
- 可在所有方向使用
- 承认阅读更具体或更一般
- 使用反映关系普遍性的名称。
一个优雅、惯用的 Prolog 解决方案通常从实例的清晰表示和描述性谓词名称开始。
我正在努力思考 CLP(FD)。这是一个我不确定最惯用方法的简单示例。假设我们有一个数字列表 (L)，其中已经填充了一些数字，如下所示。
L = [_, _, _, 3, _, _, _, 4, _, _, 2, _]
我想说的是，一个固定数的左右两边的数字必须相加。上述问题的可能解决方案是：
L = [0, 0, 1, 3, 0, 1, 1, 4, 2, 0, 2, 0]
当然还有其他解决方案。我的第一种方法是这样的：
- 搜索第一个 pivot 数字；
- 获取pivot的左右子列表；
Append两个列表；- 使用谓词
sum/3，将结果列表约束为#=到主元。
这会是理想主义吗？我错过了更明显的东西吗？
级别 2. 我认为谓词 sum/3 完成了大部分工作。让我们稍微改变一下问题：
主元左边和右边的连续 1 串必须和主元相加。
鉴于此：
L = [_, _, _, 3, _, _, _, 5, _, _, 2, _]
可能的解决方案是：
L = [0, 0, 0, 3, 1, 1, 1, 5, 1, 1, 2, 0]
现在更棘手了...我想说的是，主元 N 的附加左右子列表必须包含长度为 N 的 1 子列表。这有意义吗？我如何使用 CLP(FD) 来表达这些内容？
"The solution that could have been"
您的推理是完全正确的，并且会奏效。
不过，它在一个关键方面有不足：您的描述目前非常强制性，如果按照您描述的方式实现，那么您将能够解决给定 个实例，但您不能 能够使用相同的 程序来生成 个这样的拼图实例。
让我更详细地解释一下我的意思。
干净的表示
我们从 表示 此类谜题开始。您目前正在使用：
L = [_, _, _, 3, _, _, _, 4, _, _, 2, _]
这称为 默认 表示，因为您无法清楚地区分不同的情况。如果你从逻辑上思考，并且认为这是一个 "instance" 的谜题，那么任何 更特殊的 这个术语 的情况必须 被视为实例的更具体案例，例如部分或完整的解决方案。但在这种表示中，不是这种情况，因为实例化其中一个参数 further 突然将它变成一个完全不同的实例，而不仅仅是一个更多的实例具体表现。
因此，这是此类谜题的干净表示：
example([?,?,?,p(3),?,?,?,p(4),?,?,p(2),?]).
在这里，我用不同的术语来区分这两种可能的情况。我正在使用：
- 未知的原子
?整数 - 形式为
p(P)的术语表示 pivot 元素P.
很多其他的表示都是可能的，如果你需要表达变量 sharing，你可以使用 i(I) 来表示一个未知的整数 I .关键是您可以通过 模式匹配 而不是测试 实例化 的非单调构造来区分案例。这是通用解决方案的关键，可用于所有方向。
声明式任务描述
让我们重新考虑一下您给出的命令式描述：
- "搜索 第一个主元数"
- "获取枢轴的左右子列表"
- "附加两个列表"
现在让我们声明性地表达这个。我们必须避免 命令式[=231=]，例如 "search"、"get" 和 "append"，因为这些都暗示着特定的 方向使用。
声明性描述可能如下所示：我们正在描述形式为 Lefts-Pivot-Rights 的 三元组 ，其中以下持有：
The sum of integers
LeftsandRightsis equal toPivot.
如果我们设法编写一个 Prolog 程序来描述 此类三元组并绘制从任务实例到此类三元组的合适连接，那么我们就完成了并且可以在所有方向。
转换为三元组
处理干净的表示很有趣，我们可以轻松地将它们转换为其他形式，因为我们可以很容易地区分大小写。因此，让我们现在将实例转换为三元组，我们可以更容易地推理。
让我们反映一下任务表示：它是一个 list 元素。在 Prolog 中 describing 列表时，DCG notation (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.
由此可见，我把"searching what is where and how far"的复杂推理去掉了。相反，它是实例和表单列表之间的简单通用 关系 ：
[Left0,Pivot0,Right0,Left1,Pivot1,Right1,Left2,...]
其中 "triples" 是隐式的，可以按如下方式分组：
[(Left0,Pivot0,Right0),(Left1,Pivot1,Right1),...]
此外，Rightn 与 Leftn+ 相同 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.
我已经突出显示了 "triple" 表示。
胜利的普遍性
现在关键点：所有这些都是完全通用，我们可以用它来生成实例本身！
示例：
?- 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]] .
这是自然思考关系并使用清晰表示[=]的副产品230=].
我将更具体的第二个问题作为第一个练习留给您。我希望上面显示的原则可以帮助您找到一个 clean 和 general 的解决方案，让您发挥逻辑编程的最大优势。
作为第二个练习，我将重写上面的代码以使用 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。
困难的部分
作为第三个也是最后一个练习，我留下了最难的一个：重读我写的东西并找到我所在的所有实例，使用命令式[=231=]措辞，没有公正地对待实际实施的内容的普遍性，改写它以反映实际情况。
我举个例子：我说"Extracting the variables"，还有什么更自然的，对吧？但我实际上已经实现了一个完整的变量和三元组之间的关系，你可以用它来：
- 从三元组中提取变量
- 测试这些变量是否对应给定的三元组
- 生成变量和三元组
- 等等
例如，我们可以使用最一般的查询:
?- phrase(variables(Ts), Vs). Ts = Vs, Vs = [] ; Ts = [[], _1960, []], Vs = [] ; Ts = [[], _1960, [], [], _1978, []], Vs = [] ; Ts = [[], _1960, [], [], _1978, [], [], _1996, []], Vs = [] .
这当然不是一个非常公平的枚举，但它远远超出了提取的范围，因为nothing at all 甚至在查询中给出。
你怎么地道！
所以，回答你的问题：在我看来，我们认为 最惯用的 Prolog 那些最令人印象深刻地展示了声明性属性的解决方案 我们期望从 关系 和逻辑程序的独特优势，例如：
- 可在所有方向使用
- 承认阅读更具体或更一般
- 使用反映关系普遍性的名称。
一个优雅、惯用的 Prolog 解决方案通常从实例的清晰表示和描述性谓词名称开始。