Пролог-граф найти путь без петель, проверяя ребра

Я пытаюсь найти путь в графе в Прологе. Мне удалось заставить это работать с некоторым фрагментом, который я нашел онлайн. Однако он отслеживает узлы, чтобы не посещать их дважды, а мне нужно, чтобы они не посещали один и тот же край дважды. Это, вероятно, сводится к тому же самому в большинстве графиков, но поскольку я хочу использовать его для вычисления путей от точек на ребрах к другим точкам на ребрах, я не хочу, чтобы он возвращал путь от точки к соседнему узлу для противоположный узел (скажем, если бы у нас был ребро AC от узла A к узлу C с точкой B в середине, ACB не был бы приемлемым путем, потому что он прошел AC дважды).

Вот мой текущий код:

path(A,B,Nodes,Edges) :- path1(A,[B],Nodes,Edges).
path1(A,[A|P1],[A|P1],[]).
path1(A,[Y|P1],Nodes,Edges) :- 
   connected(X,Y,Edge), \+ memberchk(X,[Y|P1]), path1(A,[X,Y|P1],N1,E1), append(E1,[Edge],Edges).

connected(a,c,ac). % connected(Node1,Node2,Edge) need not represent an edge:
connected(a,b,ac). % it may also refer to a point on the edge.
connected(b,c,ac).

Для приведенного выше примера это возвращает, например:

path(a,b,[a,b],[ac])
path(a,b,[a,c,b],[ac,ac])

Теперь я думал, что смогу просто заменить \+ memberchk(X,[Y|P1]) с \+ memberchk(Edge,S) чтобы убедиться, что один и тот же край не попадет на путь дважды, что решило бы проблему. Однако, когда я делаю это, Пролог говорит, что пути нет.

Может кто-нибудь объяснить мне, где это идет не так?

1 ответ

Решение

Этот ответ очень помог мне: очевидно, это потому, что вы не можете использовать путь, который еще не был создан, для проверки циклов. Предлагает использовать freeze\2, но я не знаю, как справиться с этим в JIProlog. Я открою новый вопрос для этого.

Другие вопросы по тегам