3

1 と 0 のリストで連続する 1 の数を制限する非常に単純なオートマトンを実装したいと考えています ([0,1,1,0,1,1,1] など)。

私のオートマトンは次のようになります。

% 'Day' is a list of clpfd variables
% 'Allowed' is an integer
%
% consecutiveOnes(+Day, +Allowed)
consecutiveOnes(Day, Allowed) :-

    automaton(Day, _, Day,
        [source(n)],
        [
         arc(n, 0, n, [0]  ),
         arc(n, 1, n, [C+1])
        ],
        [C],
        [0],
        [_N]
    ).



% example 1:
%   consecutiveOnes([0,0,0,1,1,1], 2)  -> there are three consecutive 1s and we allow only 2 -> Fail.

% example 2:
%   consecutiveOnes([0,1,1,1,0,0], 2)  -> there are three consecutive 1s and we allow only 2 -> Fail.


% example 3:
%   consecutiveOnes([0,1,1,0,0,0], 2)  -> there are only two consecutive 1s and we allow 2 -> OK

上記の Prolog コードにカウンターC指定の制約を追加するにはどうすればよいですか?C <= Allowed

4

2 に答える 2

3

これを追加の状態で定式化するのが最善かもしれません。たとえば、最大 2 つの連続する 1 の場合:

:- use_module(library(clpfd)).

at_most_two_consecutive_ones(Day) :-
    automaton(Day,
        [source(n),sink(n),sink(n1),sink(n2)],
        [arc(n, 0, n),
         arc(n, 1, n1),
         arc(n1, 1, n2),
         arc(n1, 0, n),
         arc(n2, 1, false),
         arc(n2, 0, n)
        ]).

クエリの例:

?- at_most_two_consecutive_ones([0,0,0,1,1,1]).
false.

?- at_most_two_consecutive_ones([0,1,1,0,1,1]).
true.

?- at_most_two_consecutive_ones([0,1,1,0,1,0]).
true.

より一般的な解決策として、実行の最大長が与えられたときにオンデマンドでオートマトンを構築する必要があります。

于 2013-07-21T15:02:21.183 に答える