問題タブ [transitive-closure]

次のような事実が与えられた場合:

• ジェイクはニックより賢い
• ニックはウェスより賢い
• ウェスはディックより賢い

Jake の方が Dik よりも賢いかどうかを判断する再帰的なプログラムを作成してください。

私が持っている解決策は次のとおりです。

出力：

しかし、私がそれを交換すると:

出力に「ERROR: Out of local stack」と表示されます。出力に「False」と表示する必要があります。どうすれば修正できますか？

ありがとう

Protégé での推移的な役割の推論について問題があります。

次のような単純なオントロジーを作成しました。

「どのロッドもエンジンの一部です。」

「どんなエンジンも車の一部です。」

「PartOf リレーションは推移的です。」

Protégé がこの DL を DL メトリクスの S として認識し、「ロッドは車の一部である」と推論することを期待していましたが、推移性の公理を無視しているようです。問題はその理由です。

(私は Protégé の異なるバージョン (4.3 と 5.0) と異なる推論を使用しました。いくつかの重要なチェックボックス オプションを設定しなかったと思われます。)

オントロジーを添付します。

boostのtransitive_reductionを使おうとしているのですが、使い方がわかりません。

で定義されたグラフがあります：

メソッドを呼び出したい：

「g_to_tr_map_stor」と「g_to_tc_map_stor」に使用するタイプがわかりません。

私が読んだ情報によると、それは頂点から整数へのマップでなければなりません。さまざまな種類のマップを試しましたが、成功しませんでした。

いくつかのアイデア？

どうも

実装しようとすると問題が発生します

私が尋ねる?- friends(mia, X).と、ローカルスタックが不足します。

それから私は追加します

私は尋ねます ?- friends(mia, X).、それは答え続けX = miaます。

理解できません、なぜ再帰的なのですか？

私が書いたこのコードが機能しない理由がわかりません。

例えば：

多くの述語は、二項関係を介して定義されたエッジから構築されたある種の非循環パスを定義します。これは、推移閉包を定義するのと非常によく似ています。したがって、一般的な定義が求められます。

グラフ理論で定義された概念は、一般に期待されているものとすぐには一致しないことに注意してください。最も注目すべきは、エッジの名前には関心がないことです。

さらに悪いことに、グラフ理論も少し変更され、 walk の概念が導入されました。

伝統的に、現在一般にオープンウォークとして知られているものと呼ばれる道。今日では、条件なしで述べた場合、通常、パスは単純であると理解されています。つまり、頂点が繰り返されない (つまり、エッジが繰り返されない) ことを意味します。(チェインという用語は、すべての頂点とエッジが異なるウォークを指すためにも使用されています。)

だから私の質問は: この機能に名前を付けて定義する方法は?

私がこれまでに行ったことは、次のように定義することです。

最初の引数は、さらに 2 つの引数がない不完全な目標である関係の継続でなければなりません。次にPath、頂点または頂点のペアのいずれかが続きます。

使用例

実装

DAGの隣接リストMap<Vertex, Set<Vertex>>が与えられた場合、すべての頂点の到達可能性を計算したいと考えています (つまり、u から v へのパスがある場合)。

static Map<Vertex, Set<Vertex>> reachability(Map<Vertex, Set<Vertex>> adjList) {}

Floyd-Warshall を使用して可能であることを知っていますO(V^3)

しかし、私はスパース グラフ (および隣接リスト) を持っているので、これを行うための最速の方法は何ですか?