1

我正在尝试解决荷兰国旗问题。基本上，给定一个列表，我想按照红-白-蓝的顺序对它们进行排序。红色、白色和蓝色由它们的谓词定义（即红色（x）、白色（x）等）。目前，我有以下代码：

red(1).
white(2).
blue(3).

dutch(Xs,Ys):- 
    getRed(Xs,[], Red), getWhite(Xs,[],White), getBlue(Xs,[],Blue), 
    append([], Red, Y1), append(Y1, White, Y2), append(Y2, Blue, Ys).

getRed([],Rs,Rs).
getRed([X|Rest], Acc, Rs) :- red(X), getRed(Rest, [X,Acc] , Rs).
getRed([X|Rest], Acc, Rs) :- getRed(Rest, Acc, Rs).

getWhite([],Rs,Rs).    
getWhite([X|Rest], Acc, Rs) :- white(X), getWhite(Rest, [X,Acc], Rs).
getWhite([X|Rest], Acc, Rs) :- getWhite(Rest, Acc, Rs).

getBlue([],Rs,Rs).
getBlue([X|Rest], Acc, Rs) :- blue(X), getBlue(Rest, [X,Acc], Rs).    
getBlue([X|Rest], Acc, Rs) :- getBlue(Rest, Acc, Rs).

我的输出如下所示：

?- dutch([1,2,3],R).
R = [1, [], 2, [], 3, []]
R = [1, [], 2, []]
R = [1, [], 3, []]
R = [1, []]
R = [2, [], 3, []]
R = [3, []]
R = []

我想要的是它看起来像这样：

R = [1, 2, 3]

我已经尝试了几种方法来强制输出我想要的，但一直无法接近。

编辑：看起来我可以通过使用置换所有可能集合并评估集合是否按“荷兰国旗”顺序的蛮力解决方案来解决它。不过有更好的解决方案吗？

4

2 回答 2

1

纯溶液

前言

我想为现有的解决方案添加一个纯粹的关系解决方案。

理想情况下，您可以在所有方向上使用 Prolog 谓词，现在我将展示一个可以让您这样做的实现：您不仅可以根据您的标准对实例化列表进行排序，不，您还可以生成解决方案并完成部分实例化的解决方案.

为此，我使用了if_/3来自library(reif).

具体化谓词

我从您的谓词的具体化版本开始，也冒昧地使用更具说服力的名称red，white并blue表示颜色：

红色（R，T）：- =（R，红色，T）。

白色（W，T）：- =（W，白色，T）。

蓝色（B，T）：- =（B，蓝色，T）。

注意我正在使用(=)/3，它与library(reif).

使用 DCG 描述列表

接下来，纯粹为了方便，我使用符号来描述感兴趣的子序列：

红色（[]）-> []。
红色（卢比）-->
        [R],
        { if_(red(R), Rs = [R|Rest], Rs = Rest) },
        红色（休息）。

白人（[]）-> []。
白人（Ws）-> [W]，
        { if_(white(W), Ws = [W|Rest], Ws = Rest) },
        白人（休息）。

蓝调（[]）-> []。
布鲁斯（Bs）-> [B]，
        { if_(blue(B), Bs = [B|Rest], Bs = Rest) },
        布鲁斯（休息）。

我把这个变得更简洁作为一个简单的练习。

解决方案

通过这些构建块，我们可以表达整体解决方案：

荷兰语（颜色，Ds）：-
        短语（红色（Rs），颜色），
        短语（白人（Ws），颜色），
        短语（蓝调（Bs），颜色），
        短语（（Rs，Ws，Bs），Ds）。

例子

当然，这适用于简单的实例化案例，例如：

?- 荷兰语（[红色，白色，蓝色]，Ds）。
Ds = [红、白、蓝]；
错误的。

现在重点：这也适用于最一般的情况，其中所有参数都是变量：

?-长度（Cs，_），荷兰语（Cs，Ds）。
Cs = Ds，Ds = []；
Cs = Ds，Ds = [红色]；
Cs = Ds，Ds = [白色]；
Cs = Ds，Ds = [蓝色]；
Cs = [_G1322],
Ds = [],
差异（_G1322，蓝色），
差异（_G1322，白色），
差异（_G1322，红色）；
Cs = Ds，Ds = [红色，红色]；
Cs = Ds，Ds = [红，白]；
Cs = Ds，Ds = [红，蓝]；
Cs = [红色，_G1340]，
Ds = [红色]，
差异（_G1340，蓝色），
差异（_G1340，白色），
差异（_G1340，红色）。

