Prolog 中的约束

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

我正在尝试生成 6 个大小为 2N 的 0 和 1 向量，检查用 XOR 运算编写的约束、字典顺序和辛积（接近标量积）定义为：

如果 u = (u1, ..., uN, u_{N+1}, ..., u_{2N}) 且 v = (v1, ..., vN, v_{N+1}, .. . , v_{2N} ) 那么 西格玛(u,v)= u1vN + u2v_{N+1} + ... + u_{N}v_{2N} + u_Nv_1 + ... + u_{2N}*v_N

大约有 15 个限制，我知道有几种解决方案。

我的问题是，只要我设置 3 或 4 个约束，Prolog 就会给我 .false...所以我的代码中有问题，我完全陷入困境。

这是代码：

% Appel automatique à CLP(fd)
:- use_module(library(clpfd)).


% ordre lexicographique
leq([0],[1]).

leq([X|C1],[X|C2]):-
    leq(C1,C2).

leq([0|_],[1|_]).
    
% liste de listes de taille N
lengthliste([X],N):-
    length(X,N).
    
lengthliste([X|L],N):-
    length(X,N),
    lengthliste(L,N).
    


% xor

xor(0,0,0).
xor(1,0,1).
xor(0,1,1).
xor(1,1,0).

xorListe([X1],[X2],[X]):-
    !,xor(X1,X2,X).
    
xorListe([X1|L1],[X2|L2],[X|L]):-
    xor(X1,X2,X),
    xorListe(L1,L2,L),
    !.
    

% on calcule sigma(u,v) en faisant le produit scalaire entre u1,...,uN,uN+1,..U2N et vN+1,...,v2N,v1,...,vN

% on coupe L en un morceau de taille N et un autre
split(L,0,[],L).

split([X|Xs],N,[X|Ys],Zs) :- N1 is N - 1, split(Xs,N1,Ys,Zs).


% produit scalaire
ps([X1],[Y1],Res):-
    Res is X1*Y1.

ps([X1|L1],[X2|L2],Res):-
    ps(L1,L2,Res2),!,
    Res is xor(X1*X2, Res2).

% produit symplectique
sigma(O1,O2,N,Res):-
    split(O2,N,Moitie1,Moitie2),
    append(Moitie2,Moitie1,NewO2),
    ps(O1,NewO2,Res),!.
        





contraintes(O1,O2,O3,O4,O5,C, N):-
    NN is 2*N,
    length(O1,NN),
    length(O2,NN),
    length(O3,NN),
    length(O4,NN),
    length(O5,NN),
    length(C,NN),
    O1 ins {0,1},
    O2 ins {0,1},
    O3 ins {0,1},
    O4 ins {0,1},
    O5 ins {0,1},
    C ins {0,1},
    xorListeListe([O1,O2,O3,O4],O5),
    xorListe(C,O1,D1),
    xorListe(C,O2,D2),
    xorListe(C,O3,D3),
    xorListe(D3,O5,D4),
    xorListe(D3,O4,D5),
    xorListe(D2,O4,D6),
    xorListe(D2,O5,D7),
    xorListe(D1,O4,D8),
    xorListe(D1,O5,D9),
    leq(O1, C),
    leq(O1, O2),
    leq(O2, O3),
    leq(O3, O4),
    leq(O4, O5),
    leq(O1,D1),
    leq(O2,D2),
    leq(O2,D3),
    leq(O1,D4),
    leq(O1,D5),
    leq(O1,D6),
    leq(O1,D7),
    leq(O2,D8),
    leq(O2,D9),
    sigma(O1,O2,N,1),
    sigma(O1,O3,N,1),
    sigma(O1,O4,N,1),
    sigma(O1,O5,N,1),
    sigma(O2,O3,N,1),
    sigma(O2,O4,N,1),
    sigma(O2,O5,N,1),
    sigma(O3,O4,N,1),
    sigma(O3,O5,N,1),
    sigma(O4,O5,N,1),
    sigma(O4,C,N,1),
    sigma(O1,C,N,0),
    sigma(O2,C,N,0),
    sigma(O3,C,N,0),
    labeling([],[O1,O2,O3,O4,O5,C]).

