Взаимоисключающие события в прологе - PullRequest
Новая
       14

Взаимоисключающие события в прологе

0 голосов
/ 30 апреля 2018

Я хочу определить события в прологе, где, если одно происходит, другое не может.

Например, у меня есть 5 коробок разных размеров, скажем, 50,50,50,80,90 кв. См, и 4 места для хранения, и если я помещаю ящик в одно место для хранения, я хочу, чтобы его нельзя было хранить дважды , Кроме того, я хочу, чтобы общий размер хранилища составлял 230. Таким образом, по сути, я хочу рассчитать все возможные сценарии, где это может произойти и в каком ящике находится место для хранения.

Есть идеи, как это сделать?

Ответы [ 2 ]

0 голосов
/ 01 мая 2018

Моя интерпретация этого вопроса заключается в том, что вы ищете все перестановки элементов из списка [50, 50, 50, 80, 90] размером не более 4 и суммой не более 230. Решение здесь намеренно примитивное, не использует никаких симметрий, даже не равенство множественных вхождений числа 50.

Итак, давайте начнем с предиката, который описывает такие перестановки элементов списка с ограниченным размером. Проще всего использовать DCG, чтобы определить это: 

permuted_sublist(List, MaxLength, PermutedSublist) :-
    phrase(permuted_sublist(List, MaxLength), PermutedSublist).

permuted_sublist(_List, _N) -->
    [].
permuted_sublist(List, N) -->
    { N > 0 },
    { select(Element, List, List1) },
    [Element],
    { N1 is N - 1 },
    permuted_sublist(List1, N1).

Одна тонкость заключается в том, что заголовок первого предложения соответствует любой длине, а не только 0. Если мы введем 0 для _N, эта грамматика будет точно описывать подсписки длины данное число, но мы также хотим разрешить более короткие.

Тест: 

?- permuted_sublist([a, b, c, d, e], 2, Selection).
Selection = [] ;
Selection = [a] ;
Selection = [a, b] ;
Selection = [a, c] ;
Selection = [a, d] ;
Selection = [a, e] ;
Selection = [b] ;
Selection = [b, a] ;
Selection = [b, c] ;
Selection = [b, d] ;
Selection = [b, e] ;
Selection = [c] ;  % etc

Учитывая это, нам просто нужно добавить ограничение на сумму: 

placement(Sizes, Selection, Sum) :-
    permuted_sublist(Sizes, 4, Selection),
    sumlist(Selection, Sum),
    Sum =< 230.

И это ведет себя следующим образом: 

?- placement([50, 50, 50, 80, 90], Placement, Sum).
Placement = [],
Sum = 0 ;
Placement = [50],
Sum = 50 ;
Placement = [50, 50],
Sum = 100 ;
Placement = [50, 50, 50],
Sum = 150 ;
Placement = [50, 50, 50, 80],
Sum = 230 ;
Placement = [50, 50, 80],
Sum = 180 ;
Placement = [50, 50, 80, 50],
Sum = 230 ;  % etc

Опять же, в этом есть избыточность, которую можно уменьшить, заменив цель select/3 на append(_Prefix, [Element|List1], List).

0 голосов
/ 30 апреля 2018

Я бы смоделировал это с помощью термина и подпрограммы хранения, примерно так: 

% this is a start state
start(storage(empty, empty, empty, empty)).

Это дает вам 4 места для хранения. Теперь вам нужно правило для вставки в них. 

store(BoxSize, storage(empty, S2, S3, S4), storage(BoxSize, S2, S3, S4)).
store(BoxSize, storage(S1, empty, S3, S4), storage(S1, BoxSize, S3, S4)).
store(BoxSize, storage(S1, S2, empty, S4), storage(S1, S2, BoxSize, S4)).
store(BoxSize, storage(S1, S2, S3, empty), storage(S1, S2, S3, BoxSize)).

Это определяет store/3, который принимает новый блок (представленный его размером) и вашу структуру из 4 областей памяти, и помещает этот блок в следующую пустую корзину в ваших областях памяти.

Теперь вы можете легко подсчитать, сколько места вы используете: 

total(storage(S1, S2, S3, S4), Total) :-
    findall(N, (member(N, [S1, S2, S3, S4]), number(N)), Sizes),
    sumlist(Sizes, Total).

Соблазнительно написать Total is S1+S2+S3+S4, но это не удастся, если какой-либо контейнер пуст.

Вот как вы используете то, что мы построили здесь: 

?- start(Store), store(40, Store, NewStore), 
   store(50, NewStore, NewerStore), total(NewerStore, Total).
Store = storage(empty, empty, empty, empty),
NewStore = storage(40, empty, empty, empty),
NewerStore = storage(40, 50, empty, empty),
Total = 90 ;
Store = storage(empty, empty, empty, empty),
NewStore = storage(40, empty, empty, empty),
NewerStore = storage(40, empty, 50, empty),
Total = 90 ;

Как вы видите, мы можем добавлять вещи в магазин, и это дает нам альтернативные решения, перемещая корзины в разные слоты. Нанизывать состояние вокруг вручную не очень весело; вы, вероятно, записали бы это как свертку или использовали бы phrase/3 для обработки состояния, чтобы вам не нужно было создавать промежуточные состояния.

Я не совсем уверен, что вы пытаетесь сделать в отношении вашего списка из пяти пунктов. Поэтому вам, вероятно, придется взять его отсюда, чтобы выяснить, как вы хотите вставить их и удовлетворить свои ограничения. Я предполагаю, что вы хотите что-то сделать с select/3, где вы положите их в мусорные ведра, получите размер и забудете обо всем, что осталось.

...