 |
|
Программы реализации клеточных автоматов.
Кле́точный автома́т (КА) — набор клеток, образующих некоторую периодическую решетку с заданными правилами перехода, определяющими состояние клетки в следующий момент времени через состояние клеток, находящимися от нее на расстоянии не больше некоторого, в текущий момент времени. Как правило, рассматриваются автоматы, где состояние определяется самой клеткой и ближайшими соседями. В качестве решетки обычно рассматривается кубическая решетка. Один из самых интересных примеров клеточного автомата — игра «Жизнь».
Отметим основные свойства классической модели клеточных автоматов.
• Локальность правил. На новое состояние клетки могут влиять только элементы её окрестности и, возможно, она сама;
• Однородность системы. Ни одна область решётки не может быть отличена от другой по каким-либо особенностям правил и т. п. Однако на практике решётка оказывается конечным множеством клеток (ведь невозможно выделить неограниченный объём данных). В результате могут иметь место краевые эффекты, клетки стоящие на границе решётки будут отличны от остальных по числу соседей. Во избежание этого можно ввести периодические краевые условия
• Множество возможных состояний клетки — конечно. Это условие необходимо, чтобы для получения нового состояния клетки требовалось конечное число операций. Отметим, что оно не мешает использовать клетки для хранения чисел с плавающей точкой при решении прикладных задач.
• Значения во всех клетках меняются единовременно, в конце итерации, а не по мере вычисления. В противном случае порядок перебора клеток решётки, при совершении итерации, существенно влиял бы на результат. Необходимо отметить, что на практике, при решении определённых задач, возникает потребность в том, чтобы отказаться от последних трёх свойств.
Пример реализации клет автомата 2
domains
i=integer
s=i*
database
ka(i,i,i,i) kb(i,i,i,i)
d(s)
n(real)
predicates
t(i,s)
ra(i,i,i,i) zb(i,i,i,i) za(i,i,i,i) mz(i,s) app(s,s,s) p(i,i,i,i)
ps(i,i,i) prs(i,i,i) pps(i,i) pls(i,i) pvs(i,i) pns(i,i)
automat(i)
risov(i,i,i)
delay(real)
clauses
mz(M,[M|_]).
app([],X,X):-!.
app([A|L1],L2,[A|L3]):-!,app(L1,L2,L3).
ra(A,X,Y,S):-retract(ka(A,X,Y,S)),
asserta(ka(A,X,Y,S)),!.
zb(A,X,Y,S):-assertz(kb(A,X,Y,S)).
za(A,X,Y,S):-retract(ka(_,_,_,_)),
assertz(ka(A,X,Y,S)),!.
t(V,L1):-retract(d(L0)),mz(V,L0),
ra(V,X,Y,S),p(V,X,Y,S),
M1=V+1,app([M1],L0,L1),
asserta(d(L1)).
p(A,X,Y,S):-ps(X,Y,K),K=2,zb(A,X,Y,S),!.
p(A,X,Y,_):-ps(X,Y,K),K=3,zb(A,X,Y,1),!.
p(A,X,Y,_):-zb(A,X,Y,0),!.
ps(X,Y,K):-pls(X,X1),prs(X1,Y,Z0),
pvs(Y,Y1),prs(X1,Y1,Z1),
pps(X,X2),prs(X,Y1,Z2),
pns(Y,Y2),prs(X2,Y1,Z3),
prs(X2,Y,Z4),prs(X2,Y2,Z5),
prs(X,Y2,Z6),prs(X1,Y2,Z7),
K=Z0+Z1+Z2+Z3+Z4+Z5+Z6+Z7,!.
prs(X,Y,Z):-ra(_,X,Y,S),S=1,Z=1.
prs(_,_,Z):-Z=0.
pls(X,X1):-X>0,X1=X-1.
pls(_,X1):-X1=4.
pvs(X,X1):-X>0,X1=X-1.
pvs(_,X1):-X1=4.
pps(X,X1):-X<4,X1=X+1.
pps(_,X1):-X1=0.
pns(X,X1):-X<4,X1=X+1.
pns(_,X1):-X1=0.
automat(0).
automat(I):-delay(40000),
L0=[0],asserta(d(L0)),!,
t(V,_),V=24,retract(d(_)),
retract(kb(AA,XX,YY,SS)),risov(XX,YY,SS),
za(AA,XX,YY,SS),AA=24,I1=I-1,automat(I1).
risov(X,Y,0):-X1=2*X+100,Y1=2*Y+100,
putpixel(X1,Y1,0).
risov(X,Y,1):-X1=2*X+100,Y1=2*Y+100,
putpixel(X1,Y1,7).
delay(R):-asserta(n(0)),!,retract(n(R0)),
R1=R0+1,asserta(n(R1)),R<R1,retract(n(_)).
goal consult("iklet0.dba"),
initgraph(1,0,_,_,"c:\\prolog"),
setbkcolor(3),
automat(30),retract(ka(AJ,_,_,_)),
AJ=24.