谢谢你，周日快乐

我的代码有问题，我完全陷入困境。

prolog constraints
1个回答
0
投票

下面的代码给了我N=2的唯一解决方案，我删除了剪切，我不得不注释掉标签指令，我不知道为什么。

对于N=3，程序已经运行了几分钟，但我仍然没有结果......

欢迎任何评论：



% Appel automatique à CLP(fd)



:- use_module(library(clpfd)).


% ordre lexicographique
leq([0],[1]).


leq([X|C1],[X|C2]):-
leq(C1,C2).


leq([0|],[1|]).


% liste de listes de taille N
lengthliste([X],N):-
length(X,N).


lengthliste([X|L],N):-
length(X,N),
lengthliste(L,N).


% xor


xor(0,0,0).
xor(1,0,1).
xor(0,1,1).
xor(1,1,0).


xorListe([X1],[X2],[X]):-
xor(X1,X2,X).


xorListe([X1|L1],[X2|L2],[X|L]):-
xor(X1,X2,X),
xorListe(L1,L2,L),
xorListe(L1, L2, L).


xorListeListe([X1,X2],L):-
xorListe(X1,X2,L).


xorListeListe([X1|X],L):-
xorListeListe(X,LL),
xorListe(X1,LL,L).


% on calcule sigma(u,v) en faisant le produit scalaire entre u1,...,uN,uN+1,..U2N et vN+1,...,v2N,v1,...,vN


% on coupe L en un morceau de taille N et un autre
split(L,0,[],L).


split([X|Xs],N,[X|Ys],Zs) :- N1 is N - 1, split(Xs,N1,Ys,Zs).


% produit scalaire
ps([X1],[Y1],Res):-
Res is X1*Y1.


ps([X1|L1],[X2|L2],Res):-
ps(L1,L2,Res2),!,
Res is xor(X1*X2, Res2).


% produit symplectique
sigma(O1,O2,N,Res):-
split(O2,N,Moitie1,Moitie2),
append(Moitie2,Moitie1,NewO2),
ps(O1,NewO2,Res),!.


contraintes(O1,O2,O3,O4,O5,C, N):-
NN is 2*N,
length(O1,NN),
length(O2,NN),
length(O3,NN),
length(O4,NN),
length(O5,NN),
length(C,NN),
O1 ins {0,1},
O2 ins {0,1},
O3 ins {0,1},
O4 ins {0,1},
O5 ins {0,1},
C ins {0,1},
xorListeListe([O1,O2,O3,O4],O5),
xorListe(C,O1,D1),
xorListe(C,O2,D2),
xorListe(C,O3,D3),
xorListe(D3,O5,D4),
xorListe(D3,O4,D5),
xorListe(D2,O4,D6),
xorListe(D2,O5,D7),
xorListe(D1,O4,D8),
xorListe(D1,O5,D9),
leq(O1, C),
leq(O1, O2),
leq(O2, O3),
leq(O3, O4),
leq(O4, O5),
leq(O1,D1),
leq(O2,D2),
leq(O2,D3),
leq(O1,D4),
leq(O1,D5),
leq(O1,D6),
leq(O1,D7),
leq(O2,D8),
leq(O2,D9),
sigma(O1,O2,N,1),
sigma(O1,O3,N,1),
sigma(O1,O4,N,1),
sigma(O1,O5,N,1),
sigma(O2,O3,N,1),
sigma(O2,O4,N,1),
sigma(O2,O5,N,1),
sigma(O3,O4,N,1),
sigma(O3,O5,N,1),
sigma(O4,O5,N,1),
sigma(O4,C,N,1),
sigma(O1,C,N,0),
sigma(O2,C,N,0),
sigma(O3,C,N,0).
%labeling([],[O1,O2,O3,O4,O5,C]).
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.