在序言中遍历无向图 [英] Traverse undirected graph in prolog

问题描述

简而言之：我试图在序言中遍历一个无向图，但不知道如何做，任何建议都将不胜感激。

背景：

试图建立铁路系统模型，将站点作为节点，并将它们的链接作为重量为1的边。

没有问题以有针对性的方式进行，但无法在无向图中进行。

从网上一般来说，我已经知道无向图是用以下方式声明的：

 节点（1）。 
节点（2）。 
节点（3）。 
节点（4）。 
节点（5）。 
节点（6）。 
 
 arc（1,2）： - 节点（1），节点（2），1 == 2。 
 arc（1,4）： - 节点（1），节点（4），1 == 4。 
 arc（2,3）： - 节点（2），节点（3），2 == 3。 
 arc（3,5）： - 节点（3），节点（5），3 == 5。 
 arc（4,5）： - 节点（4），节点（5），4 == 5。 
 arc（5,6）： - 节点（5），节点（6），5 == 6。 （X，Z，A）： - （弧（X，Y），路径（Y，Z，A1），A是A1 + 1;弧（X，Z），A是1）。 
  

因此，查询路径（1,2，X）。应该返回1，但它不这样做...真正需要帮助/指导..谢谢！

解决方案

指针：
为了建模一个无向图，你不需要事实'节点'，只是事实'弧'。
您想要通过弧这一事实来确认什么，以及两个节点之间是否存在弧线。所以你只需要像

  arc（1,2）。 
 arc（1，4）。 
 ... 
  

现在，根据您对Path的定义，似乎您想要如果存在一个从X到Y的路径，总重量为A，则查询成功。
如果您正在处理可以使用谓词表示的有向图：

 路径（X，Y，1）： -  arc（X，Y）。 
 path（X，Y，A）： -  arc（X，Z），Z\ = Y，
 path（Z，Y，A1），
 A是A1 + 1。 
  

请注意，如果图形是循环的，则可能会导致无限循环。
为避免此问题，您可能需要跟踪访问的节点，以便每次访问几乎每个节点：

 路径（X，Y，A）： - 路径（X，Y，[X]，A）。 
 
 path（X，Y，_，1）： -  arc（X，Y）。 
 path（X，Y，Visited，A）： -  arc（X，Z），
 not（成员（Z，访问）），
 path（Z，Y，[Z |访问]，A1），
 A是A1 + 1。 
  

现在可以对此算法进行细微修改，以处理无向图，只增加一个子句。 p>

In short: I am trying to traverse an undirected graph in prolog, but don't know how to, any advise would be greatly appreciated.

Background:

Trying to model rail system, with stations as nodes and their links as edges with weight 1.

I had no problem doing it in a directed manner, but cant do it in an undirected graph.

From the net generally, i've learned that undirected graph is declared in the following way:

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).

thus, the query path(1,2,X). should return 1, but it is not doing so...truly need help/guidance..thanks!

解决方案

Here goes some pointers: To model an undirected graph you dont need the fact 'node', just the fact 'arc'. What do you want to acknowledge with the fact 'arc', well that there is an arc between the two nodes. So you would only need something like

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

Now, according to your definition of Path, it seems you want the query to succeed if there is a path from X to Y with total weight A. If you were dealing with directed graphs that could be expressed with a predicate like this:

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

Note however, that this may lead to infinite loops if the graph is cyclic. To avoid this problem, you may want to track the visited nodes, so that you visit almost once each node:

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.

Now this algorithm can be trivially modified to deal with undirected graphs, adding just one more clause.

这篇关于在序言中遍历无向图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！