Блог

У меня есть простая проблема, с которой у меня возникли проблемы, хотя я думаю, что ответ довольно прост. Вот оно начинается:

Предположим, что взвешенный ориентированный граф описывается с помощью предиката edge/3, такого, что ребро (X, Y, C) является истинным, если существует ребро от вершины X до вершины Y стоимостью C. Например, справа находится граф и его описание с использованием edge /3:

 edge(a, c,1).
edge(a,d,3).
edge(b,d,2).
edge(c,e,5).
edge(e, c,2).
edge(e,f,2).
edge(d,f,10).
 

Я должен это сделать . Определите предикат reachable/2, который вычисляет список узлов, к которым можно получить
доступ из данного узла. Например, на запрос достижимый (a, L) Prolog должен ответить L=[c, e,d,f]
(в любом порядке). (Помните findall .)

Вот что я написал на данный момент

 path(X,Y):-edge(X,Y,_).
path(X,Y):-edge(X,Z,_),path(Z,Y).

reachable(X,L):-findall(Y,path(X,Y),L).

 

Я не вижу, что не так, но он ходит кругами и останавливается из-за проблем с памятью.
Есть идеи, как это решить?

Пожалуйста, это помогло бы творчески!

Если у вашего графика есть ребро, например c → e → c → e → … , тогда ничто не останавливается path при каждом переходе от e туда c и обратно. Если мы не добавим что-то, чтобы предотвратить это.

Мы можем использовать список, содержащий все уже посещенные элементы, и запретить их посещение в другой раз:

 path(X, Y) :-
    path(X, Y, [X]).

path(X, Y, V) :-
    edge(X, Y, _),
      member(Y, V).
path(X, Y, V) :-
    edge(X,Z,_),
      member(Z, V),
    path(Z, Y, [Z|V]). 

таким образом, мы начинаем со списка, который содержит только X . Каждый раз, когда мы берем ребро, мы проверяем, не является ли цель ( Y или Z ) членом V , и в случае рекурсии мы добавляем Z в список.

Для данного графа:

таким образом, это приводит к:

 ?- path(X, Y).
X = a,
Y = c ;
X = a,
Y = d ;
X = b,
Y = d ;
X = c,
Y = e ;
X = e,
Y = c ;
X = e,
Y = f ;
X = d,
Y = f ;
X = a,
Y = e ;
X = a,
Y = f ;
X = a,
Y = f ;
X = b,
Y = f ;
X = c,
Y = f ;
false.