通过添加更多目标，我们可以专门化这个查询来观察现在生成的具体解决方案：

?- 长度(Cs, _), Cs = [_,_,_|_] , 荷兰语(Cs, Ds), ground(Cs)。
Cs = Ds，Ds = [红，红，红]；
Cs = Ds，Ds = [红、红、白]；
Cs = Ds，Ds = [红、红、蓝]；
Cs = [红，白，红]，
Ds = [红、红、白]；
Cs = [红，蓝，红]，
Ds = [红，红，蓝]。

将此与其他答案进行比较，后者不能用于公平枚举解决方案：

?-长度(Xs, _), Xs = [_,_,_|_], 荷兰语(Xs, Ys)。
Xs = Ys, Ys = [1, 1, 1] ;
Xs = Ys, Ys = [1, 1, 1, 1] ;
Xs = Ys, Ys = [1, 1, 1, 1, 1] ;
Xs = Ys, Ys = [1, 1, 1, 1, 1, 1] ;
Xs = Ys, Ys = [1, 1, 1, 1, 1, 1, 1]。

概括

因此，通过保留，我们得到了一个更通用的逻辑程序，我们可以在各个方向上使用它。

诚然，您没有要求这种概括性。但是，当我们这样做的时候，为什么要放弃它呢？

于 2016-10-26T09:10:37.517 回答
0

我在您的代码中看到两个错误：

1）您的终端子句getRed([],Rs,Rs), getWhite([],Rs,Rs),getBlue([],Rs,Rs)接受空列表作为值结果（当Rs等于 时[]）；我建议将它们重写为

getRed([],Rs,Rs)   :- Rs \= [].
getWhite([],Rs,Rs) :- Rs \= [].
getBlue([],Rs,Rs)  :- Rs \= [].

2）在接受子句中（X搜索的颜色是什么时候），当你应该使用管道（[X,Acc];应该是（[X|Acc]）时，你用逗号将它添加到累加器中；我建议将它们重写为

getRed([X|Rest], Acc, Rs)   :- red(X),   getRed(Rest, [X|Acc], Rs).
getWhite([X|Rest], Acc, Rs) :- white(X), getWhite(Rest, [X|Acc] , Rs).
getBlue([X|Rest], Acc, Rs)  :- blue(X),  getBlue(Rest, [X|Acc], Rs).

题外话：没有理由追加Red到空列表；结果列表 ( Y1) 是Red它本身；我建议简化

append([], Red, Y1), append(Y1, White, Y2), append(Y2, Blue, Ys)

如下

append(Red, White, Mid), append(Mid, Blue, Ys)

- - 编辑 - -

不知道你到底想要什么，但我怀疑第三个版本条款中的第三个错误：什么时候X没有累积。

我认为您应该添加一个检查以确保这X不是搜索的颜色；我建议将它们重写如下

getRed([X|Rest], Acc, Rs)   :- \+ red(X),   getRed(Rest, Acc, Rs).
getWhite([X|Rest], Acc, Rs) :- \+ white(X), getWhite(Rest, Acc, Rs).
getBlue([X|Rest], Acc, Rs)  :- \+ blue(X),  getBlue(Rest, Acc, Rs).

--- 编辑 2 ---

getRed/3我认为您的,getWhite/3和getBlue/3子句中不需要累加器。

我提出了一个只有 2 个参数的版本

red(1).
white(2).
blue(3).

dutch(Xs,Ys):- 
    getRed(Xs, Red), getWhite(Xs, White), getBlue(Xs, Blue), 
    append(Red, White, Mid), append(Mid, Blue, Ys).

getRed([],[]).
getRed([X|Rest], [X|Rs]) :- red(X),    getRed(Rest, Rs).
getRed([X|Rest], Rs)     :- \+ red(X), getRed(Rest, Rs).

getWhite([],[]).
getWhite([X|Rest], [X|Rs]) :- white(X),    getWhite(Rest, Rs).
getWhite([X|Rest], Rs)     :- \+ white(X), getWhite(Rest, Rs).

getBlue([],[]).
getBlue([X|Rest], [X|Rs]) :- blue(X),    getBlue(Rest, Rs).
getBlue([X|Rest], Rs)     :- \+ blue(X), getBlue(Rest, Rs).
于 2016-10-25T13:33:15.443 回答