問題タブ [transitive-closure]

必要だと言われたメソッドに関する限り、プログラムに必要なもののスケルトンは既にあります。ただし、それ以外は、このプログラムのコーディングを開始する方法がわかりません。詳細は以下の通りです。 私は自分のプログラムを私のためにやってくれるように頼んでいるわけではありません。テキスト ファイルを取得するためにユーザー入力を読み込む必要があることはわかっています。私の大学ではスキャナーを使用していますが、それがコンストラクター、メイン、または別のメソッドに必要かどうかはわかりません。

1. 単一のコマンド ライン パラメータ、つまり行で区切られた文字列のペアのリストを含むテキスト ファイルを受け入れます。これらの文字列のペアは、依存グラフのエッジを表します。たとえば、A.java B.java という行は、A.java から B.java への依存エッジを表します。上記のグラフを表すファイルは次のようになります。 Main.java A.java A.java B.java

2. ファイルから読み取った各文字列を一意の整数識別子にマップします。このマッピングにより、ファイル名を配列インデックスに簡単に変換できます。

3. (上記の) 一意の整数識別子のそれぞれを元の文字列にマップします。

4. 文字列間の依存関係を表す隣接行列を計算します。

5. 隣接行列に対して推移閉包操作を実行して、文字列間の推移的な依存関係を表す新しい閉包行列を生成します。この操作を実行する簡単な方法は、Floyd-Warshall アルゴリズムです。このトピックについて調査することをお勧めします。

6. 出力は、コース Web サイトのサンプル出力ファイルで示されている形式に従う必要があります。コースの Web サイトには、サンプルの入力ファイルと対応する出力ファイルがあります。この例では、出力は同じ形式である必要があります。目標は、出力情報を魅力的で読みやすい形式にして、以下にリストされている各方法が正しく機能することを明確にすることです。

7. プライベート フィールドを持つメソッドは、クラスの内部状態の可変部分を返すのではなく、getNameIdMap、getIdNameMap、getRoots などの型を返します。そのマップのコピー (クローン)、リストが返されます。このようにして、呼び出し元は、クラスの内部状態に影響を与えることなく、完全に使用可能なオブジェクト (リストやマップなど) を取得します。

プログラムは、次のメソッドも提供する必要があります。

1. public Map getNameIdMap() - 文字列から一意の整数識別子へのマッピングを返します。整数識別子は、指定された文字列の隣接行列と閉包行列へのインデックスを表します。注: Python では、戻り値は、キーが文字列で値が int のペアを持つ辞書である必要があります。

2. public Map getIdNameMap() - 一意の整数識別子から元の文字列へのマッピングを返します。注: Python では、戻り値は、キーが int で値が文字列のペアを持つ辞書である必要があります。

3. public int[][] getDependenceGraph() - ファイル間の依存関係を表す隣接行列を返します。

4. public int[][] getTransitiveDependenceGraph() - 推移閉包操作が適用された後に依存グラフを返します。

5. public List getRoots() - 他のファイルが依存していないファイルに対応する文字列のリストを返します (例: 上記の例の Main)。注: Python では、戻り値も文字列のリストです。

6. public List getLeaves() - 他のファイルに依存しないファイル (上記の例の B など) に対応する文字列のリストを返します。注: Python では、戻り値も文字列のリストです。

7. public void removeLeaf(String leaf) - 隣接および推移閉包行列の両方から葉を削除します。これは、X が Y に依存し、Y が削除されるリーフである場合、X の Y への依存も削除されることを意味します。これにより、X が新しいリーフになる場合とならない場合があります。ファイルが論理的に削除されたことを示すために、マトリックスで特別な番号 (つまり、0 と 1 以外) を使用することを検討してください。

8. public List firewall(String node) - 指定されたファイルの「クラス ファイアウォール」を計算します。ソフトウェア エンジニアリングでは、クラス ファイアウォールの概念により、システムでメンテナンスが実行される場合、変更されたクラスと変更によって影響を受けるクラスのみを再テストする必要があると述べられています。注: Python では、戻り値も文字列のリストです。この方法では、間接的および直接的に影響を受けるクラスを再テストする必要があります。たとえば、クラス A がクラス B に依存し、クラス B がクラス C に依存している場合、クラス C を変更すると、クラス A と B を再テストする必要があります。

