Подсчет решений в CSP

Question

Я использую пролог, и у меня есть этот код:

:- use_module(library(clpb)).

fun(A, B, C, D, E) :-
  sat(A + B + C + D),
  sat(E),
  labeling([A, B, C, D, E]).

Если я хочу посчитать все решения, как я могу это сделать? Я читал о sat_count(+Expr, -Count), используемом в clpb, но я не могу реализовать это без ошибок

Answer 1

Перебор

Простой способ подсчитать количество решений - это сгенерировать их и посмотреть, сколько их существует.

Например, с программой, которую вы разместили, мы можем использовать findall/3 следующим образом получить ответ:

? - findall (., веселье (A, B, C, D, E), Ls),
   длина (Ls, L).
Ls = ['.', '.', '.', '.', '.', '.', '.', '.', '.' |...],L = 15

Конечно, это очень плохо масштабируется и быстро становится невозможным в более сложных случаях. Тем не менее, в этом примере этой стратегии достаточно.

Альтернатива: sat_count/2

С CLP(B) мы имеем sat_count/2 что вы уже обнаружили.

Основное преимущество sat_count/2 является то, что мы можем подсчитать количество решений, не перечисляя их. Это, конечно, очень удобно, когда есть очень много решений.

Хитрость в использовании sat_count/2 это избежать labeling/1и напишите свое основное отношение таким образом, чтобы оно только размещало ограничения.

Например:

веселье (A, B, C, D, E):- сб (A + B + C + D), сб (E).

Это имеет несколько преимуществ. Прежде всего, теперь мы можем запросить:

? - весело (A, B, C, D, E).Е = 1,
сб (A=\= ... # ... # B#B*C#B*C*D#B*D#C#C*D#D).

Этот ответ показывает, что E обязательно 1! Если бы мы использовали labeling/1это было бы несколько сложнее увидеть.

Кроме того, после публикации соответствующих ограничений, мы можем использовать sat_count/2предоставляя в качестве первого аргумента выражение CLP(B), которое должно соответствовать действительности.

В нашем случае мы не хотим накладывать дополнительные ограничения на решение, поэтому мы указываем в качестве первого аргумента тавтологию, которая содержит переменные, которые нас интересуют. Подходящей идиомой для этого является +[1|Vs],

Итак, мы можем использовать:

? - веселье (A, B, C, D, E),
   sat_count (+ [1, A, B, C, D, E], Count).
Е = 1,Количество = 15,
сб (A=\= ... # ... # B#B*C#B*C*D#B*D#C#C*D#D).

Резюме

В этом конкретном случае количество решений настолько мало, что между этими двумя подходами почти нет различий.

Тем не менее, я хотел бы подчеркнуть важный общий принцип при написании программ логики ограничений:

Рекомендуется отделить основное отношение от фактического поиска решений (labeling/1 и аналогичные предикаты, как встроенные, так и написанные вручную).

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

Более того, это позволяет вам попробовать разные стратегии поиска без перекомпиляции вашей программы!