Список всех достижимых узлов

Question

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

has(a, b). 
has(b, c). 
has(d, b). 

Теперь я хотел бы перечислить все узлы, которые могут быть достигнуты (с определенного узла) с заданным количеством шагов.

connected_nodes(a, T, 2). 

должен поэтому выход

T = c 
T = d 

Мой текущий код выглядит следующим образом:

connected_nodes(A, B, 0) :- write(A). 
connected_nodes(A, B, N) :- 
    N > 0, M is N - 1, 
    has(A, X), 
    connected_nodes(X, B, M). 

Это работает для Т = с, но не при Т = д, так как это би- направленное отношение.

Я правильно думаю о рекурсии или о том, как решить эту проблему другим способом?

Answer 1

Ваш connected предикат кажется хорошо. Возможно, имело смысл сделать основной случай положительным на has, но это зависит от вас.

Однако сказать Ваш предикат has является «двунаправленным», но вы явно не создали правило, которое указывает это.

Следующий код является «двунаправленным» версия кода:

has(a, b). 
has(b, c). 
has(d, b). 

bi_has(X,Y) :- has(X,Y). 
bi_has(X,Y) :- has(Y,X). 

connected_nodes(A, B, 0) :- write(A). 
connected_nodes(A, B, N) :- 
    N > 0, M is N - 1, 
    bi_has(A, X), 
    connected_nodes(X, B, M). 

Однако обратите внимание, что ваш запрос теперь возвращает a как возможный ответ тоже. Это происходит потому, что, поскольку вы никогда явно не заявляли, что не хотите возвращаться к тому же элементу после двух шагов.

Если вы не хотите этого поведения, вам также необходимо сохранить список элементов, которые были посещены до сих пор (например, аккумулятор), и подтвердить, что вы не пересматриваете элементы.