时间戳

首页 > 解决方案 > 减少 Prolog 中的约束

prolog - 减少 Prolog 中的约束

问题描述

最近出现的代码挑战之一要求我解决最少量的输入材料，我可以使用这些材料来应用一组给定的反应并获得 1 个单位的输出材料。

例如，给定

10 ORE => 10 A
1 ORE => 1 B
7 A, 1 B => 1 C
7 A, 1 C => 1 D
7 A, 1 D => 1 E
7 A, 1 E => 1 FUEL

我们总共需要 31 块矿石来制造 1 种燃料（1 块用来生产单位 B，然后 30 块用来制造必需的 28 A）。

今年，我一直在努力拓展我的编程语言视野，所以我已经完成了 SML/NJ 的大部分挑战。这个似乎——<em>似乎——很适合 Prolog，考虑到我对它的了解很少：逻辑编程、约束求解等。

在一些帮助下，我能够整理出一个工作版本，并且我抽出时间阅读了一些关于 CHR 编程的教程。我想我基本上明白，下面，我们说如果我们知道 10 个a(1)项目（这些被称为什么？证明？），那么我们可以将其替换为ore(10)- 将扩展为 10 个单独的ore(1)调用。

%prolog

:- module(ore, [ fuel/1 ]).
:- use_module(library(chr)).
:- use_module(library(clpfd)).

% constraint names
% ore and fuel are guaranteed
:- chr_constraint
    ore/1,
    a/1,
    b/1,
    c/1,
    d/1,
    e/1,
    fuel/1.

% problem constraints
a(1),a(1),a(1),a(1),a(1),a(1),a(1),a(1),a(1),a(1) <=> ore(10).
b(1) <=> ore(1).
c(1) <=> a(7), b(1).
d(1) <=> a(7), c(1).
e(1) <=> a(7), d(1).
fuel(1) <=> a(7), e(1).

% decompositions (one per element???)
a(X) <=> X #> 1, Y #= X-1 | a(Y), a(1).
b(X) <=> X #> 1, Y #= X-1 | b(Y), b(1).
c(X) <=> X #> 1, Y #= X-1 | a(Y), a(1).
d(X) <=> X #> 1, Y #= X-1 | d(Y), d(1).
e(X) <=> X #> 1, Y #= X-1 | e(Y), e(1).
ore(X) <=> X#> 1, Y #= X-1 | ore(Y), ore(1).

% aggregation (for convenience) 
% always present
:- chr_constraint ore_add/1, total_ore/1.

total_ore(A), total_ore(Total) <=> NewTotal #= A + Total, total_ore(NewTotal).

ore(1) <=> total_ore(1).

不过，如果能够编写以下内容，那就太好了：

a(10) <=> ore(10)

并以某种方式告诉 prolog，如果我“知道”，例如，a(8)我仍然可以替换它ore(10)（因为我需要 10 矿石来制造那些 8a，而有些只是浪费了）。

我认为如果我能做到这一点，我可以把这个输出

?- fuel(1).
ore:a(1),
ore:a(1),
ore:a(1),
ore:a(1),
ore:a(1),
ore:a(1),
ore:a(1),
ore:a(1),
ore:total_ore(21).

进入

?- fuel(1).
ore:total_ore(31).

如果我手动添加,ore:a(2)到燃料查询中，我会得到正确的总矿石。

总结一下，

  1. 我如何表达我不能部分运行反应，但我可以运行反应以获得比我需要的更多的约束？换句话说，如果我需要a(8)，就足以知道我需要a(10)吗？我认为，这也将允许我用类似的语言a(10) <=> ore(10)而不是荒谬的语言来编写原始问题陈述a(1),a(1)...。还是会？
  2. 这会解决我的“搜索”问题，这样fuel(1)会给我ore:total_ore(31)吗？

更新：我花了一些时间玩（1）来获得

%prolog

:- module(ore, [ fuel/1 ]).
:- use_module(library(chr)).
:- use_module(library(clpfd)).

% constraint names
% ore and fuel are guaranteed
:- chr_constraint
    ore/1,
    a/1,
    b/1,
    c/1,
    d/1,
    e/1,
    fuel/1.

% problem constraints
a(X) <=> X #>= 1, X #=< 10 | ore(10).
b(1) <=> ore(1).
c(1) <=> a(7), b(1).
d(1) <=> a(7), c(1).
e(1) <=> a(7), d(1).
fuel(1) <=> a(7), e(1).

% decompositions (one per element???)
b(X) <=> X #> 1, Y #= X-1 | b(Y), b(1).
c(X) <=> X #> 1, Y #= X-1 | a(Y), a(1).
d(X) <=> X #> 1, Y #= X-1 | d(Y), d(1).
e(X) <=> X #> 1, Y #= X-1 | e(Y), e(1).
ore(X) <=> X#> 1, Y #= X-1 | ore(Y), ore(1).

% aggregation (for convenience) 
% always present
:- chr_constraint ore_add/1, total_ore/1.

total_ore(A), total_ore(Total) <=> NewTotal #= A + Total, total_ore(NewTotal).

ore(1) <=> total_ore(1).

这total_ore(41)为我的查询产生了。我相信“剩菜”正在转化为矿石，在这种情况下，这不是我想要的（尽管它当然是指定的）。s现在a被删除得太早了——也就是说，这是正确的，但不是最小的。如何更喜欢整体反应？嗯……

