問題タブ [transitive-closure]

私は航空会社とそのフライトのプロローグにこのナレッジベースを持っています:

再帰規則:

そして、これで私は質問をすることができます: ロンドンとバルセロナの間の接続は可能ですか?

質問：connection(london,barcelona).

そして、答えは肯定的になります。しかし、詳細を教えてくれるルールや質問はありますか?

例: ロンドンとバルセロナ間の接続は直接ですか、それとも間接ですか?

その他の質問: 直行便の場合、中間の都市はどこですか? (上記の例では、たとえば "paris" になります。

誰でも私がそれを理解するのを助けることができますか?

私はPrologを初めて使用し、グラフを調べていました。ノードを指定し、そのノードから到達可能なすべての単純なパスをリストするように求めるオンラインの問題を見つけました。ゴールノードはありません。すべての可能性を試して、それらすべてのパスを返すだけです。

X から Y への有向辺を象徴するパス (X, Y) としてグラフを表しました。

周期的なこの単純な知識ベースを構築しました。

all_paths(a, P) をクエリすると、P は次のようになります (すべてのオプションがなくなるまで ; がスパムされたと仮定します)。

私はスターターとしてそのようなものを書きました：

わかりました、少し変更しました。今、私は戻ってきました：

誰かがすべてのパスを正しく取得する方法を理解するのを手伝ってくれますか?

だから私が得るのは、マトリックス内の座標を含むリストです。例えば：

これらすべてのノードが相互に接続されているかどうかを確認する必要があります。つまり、任意のノードを選択すると、他のノードに到達できます。最初の 4 つのノードのいずれかから最後の 4 つのノードのいずれかに到達する方法List 1がないため、これは には当てはまりますが、には当てはまりません。List 2ではList 1、ノード[2, 2]はブリッジとして機能するため、true です。

特定のセルの隣人を返す述語を書くことができましたが、続行する方法がわかりません。

編集：これが私が今持っているものです：

編集 2: 1 つのセルのみを左/上/右/下に移動できます。マトリックスの各セルには、X 座標と Y 座標があります。リスト 1 では、常に 1 つの隣接ノードがあるため、任意のノードから任意のノードに到達できます。したがって、リーチとは、ノード A からノード B に移動することを意味し、X または Y を 1 だけインクリメントします。

私はPrologが初めてで、それを学ぼうとしています。のようなものを達成したいしa>b、b>cそれa>cは推移的な関係です。

私は次のルールのセットを持っています。

象はウイルスよりも大きいことを私たちは知っています。私が達成したいのは、使用smaller(ant,elephant)すると返されることtrueです。smaller(X,Y)使ってみたルールは

問題に対処します。コードの再帰ルールが実行する再帰の回数を計算したいと考えています。

私のプログラムは、オブジェクトがコンピューターハードウェアのコンポーネントであるかどうかを調べます（コンポーネント（X、Y）述語を介して）。たとえば、コンポーネント（コンピューター、マザーボード）-> true。

オブジェクトが直接のコンポーネントではなく、別のコンポーネントのサブコンポーネントである場合も調べます。例 subcomponent(computer,ram) -> true. (RAM はマザーボードのコンポーネントであり、マザーボードはコンピュータのコンポーネントであるため)

私のコードは 400 行を超えているので、component(X,Y) という形式の述語と、subcomponent(X,Y) という規則の述語だけを紹介します。

したがって、いくつかの述語を以下に示します。

等々....

私のルールは次のとおりです。

さて、特定のコンポーネント X から特定のコンポーネント Y に含まれるコンポーネントの数、つまり再帰ルール subcomponents(X,Y) の再帰の数を計算するために、失敗したいくつかの試みを行いました。ただし、以下に示します。

私）

この場合、「エラー: is/2: 引数が十分にインスタンス化されていません」というエラーが表示されます。

ii)

この場合、結果として 1 または 11 のいずれかが得られ、この数値の後に true が返され、それだけです。まったく論理的ではありません！

iii)

この場合、私の知識ベースによると正しくない結果の数値が得られます (または、この方法にはいくつかの論理があるように見えるため、それらを誤訳します)。

それで、私は何を間違っているのですか？代わりに何を書くべきですか？

あなたの答えを読むのを楽しみにしています！

述語parent/2を介して親子関係を表す一連の事実が与えられた場合、以下に示すように述語pred1/2およびpred2/2を使用して関係「祖先」(先祖) を定義するときの違いは何ですか?

関係のこれらの関数依存関係の閉鎖は何ですか?

1. A -> DC
2. D -> B

回答: A -> BC (疑似推移性ルールを使用)。

私は正しいですか、それとも何か不足していますか?

単純なグラフの問題に取り組むために Spark を使用しようとしました。Spark のソース フォルダーにサンプル プログラムがありました。しかし、私のラップトップでは、10 分以上実行され、終了しません。私が使用するコマンド ラインは、spark-submit transitionive_closure.py です。

このような小さな推移閉包の結果を計算する場合でも、なぜ spark が非常に遅いのだろうか? よくあるケースですか？私が見逃している設定はありますか？

プログラムを以下に示します。このプログラムは、Web サイトの spark インストール フォルダーにあります。

迷路構造に対して経路探索クエリを実行する単純な Prolog プログラムの実装に興味があります。

バグ: 私の Prolog インタープリター (SWI) は、パスが >= 5 ステップ離れた入力ノードで使用されると、無限再帰の状態にスローされます。ただし、パス内のノード ステップが 5 つ未満の場合、ルールは正常に機能します。不思議なことに、対称性の規則を省略すると (単純に前後の隣接関係を宣言するだけです)、パスの呼び出し制限が 3 ノード差未満に減少します。デフォルトのスタック割り当てを再度オーバーライドすると、スタック オーバーフローの前にパスのスパンが増加します。

明らかに、アキュムレータが適切です。インタープリターがパス内で既に通過したノードに再アクセスし続けるため、実行時にプログラムがクラッシュするのではないかと思います。

アキュムレータとして機能pathする の追加要件を含めるように変更しました。legal

ただし、現在、varZが「シングルトン」であるという問題に直面しています。

過剰なスタック呼び出しを避けるためにアキュムレータを適切に実装する方法について何か提案はありますか?