問題タブ [transitive-closure]

可換性と推移性のプロパティを使用して、Prolog で同等性をシミュレートしたいと思います。これが私が行ったことです。equal/2 は事実として提供されます。

しかし、transitiveEqual/2 を計算しようとすると、上記のソリューションでパフォーマンスの問題が発生します (約 20 分かかりました)。equal/2 から約 2K の対称 Equal/2 ファクトがかなり高速に計算されるため、ルールの原因である必要があります。推移的Equal / 2の場合、誰でもこれに関する改善を提案できますか?

どうもありがとう。

組織階層の推移閉包を表すテーブルがあります（つまり、単一のルートを持つツリー）。

各ユーザーがアクセスを許可されている組織を含む別のテーブルがあります。

システムは、ユーザーがアクセスできる各組織に関連付けられた支出のロールアップをユーザーに表示します。私はいつでも、ユーザーに会社のビュー（つまり、ルート）を表示して、ユーザーに直接の子組織のリストと、彼の組織が合計にどれだけ貢献しているかを表示することから始めることができます。ほとんどの場合、子は1人であり、ユーザーは複数の子を表示する前に複数のレベルをドリルダウンする必要があります。私は、複数の子供を示す最初の組織（つまり、LCA）からプレゼンテーションを開始したいと思います。

特定のユーザーの場合、ルートへのパスのセットを簡単に見つけることができますが、最も一般的でない祖先を見つけるのに問題があります。私はpostgresql9.1を使用していますが、データベースに依存しないソリューションを好みます。最悪の場合、ルートへのパスをアプリケーションのコードに戻し、そこでLCAを計算できます。

私はこの結果を得るためにこのプログラムを書きます: "X=john" "Y=jane"

しかし、このプログラムを実行すると、次の結果が得られます。プログラムがループに入ると思います。正解したらやめたい！

私はエラーがあります！この問題をどのように解決しますか？

デバッグによって:

などなど.. なぜ好き(ジェーン、_G2267) ??????

LR(1) クロージャーをすばやく計算するために、Warshall のアルゴリズムを実装しようとしています。

LR（0）でどのように機能するかを理解していると思います：

• グラフのノードは、次のようなLR アイテムです。A → B • C
• エッジは、から始まる「トランジション」ですA → B • C。C → • D

問題は、LR(1) には先読みの計算が必要であり、それらをアルゴリズムに組み込む方法がわかりません。与えられた LR アイテムの推移閉包を知っ
ていたとしても、各アイテムの先読みセットが何であるかを理解するためだけに、同じ計算をすべて行う必要があるように思えます。

ウォーシャルのアルゴリズムを使用して正規の LR(1) クロージャーを計算することは可能ですか?それとも、より制限されたケース (LR(0)、SLR(1) など) でのみ可能ですか?

MySQL ストアド プロシージャにウォーシャルのアルゴリズムを実装しました。残念ながら、手続きが完了するまでに時間がかかります。私はストアド プロシージャの作成の初心者です。高速化するために何ができるか知っていますか?

簡単な説明: 隣接リストの推移閉包を計算しようとしています。どのノードが接続されているかを知りたい (1 つのエッジで直接、または複数のエッジで間接的に)。例えば：

次の図は、グラフを示しています。

_{ウィキメディア・コモンズからの画像: https://en.wikipedia.org/wiki/File:Transitive-closure.svg}

SQL Fiddleまたはここでコードを表示できます。

1466 レコードのテーブルで手順を実行すると、私のコンピューターでは 45 秒かかります。

まず文脈。次の双方向グラフがあります。

Prolog では次のように表されます。

したがって、ノード間の関係と、ノード間の接続が、前に述べたように、両方向に関係しています。

私が探しているのは、2 つのノード間のグラフにパスがあるかどうかを判断path(X,Y)できるプロローグ定義です(両方のノード間に少なくとも 1 つのパスが存在する場合は true、両方のノード間に既存のパスがない場合は false を返します)。

したがって、このモデルの目標出力は次のようになります。

これには訪問済みリストの使用が含まれることを知っています。これの例を見たことがありますが、2つのノード間のすべての可能なパスを示しています。しかし、これは私が探しているものではありません。私が探しているのは、2 つのノード間にパスがあるかどうかを検出する定義であり、2 つのノード間に可能なすべてのパスを提供するわけではありません。

編集: @mbratch のおかげで、提案された問題を解決策に適応させることができるようになりました。

私は次のプログラムを与えられています：

次のクエリにプルーフ ツリー アルゴリズムを適用する場合は、次のように尋ねました。

証明木は無限の成功木ですか、それとも無限の失敗木ですか?

私が見ているように、ツリーの構築中に、パスのルール 1 を何度も適用し、無限のツリーを作成し、パスのルール 2 に到達することはありません..

したがって、無限の障害ツリーが作成されます。しかし、私が持っている解決策は、それが無限の成功の木であると言います。私の質問は、私は正しいですか、それとも私の教授は正しいですか? :]

Haskell を使用してリストに推移閉包を生成する必要があります。

これまでのところ、私はこれを得ました：

出力 1:

出力 2:

問題は2番目の出力にあります。新しく生成されたリストで追加の推移閉包をチェックする代わりに、単に結果を返します。

Haskell コードのプロトタイプを作成するために、次のPython コードを使用しました。

出力：

これは、Haskell 関数で必要な正しい出力です。

Haskell コードで同じことを行うには? if( Python コードから Haskell コードへのステートメントを再作成する必要があります)

ノードとアークの存在に関する制約を解決することにより、有向グラフの形状を決定しようとしています。たとえば、バイナリ変数V1V2は、ノードから へ1のアークがある場合です。たとえば、グラフが接続されていること、または特定のノードから別の特定のノードへのパスがあることを要求するために、到達可能性制約を表現したいと思います (または、代わりに推移閉包を見つけます)。V1V2

SICStus Prolog がfd_closureこの目的のために持っていることを見てきましたが、SWI Prolog には似たようなものは見つかりませんでした。CHRを使用する必要がありますか? アーク/パスの一貫性の例を見てきましたが、正しい方向を見ているかどうかはわかりません。