减少Prolog中的约束

问题描述 投票：1回答：1

[One of the recent Advent of code challenges要求我解决最少量的输入材料，我可以使用这些输入材料来应用给定的一组反应并获得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中的大多数挑战。鉴于我对此了解甚少，这似乎似乎很适合Prolog，例如：逻辑编程，约束求解等。I was able to put together a working version of this, with some help，我有时间阅读一些有关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) 

并且以某种方式告诉序言，如果我“知道”，例如a(8)，我仍然可以替换该ore(10)（因为我需要10颗矿石才能制造出这8颗矿石，有些已经被浪费掉了。]]
我
认为
如果我可以做到这一点，我可以打开此输出?- 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)添加到燃料查询中，则得到正确的总矿石。
总结一下，

    我如何表达不能部分运行反应的约束，但我可以运行该反应以获得超出所需的限制？换句话说，如果我需要a(8)，就足以知道我需要a(10)吗？我认为，这也将使我能够使用a(10) <=> ore(10)之类的语言而不是荒谬的a(1),a(1)...来编写原始问题说明。还是会？
  1. 这是否可以解决我的“搜索”问题，例如fuel(1)会给我ore:total_ore(31)？
  2. 更新：我花了一些时间玩（1）来获得

    3. %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)。 
我相信“剩菜”将转化为矿石，在这种情况下，这不是我想要的（尽管它是明确指定的。）> a现在被过早移除，即正确但并非最小。如何首选
整个反应？嗯...
最近的代码问世之一挑战我，要求我解决可用于应用给定一组反应并获得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, 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的约束条件说>>

如果我们需要X+Y a，其中X+Y > 10，那么我们可以用10矿石来做，但是剩下10-(X+Y)；和

如果我们需要X+Y a，其中X+Y < 10，那么我们也可以使用10块矿石而没有剩余物（不幸的是，我们永远不会看到浪费的情况）。

    我相信该命令要求序言更喜欢第一条规则，这有助于解决我们的最小化问题。但是，我还没有在其他版本的问题上测试这种策略–我怀疑生产中的无形浪费可能会咬我。
  1. 这给
  2. ?- fuel(1). ore:total_ore(31)

    3. 对于更复杂的问题，关键是这样：每当反应产生x的1，并使用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).
prolog swi-prolog clpfd constraint-handling-rules
1个回答
0
投票
a的约束条件说>>

如果我们需要X+Y a，其中X+Y > 10，那么我们可以用10矿石来做，但是剩下10-(X+Y)；和
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.