Длина и путь в графах Пролог (избегайте бесконечной рекурсии для циклов) - PullRequest
Новая
       47

Длина и путь в графах Пролог (избегайте бесконечной рекурсии для циклов)

0 голосов
/ 16 февраля 2019 
node(a).
node(b).
node(c).
node(d).
node(e).
node(f).
node(g).
node(h).
edge(a,b).
edge(b,c).
edge(c,a).
edge(c,e).
edge(c,d).
edge(d,e).
edge(d,h).
edge(e,g).
edge(g,e).
edge(e,f).
edge(f,g).
parent(X,Y):-edge(X,Y).
child(X,Y):-parent(Y,X).
path(X,Y):-edge(X,Y).
path(X,Y):-edge(X,Z),path(Z,Y).
path(X,Y,Z):- 
length_of_path(X,Y,1):-edge(X,Y).
length_of_path(X,Y,N):-edge(X,Z),length_of_path(Z,Y,N1),N is N1+1.
connected(X,Y):-path(X,Y); path(Y,X).
undirected_edge(X,Y):-edge(X,Y);edge(Y,X).
undirected_path(X,Y):-path(X,Y);path(Y,X).
tpath(Node1,Node2):-edge(Node1, SomeNode), edge(SomeNode,Node2).

Путь (X, Y) должен найти направленный путь от узла X к узлу Y. Однако в моем случае есть проблема, потому что существует бесконечная рекурсия (узлы e, f, g являются кругом).

Путь (X, Y, Z) должен найти направленный путь от узла X к узлу Y и сохранить в Z.

length_of_path (X, Y, Z), Z - длинапути от X до Y.

Что затрудняет эти 3 вопроса, так это то, что вам необходимо учитывать наличие кругов на графике.Я не уверен, как решить эту проблему.

1 Ответ

0 голосов
/ 16 февраля 2019

Простой подход - отслеживать путь до сих пор, а не переходить на узел, который вы уже посетили.Вот одна из реализаций: Определение пути / тропы / прогулки

Если я возьму это и добавлю определения вашего узла / 1 и ребра / 2, я получу: 

?- path(edge, Path, e, X).
Path = [e],
X = e ;
Path = [e, g],
X = g ;
Path = [e, f],
X = f ;
Path = [e, f, g],
X = g ;
false.
...