Снижение ограничений в Prolog

Question

Снижение ограничений в 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. Этот вариант кажется - казался - подходящим для Prolog, учитывая то немногое, что я о нем знаю: логическое программирование, решение ограничений и т. Д.

Я смог собрать рабочую версию этого с некоторой помощью, и я нашел время, чтобы прочитать несколько руководств по программированию CHR. Думаю, я в основном понимаю, что ниже мы говорим, что если мы знаем 10a(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).... Или будет?
Решит ли это мою проблему "поиска", так что 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)по моему запросу. ~~Я считаю, что "остатки" превращаются в руду, что в данном случае не то, что я хочу (хотя это, конечно, указано).~~ Вaтеперь удаляются слишком рано, т. е. это правильно, но не минимально. Как предпочесть целые реакции? Хм...

2

prolog swi-prolog clpfd constraint-handling-rules

Источник

user4400820 16 дек '19 в 00:30

1 ответ

Другие вопросы по тегам prolog swi-prolog clpfd constraint-handling-rules

user4400820 16 дек '19 в 19:20 2019-12-16 19:20 · Answer 1 · 2019-12-16 19:20

Я смог получить точный ответ, используя

%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 а, где X+Y > 10, то мы можем сделать это с 10 рудой, но у нас 10-(X+Y)остаток; а также
Если нам нужно X+Y а, где X+Y < 10, то мы также можем сделать это с 10 рудой и без остатков (к сожалению, мы никогда не видим потерянных как).

Я считаю, что упорядочение просит пролог предпочесть первое правило, которое помогает с нашей проблемой минимизации. Однако мне еще предстоит протестировать эту стратегию на других версиях проблемы - я подозреваю, что невидимые отходы производства могут меня укусить.

Это дает

?- 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).