Пересечение неориентированного графа в прологе

Question

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

Фон:

Попытка смоделировать рельсовую систему со станциями в качестве узлов и их связями в качестве ребер с весом 1.

У меня не было проблем сделать это направленным образом, но я не могу сделать это в неориентированном графе.

Как правило, из сети я узнал, что неориентированный граф объявляется следующим образом:

node(1).
node(2).
node(3).
node(4).
node(5).
node(6).

arc(1,2):-node(1),node(2),1==2.
arc(1,4):-node(1),node(4),1==4.
arc(2,3):-node(2),node(3),2==3.
arc(3,5):-node(3),node(5),3==5.
arc(4,5):-node(4),node(5),4==5.
arc(5,6):-node(5),node(6),5==6.

path(X,Z,A) :-  (arc(X,Y),path(Y,Z,A1),A is A1+1;arc(X,Z), A is 1).

Таким образом, путь запроса (1,2, X). должен вернуть 1, но это не так ... действительно нужна помощь / руководство .. спасибо!

Answer 1

Вот несколько указателей: для моделирования неориентированного графа вам не нужен факт «узел», просто факт «дуга».Что вы хотите подтвердить фактом «дуги», так это то, что между двумя узлами есть дуга.Таким образом, вам нужно всего лишь что-то вроде

arc(1, 2).
arc(1, 4).
...

Теперь, согласно вашему определению Path, кажется, что вы хотите, чтобы запрос выполнялся успешно, если существует путь от X до Y с общим весом A. Если выРабота с ориентированными графами, которые могут быть выражены с помощью предиката, подобного следующему:

path(X, Y, 1):- arc(X, Y).
path(X, Y, A):- arc(X, Z), Z\=Y,
                path(Z, Y, A1),
                A is A1+1.

Обратите внимание, что это может привести к бесконечным циклам, если граф циклический.Чтобы избежать этой проблемы, вы можете отслеживать посещенные узлы, так что вы посещаете почти один раз каждый узел:

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

path(X, Y, _, 1):- arc(X, Y).
path(X, Y, Visited, A):-  arc(X, Z),
                          not(member(Z, Visited)),
                          path(Z, Y, [Z|Visited], A1),
                          A is A1+1.

Теперь этот алгоритм может быть тривиально изменен для работы с неориентированными графами, добавив еще одно предложение.

Answer 2

Спасибо, что указали мне в правильном направлении.Я немного изменил ваш код, чтобы достичь своей цели обхода неориентированных графов:

path(X, Y, A):-  % this method allows user to input a path to be checked
   path(X, Y, [X], A). % this is to ensure a list exists, to determine visited nodes later.

member(X,[X|_]). % X can be head of list.
member(X,[_|Tail]) :-
   member(X,Tail). %X can be tail of list, regardless of what the head is.

path(X, Y, Visited, A):- 
   (  arc(X,Y), A is 1
   ;  not(arc(X,Y)),
      arc(X, Z),
      not(member(Z,Visited)),
      path(Z, Y, [Z|Visited], A1),
      A is A1+1
   ).  
% this method checks if a direct/indirect path exists between X,Y in undirected graph

Я до сих пор не чувствую, что у меня есть хорошее понимание рекурсии.Буду признателен за любые подсказки, чтобы лучше понять его, кроме большей практики cse :)

Спасибо за помощь!

Answer 3

спасибо за указание на ту ошибку (1 == 2), которую я совершил, Каарел, и спасибо за ответ gusbro.

Гусбро, я хотел бы уточнить, действительно ли создается ненаправленный граф.

это то, что я написал для создания неориентированного графа.

дуги (1,2).

дуга (2,1).

дуги (1,4).

дуги (4,1).

дуги (2,3).

дуги (3,2).

дуги (3,5).

дуги (5,3).

* * 1 022 дуги (5,6).

дуга (6,5).

Таким образом, путь (1,4) должен показывать 1; 4; нет. Где 1 - прямой путь между узлами 1,4 и 4 - путь от узлов 1-2-3-5-4.

Но этого не происходит. Вместо этого я получаю

A = 1;

A = 3;

A = 5;

A = 7;

A = 9;

A = 11

Не уверен, почему, хотя?