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

コードに制限はありませんが、既にコーディングした他のすべての構造に適合するため、この表現に固執します。

つまり、頂点がいくつかのオブジェクトであり、エッジがそれらの間の無向関係を表す無向グラフです。この特定の例でより多くの背景を説明するために、私は長方形を表現しようとしているので、オブジェクトはその 4 つのエッジ (セグメント) です。これらのセグメントは、頂点などを使用して同様に表されます。ポイントは、同じレベルのオブジェクト間の制約を表すグラフの階層を構築することです。

問題はエッジの表現にあります。円弧 (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) のビルドにすることができます。答えを知りたいのですが、長方形が 1 つあります。ただし、この1つの長方形の組み合わせがいくつ得られるかを計算できます。また、計算に時間がかかりすぎます。明らかに、長方形レベルで終了したくありません。

要素をソートすることを考えました。セグメント内の頂点を並べ替えることができます。しかし、セグメントを長方形に並べ替えたい場合、制約は無効になります。グラフは有向になります。たとえば、最初の 2 つの関係を考慮して、アーク (a,b) と (a,c) があるとします。アークがソートされていない場合、プログラムは希望どおりに答えます: arc(b,a,connected),arc(a,c,connected) with match: Object1=b,Object2=a,Object4=c. 要素を並べ替えると、arc(b,a,connected) と arc(a,b,connected) を試すことができないため、有効ではなくなります。2つ目だけ。私はソートに固執しますが、この最後の問題を解決する方法がわかりません。

うまくいけば、私はこれらすべてを非常に明確に述べました。私は、私がすでに持っている表現やアイデアにできるだけ近づけたいと思っています. しかし、まったく新しいものも大歓迎です。私は正確な答えを期待していません.むしろ、私を正しい方向に向けたり、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)

円弧が存在しない場合、これは無限ループになるためです。ただし、最初の引数が 2 番目の引数より大きいかどうかのみを確認できます。

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

このアプローチでは、弧が 2 つの方法で表現されているために発生する可能性のある複数の解は解決されません。簡単な修正は、次を使用して 1 つのソリューションのみが期待される場合に、1 つのソリューションのみをチェックすることですonce/1。

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

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

もちろん、複数のソリューションが存在する可能性がある場合、これを行うことはできません。

もう 1 つのアプローチは、さらなる抽象化を強制することです。現時点では、2 つの点 ( 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.

円弧の順序が間違っていた場合、四角形の順序を変更しなかったことに注意してください。私たちは単に失敗しました。このようにして、ソリューションの重複を回避しましたが (それらを注文して有効な四角形として受け入れた場合、同じ四角形が 4 回表示されます)、四角形を見つけるのにかかる時間が長くなります。四角形全体を作成するのではなく、順序が正しくない最初の円弧で検索を停止することで、オーバーヘッドを削減しました。また、アークが順序付けされている場合は、オーバーヘッドも削減されます (最初の一致が順序付けられるため)。一方、この方法ですべての四角形を検索する複雑さを考慮すると、オーバーヘッドはそれほど重要ではありません。また、最初の長方形だけが必要な場合にのみ適用されます。より多くのソリューションを取得したい場合、または他のソリューションがないことを確認したい場合、prolog はツリー全体を検索します。

于 2012-07-22T12:21:30.557 に答える