1

我需要像这样表示图表：

Graph = graph([Object1,Object2,Object3,Object4],
              [arc(Object1,Object2,connected),
               arc(Object2,Object4,connected),
               arc(Object3,Object4,connected),
               arc(Object1,Object3,connected),
               arc(Object2,Object3,parallel),
               arc(Object1,Object4,parallel),
               arc(Object2,Object3,similar_size),
               arc(Object1,Object4,similar_size)])

我对代码没有限制，但是我会坚持这种表示，因为它适合我已经编码的所有其他结构。

我的意思是无向图，其中顶点是一些对象，而边表示它们之间的无向关系。为了在这个特定示例中为您提供更多背景知识，我试图表示一个矩形，因此对象是它的四个边（段）。这些线段的表示方式与使用顶点等相同。关键是构建图形的层次结构，该层次结构将表示同一级别上的对象之间的约束。

问题在于边缘的表示。表示弧 (a,b) 的最明显方法是将 (a,b) 和 (b,a) 同时放入程序中。然而，这使我的程序以指数级的冗余数据淹没了我的程序。例如，如果我有顶点 a、b、c、d。我可以构建段 (a,b),(a,c),(a,d),(b,c),(b,d),(c,d)。但我也得到（b，a），（c，a）等等。在这一点上它不是问题。但后来我建立了一个矩形。它可以由段 (a,b),(b,c),(c,d),(a,d) 构建。我想得到答案——有一个矩形。但是，您可以计算我得到了这个矩形的多少组合。计算也需要太多时间，显然我不想在矩形级别完成。

我考虑过对元素进行排序。我可以对段中的顶点进行排序。但是，如果我想对矩形中的段进行排序，则约束不再有效。图变为有向图。例如，考虑到前两个关系，假设我们有弧 (a,b) 和 (a,c)。如果弧没有按我的意愿排序，程序会回答：arc(b,a,connected),arc(a,c,connected) 匹配：Object1=b,Object2=a,Object4=c。如果我对元素进行排序，它将不再有效，因为我无法尝试 arc(b,a,connected) 和 arc(a,b,connected)。只有第二个。我会坚持排序，但我不知道如何解决最后一个问题。

希望我把这一切都说得很清楚。我更愿意尽可能接近我已有的代表和想法。但也非常欢迎全新的。我不期望有任何确切的答案，而是将我指向正确的方向或建议一些特定的阅读内容，因为我对 Prolog 还是很陌生，也许这个问题并不像我想的那么罕见。

从昨天开始，我一直在尝试解决这个问题，但找不到任何简单的答案。我查看了一些离散数学和常见的无向图表示，例如邻接表。如果有任何不清楚的地方，请告诉我——我会尽力提供更多细节。

4

1 回答 1

1

有趣的问题虽然有点宽泛，因为它没有说明你真正想用弧线、矩形等做什么；只有在某些用途下，表示可能是有效的（时间/空间/优雅）。无论如何，这里有一些想法：

排序
明显的问题是您提到的问题；如果排序对存在，您可以通过引入一个成功的子句来解决它：

arc(X,Y):-
    arc_data(X,Y)
  ; arc_data(Y,X).

请注意，您不应执行以下操作：

arc(a,b).
arc(b,c).
arc(X,Y):-
   arc(Y,X)

因为如果弧不存在，这将导致无限循环。但是，您只能检查第一个 arg 是否大于第二个：

arc(a,b).
arc(b,c).
arc(X,Y):-
   compare(>,X,Y),
   arc(Y,X)

这种方法无法解决由于以两种方式表示弧而可能出现的多种解决方案。简单的解决方法是只检查一种解决方案，其中预计只有一种解决方案使用once/1：

3 ?- arc(X,Y).
X = a,
Y = b ;
X = b,
Y = a.

4 ?- once(arc(X,Y)).
X = a,
Y = b.

当然，当可能有多种解决方案时，您不能这样做。

另一种方法是强制进一步抽象：目前，当您有两个点 ( a, ) 时，您可以在检查这些点是否连接后b创建弧 (arc(a,b)或)。arc(b,a)取而代之的是，您应该通过谓词创建弧（也可以检查点是否连接）。好处是您不再直接参与弧的表示，因此可以强制排序（是的，它基本上是面向对象的）：

cv_arc(X,Y,Arc):-
      ( arc(X,Y),
        Arc = arc(X,Y))
    ; ( arc(Y,X),
        Arc = arc(Y,X)).

（假设为数据库arc(a,b)）：

    6 ?- cv_arc(a,b,A).
    A = arc(a, b).

    7 ?- cv_arc(b,a,A).
    A = arc(a, b).

    8 ?- cv_arc(b,c,A).
    false.

当然，您需要对其余对象遵循类似的原则；我假设你正在做这样的事情来找到一个矩形：

rectangle(A,B,C,D):-
    arc(A,B),
    arc(B,C),
    arc(C,D),
    arc(D,A).

除了由于弧（已解决）导致的重复之外，这会将 ABCD、DABC 等识别为不同的矩形：

28 ?- rectangle(A,B,C,D).
A = a,
B = b,
C = c,
D = d ;
A = b,
B = c,
C = d,
D = a ;
A = c,
B = d,
C = a,
D = b ;
A = d,
B = a,
C = b,
D = c.

我们将再次这样做：

rectangle(rectangle(A,B,C,D)):-
    cv_arc(A,B,AB),
    cv_arc(B,C,BC),
    compare(<,AB,BC),
    cv_arc(C,D,CD),
    compare(<,BC,CD),
    cv_arc(D,A,DA),
    compare(<,CD,DA).

并运行arc(a,b). arc(b,c). arc(c,d). arc(a,d).：

27 ?- rectangle(R).
R = rectangle(a, b, c, d) ;
false.

请注意，如果弧的顺序错误，我们不会重新排序矩形；我们只是失败了。通过这种方式，我们避免了重复的解决方案（如果我们对它们进行排序并将其作为有效矩形接受，我们将有四次相同的矩形），但查找矩形所花费的时间会增加。我们通过在第一个无序的弧处停止搜索而不是创建整个矩形来减少开销。此外，如果对弧进行排序（因为将排序第一个匹配项），开销也会减少。另一方面，如果我们考虑以这种方式搜索所有矩形的复杂性，那么开销并没有那么大。此外，它仅适用于我们只想要第一个矩形的情况；如果我们想要获得更多的解决方案或确保没有其他解决方案，prolog 将搜索整个树，

于 2012-07-22T12:21:30.557 回答