Вы так и не определили, чем может быть S.
Добавьте edge(S,Z)
в тело правила в строке 7, чтобы избавиться от этой ошибки. Или, если вы хотите определить предикат вершины, вы также можете использовать vertex(S)
.
Поэтому я исправил ваш код с помощью списков минусов. Этот подход необычен, потому что списки не являются ключевой функцией asp, как в прологе. Хорошо, вот мое решение (работает для ориентированных графов):
edge(a,b).
edge(a,c).
edge(b,c).
edge(c,a).
edge(c,d).
edge(d,b).
node(X) :- edge(X,_). % get nodes
node(X) :- edge(_,X). % get nodes
num(N):- {node(X)} == N. % count nodes
step(1..N) :- num(N). % mark possible steps
path(X,Y,2,cons(X,cons(Y,empty))) :- edge(X,Y).
path(A,C,NN+1,cons(A,L)) :- edge(A,B), path(B,C,NN,L), step(NN+1).
member(X,path(X,Y,N,cons(X,L))) :- path(X,Y,N,cons(X,L)).
member(Y,path(X,Y,N,cons(X,L))) :- path(X,Y,N,cons(X,L)).
member(M,path(S,T,NN+1,cons(S,cons(Z,L)))) :- member(M,path(Z,T,NN,cons(Z,L))), path(S,T,NN+1,cons(S,cons(Z,L))).
track(Y,Z,N,L):- {member(X,path(Y,Z,N,L)):node(X)} == N, path(Y,Z,N,L).
#show track/4.
Сначала вам нужно знать все вершины, чтобы вычислить их количество. Также я ввел предикат step
для проверки глубины пути. path
теперь также имеет счетчик глубины в качестве третьего аргумента. Все возможные пути хранятся в пределах path/4
, разрешены циклы. Предикат member/2
генерируется для отображения всех вершин-членов в пределах path/4
. На последнем шаге все пути перенаправляются к предикату track/4
тогда и только тогда, когда количество различных вершин-членов равно длине пути. Поскольку дубликаты не учитываются, это условие гарантирует, что будут пересылаться только пути без циклов. Обратите внимание, что все вышеперечисленные шаги являются принудительными. Для каждого графика существует ровно один набор ответов.
Итак, давайте посмотрим на более похожее на ASP решение. Обычно вы задаете конкретный вопрос («путь от a до b длины n») вместо общего («все возможные пути от всех узлов ко всем узлам любой возможной длины»). Следующий код должен иметь начальный узел (start/1
) и конечный узел (end/1
). Программа устанавливает (случайный) порядок, присваивая каждой вершине в предикате order/2
ровно один порядковый номер. Предикат order
копируется в предикат пути до тех пор, пока индекс не превышает индекс конечного узла (path(S,N):- order(S,N), maxZ(Z), S<=Z.
). Единственным ограничением является то, что в порядке пути каждые 2 соседние вершины связаны ребром. Линия ограничения читается как Не может быть случая, когда есть узел S1 в позиции N внутри пути и узел S2 в позиции N+1 внутри пути и нет ребра от S1 до S2 эм>.
edge(a,b).
edge(a,c).
edge(b,c).
edge(c,a).
edge(c,d).
edge(d,b).
start(a).
end(d).
node(X) :- edge(X,_). % get nodes
node(X) :- edge(_,X). % get nodes
num(N):- {node(X)} == N. % count nodes
step(1..N) :- num(N). % mark possible steps
order(1,A):- start(A). % start has index 1
maxZ(Z):- end(E), order(Z,E), step(Z). % end has index maxZ
{order(S,N):node(N)} == 1 :- step(S). % exactly one assignment per step
{order(S,N):step(S)} == 1 :- node(N). % exactly one assignment per node
path(S,N):- order(S,N), maxZ(Z), S<=Z. % copy order when index is not largter than end node index
:- path(N, S1), path(N+1, S2), not edge(S1,S2). % successing indices are connected through edges
#show path/2.
person
DuDa
schedule
25.11.2020