5

Prolog でサイクルを使用して (実行時に) 有向グラフを作成する必要がありますが、それを表現する方法がわかりません。私の要件は、一定時間内に 1 つの頂点からその隣の頂点に到達する必要があるということです。

それをツリーとして表現することは可能ですか?例えば:

t(left_son,V,right_son)

しかし、どのようにサイクルを解決するのですか?

エッジのリストを作成できます。

graph([a,b,c,d],[e(a,b),e(b,c),e(c,a),e(c,d)])

あるいは単に

[a->[b],b->[c],c->[a,d],d->[]]

しかし、線形時間を消費する隣人を検索しているときに、リストで関数「メンバー」を呼び出さないようにするにはどうすればよいですか?

ご協力いただきありがとうございます

4

3 に答える 3

8

グラフの頂点の数が Prolog で許可されている最大アリティよりも少ない場合 (たとえば、SWI-Prolog のアリティは無制限)、エッジを引数のインデックスとして表すことができます。

になり得るこれ

G = graph(a-[2],b-[3],c-[1,4],d-[2]).

次に、arg (Edge、G、Vert-Edges) を使用して隣人にアクセスします。

もちろん、どの Prolog でも、事実を使用してグラフを記述できます。これは、非常に大きなグラフの場合にも推奨される方法です。

:- dynamic edge/2.

edge(a,b).
edge(b,c).
edge(c,a).
edge(c,d).
edge(d,b).

edit edge/2 リレーショナル表現は、自動インデックス作成の (潜在的に大きな) 利点も得ます。

もっと編集RDFSemantic Webを完全に忘れていました。本当に強力です。私たちはそれに向かっています。

于 2012-04-10T21:41:04.763 に答える
7

@chac が提案する表現に加えて、特に計算中に頂点またはエッジにさらに属性を付加する必要がある場合は、属性付き変数の使用を検討することもできます (Prolog システムがサポートしている場合)。この表現では、頂点ごとに一意の変数を使用し、必要に応じて「名前」などの属性を (put_attr/3 を使用して) 付加し、頂点のリストなどの「エッジ」などの追加の属性を付加します。 、または用語 edge(E,Vertex) のリストです。E は、エッジに影響する情報を追跡する必要がある場合に追加の属性を追加できる変数です。

于 2012-04-11T07:13:04.350 に答える
5

YAPSWISICStusCiaolibrary(ugraphs)などの多くの Prolog システムにあります。(ここに参考文献を自由に追加してください!) そこで、グラフはペアのリストとして表されます。一見すると、これはあまり効率的な表現ではないという印象を受けるかもしれません。結局、1 つの頂点へのアクセスは、リストの長さに比例します。ただし、頂点への直接アクセスが重要になることはめったにありません。ほとんどの場合、グラフは一挙に処理されます。これにより、多くの場合、アクセス コストが償却されます。Vertex-Neighbours

于 2012-04-16T14:34:08.877 に答える