Два разных пути от X до Y в графе

Question

Я застрял со следующим вопросом Пролога: заданы ребра графа без циклов как факты. например:

edge(a, b).
edge(b, c).
edge(c, d).
edge(c, e).
...

Я должен написать предикат, который проверяет, есть ли два разных пути между вершинами X и Y. Например, вызов two_paths(a, c). должен возвращать true, если есть два разных пути от узла a к узлу c. Я знаю, как проверить, существует ли путь между двумя вершинами:

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

Но как мне это сделать, чтобы проверить два разных пути? Большое спасибо за Вашу помощь.

Answer 1

Идея может заключаться в создании предиката path/3 который возвращает построенный путь, а затем запрашивает два разных пути. Что-то вроде:

path(X,Y,[X,Y]) :- edge(X,Y).
path(X,Y,[X|T]) :- edge(X,Z), path(Z,Y,T).

Сейчас path(a,c,T) покажет вам путь:

?- path(a,c,L).
L = [a, b, c] ;
false.

Теперь вы можете построить предикат:

two_paths(X,Y) :-
    path(X,Y,La),
    path(X,Y,Lb),
    dif(La,Lb).

Другими словами, вы просите Пролога построить для вас путь LaПостроим для вас дорогу Lb а затем проверьте, не равны ли они (dif(La,Lb)). Первый построен Lb будет эквивалентно La, но благодаря механизму обратного отслеживания Prologs он попытается создать вам другой путь, для которого условие может быть выполнено успешно. Это довольно чистая реализация Пролога (без среза (!), once/1, так далее.). Существуют более эффективные подходы, так как здесь вы будете "переделывать" работу во втором вызове.

Более эффективным подходом может быть построение предиката path_avoid/3 (или же path_avoid/4) где вы вводите первый построенный путь к предикату и таким образом заставляете вашу программу хотя бы в какой-то момент выполнить шаг, отличный от представленного. Я оставляю это открытым как потенциальное упражнение.