9. public void printParallelGroups() - ファイルのコンパイルを並列化したいとすると、他のファイルのコンパイルをトリガーしないファイルを特定する必要があります。これらは依存関係グラフの葉です。このメソッドは、並行してコンパイルできるファイルを識別し、そのファイルのリストを出力して、グラフから削除します。メソッドは、すべてのファイルが「コンパイル」されるまで、このプロセスを繰り返す必要があります。

Prolog で次の問題が発生しています。たとえば、ナレッジ ベースにいくつかの事実があります。

X から Y までのすべての可能なルートのリストを取得することにのみ関心があります。再帰ルールを使用する必要があり、訪問した場所をリストに追加して、飛行経路として繰り返し実行されるサイクルを停止する必要があることを理解しています。知識ベースにはいくつかのサイクルがあります。

私がこれまでに持っているものは次のとおりです。

何らかの理由で、トレースを見ると、not(member(Y,T)) をチェックしようとするとルールが失敗しますが、なぜそうなるのか理解できません。

多くの述語は、基本的に何らかの形式の推移閉包を使用しますが、終了にも対処する必要があることを発見するだけです。これを一度だけ永遠に解決してみませんかclosure0/3:

この定義を推移閉包の実装に使用できない場合はありますか?

なぜ dif/2 なのですか?

@WouterBeek のコメントに詳細に答えるには: dif/2oriso_dif/2は、潜在的な問題を表示または通知できるため、理想的です。ただし、現在の実装では、トップレベルのループが実際の問題を隠していることがよくあります。closure0(\_^_^true,a,b)確かにそれ自体が非常に問題のある目標を考えてみましょう。次のシステムを使用する場合、実際の問題は直接目に見えません。

どちらの最上位ループも、実際に見たいもの、つまりダングリング制約を示していません。SICStus では、置換を生成するために疑似変数が必要です。SWI では、クエリを でラップする必要がありますcall_residue_vars/2。このようにして、制約が付加されているすべての変数が表示されるようになりました。

グラフを入力として受け取り、そのグラフが非循環かどうかを判断する述語 acyclic/1 を定義する必要があります。だから私の理解から

いいえとを返します

はいを返します

グラフ内の 2 つのノードが接続されているかどうかを判断する述語を作成しました。接続されている場合は、yes が返されます。

これを使用して、グラフが非循環かどうかを判断する方法はありますか?

定義済みの述語を使用したくありません。

isConnected/1グラフを引数として取り、ペア間に無向パスがあるかどうかを判断する述語を作成する必要があります。

エッジのリストがあるとします（Gグラフはどこにありますか）：

したがって、3 と 4 の間にエッジがないため、これは失敗するはずです。
この問題にどのようにアプローチしますか？各エッジをトラバースして、エッジをリストに記録する必要がありますか? または、これを行うためのより良いアプローチはありますか?

チェス盤上にあり、キングのように動くロボットがあるとします。

ボードの座標は [1,1] から [8,8] です。

開始位置は [1,1] で、最終位置は [8,8] です。[[1,4]、[2,5]、[5,6]] などの障害物の座標のリストを含むリスト X があります。問題は、ロボットが開始位置から最終位置まで移動できる方法があるかどうかです。

私はこの述語を作りました：

しかし、間違いがあり、値を返しません。再帰が止まらない理由がわかりません。

これで私を助けてくれることを願っています。

Prolog で深さ優先検索アルゴリズムについて学習しようとしていますが、次のコードに出くわしました

何が起こっているのかはある程度理解できますが、それで使用できるいくつかの事実を見つけたり発明したりすることは一生できません.

助けてください。たとえそれが本当に単純な事実のセットであっても、どこかで始める必要があるだけです

前もって感謝します