标签： prologswi-prologclpfdconstraint-handling-rules

解决方案

我能够使用

%prolog

:- module(ore, [ fuel/1 ]).
:- use_module(library(chr)).
:- use_module(library(clpfd)).

% constraint names
% ore and fuel are guaranteed
:- chr_constraint
    ore/1,
    fuel/1.

% aggregation
% always present
:- chr_constraint ore_add/1, total_ore/1.
total_ore(A), total_ore(Total) <=> NewTotal #= A + Total, total_ore(NewTotal).
ore(X) <=> total_ore(X).

% BEGIN TO GENERATE

:- chr_constraint
    a/1,
    b/1,
    c/1,
    d/1,
    e/1.

% problem constraints (script to generate these?)
a(X), a(Y) <=> S #= X+Y, S #> 10, L #= S - 10 | ore(10), a(L).
a(X), a(Y) <=> S #= X+Y, S #=< 10 | ore(10).
b(1) <=> ore(1).
c(1) <=> a(7), b(1).
d(1) <=> a(7), c(1).
e(1) <=> a(7), d(1).
fuel(1) <=> a(7), e(1).

a说的限制

  1. 如果我们需要X+Ya, where X+Y > 10，那么我们可以用 10 块矿石来做，但是我们还有10-(X+Y)剩余的；和
  2. 如果我们需要X+Ya, where X+Y < 10，那么我们也可以使用 10 个矿石并且没有剩菜（不幸的是，我们从来没有看到浪费了）。

我相信排序要求 prolog 更喜欢第一条规则，这有助于我们的最小化问题。然而，我还没有在其他版本的问题上测试这个策略——我怀疑生产的无形浪费可能会咬我。

这给

?- fuel(1).
ore:total_ore(31)

对于更复杂的问题，关键是：每当反应产生 1 时x，使用，比如说n，a你可以将其编码为

x(X) <=> A #= X*n | a(A).

当反应产生A时x，您可以将其编码为

x(A) <=> ... .
x(X) <=> X #> A, L #= X - A | ..., x(L).
x(X), x(Y) <=> S #= X+Y, S #> A, L #= S - A | ..., x(L).
x(X), x(Y) <=> S #= X+Y, S #=< A | ... .

对于某些问题，但不是全部，您还需要以下内容 - 有时您需要它来处理剩菜，但其他时候，由于最小化，您希望避免此规则......尤其是当还有其他反应需要执行时.

x(X) <=> X #=< A | ... .

最后一点的一个很好的测试用例是

9 ORE => 2 A
8 ORE => 3 B
7 ORE => 5 C
3 A, 4 B => 1 AB
5 B, 7 C => 1 BC
4 C, 1 A => 1 CA
2 AB, 3 BC, 4 CA => 1 FUEL

这可以解决

%prolog

:- module(ore, [
    fuel/1,
    total_ore/1
    ]).
:- use_module(library(chr)).
:- use_module(library(clpfd)).

% constraint names
% ore and fuel are guaranteed
:- chr_constraint
    ore/1,
    fuel/1.

% aggregation
% always present
:- chr_constraint total_ore/1.
total_ore(A), total_ore(Total) <=> NewTotal #= A + Total, total_ore(NewTotal).
ore(X) <=> total_ore(X).

% BEGIN TO GENERATE

:- chr_constraint
    a/1,
    b/1,
    c/1,
    ab/1,
    bc/1,
    ca/1.

% 9 ORE => 2 A
% 8 ORE => 3 B
% 7 ORE => 5 C
% 3 A, 4 B => 1 AB
% 5 B, 7 C => 1 BC
% 4 C, 1 A => 1 CA
% 2 AB, 3 BC, 4 CA => 1 FUEL

% problem constraints (script to generate these?)
a(2) <=> ore(9).
a(X) <=> X #> 2, L #= X - 2 | ore(9), a(L).
a(X), a(Y) <=> S #= X+Y, S #> 2, L #= S - 2 | ore(9), a(L).
a(X), a(Y) <=> S #= X+Y, S #=< 2 | ore(9).
a(X) <=> X #< 2 | ore(9).
b(3) <=> ore(8).
b(X) <=> X #> 3, L #= X - 3 | ore(8), b(L).
b(X), b(Y) <=> S #= X+Y, S #> 3, L #= S - 3 | ore(8), b(L).
b(X), b(Y) <=> S #= X+Y, S #=< 3 | ore(8).
b(X) <=> X #<3 | ore(8).
c(5) <=> ore(7).
c(X) <=> X #> 5, L #= X - 5 | ore(7), c(L).
c(X), c(Y) <=> S #= X+Y, S #> 5, L #= S - 5 | ore(7), c(L).
c(X), c(Y) <=> S #= X+Y, S #=< 5 | ore(7).
a(X) <=> X #< 5 | ore(7).
ab(X) <=> A #= 3*X, B #= 4*X | a(A), b(B).
bc(X) <=> B #= 5*X, C #= 7*X | b(B), c(C).
ca(X) <=> A #= X, C #= 4*X | a(A), c(C).
fuel(1) <=> ab(2), bc(3), ca(4).

推荐阅读