問題タブ [iterative-deepening]

path(A,B,Path)A から B へのボード上のすべての有効なパスを生成する Prolog 関数があります。

この関数の出力は次のようになります。

などなど

有効なパスを含むリストの無限のセットを生成します。これらのパスの最短を取得したいだけです（ただし、いくつもあります）。つまりshortest(A,B,Path)、ボード上の A から B への最短の有効なパスを生成する関数が必要です。

私が望む出力は次のとおりです。

Prologの関数をいじって、setofすべてのパスをセットにバインドし、そのセットに長さの制限を課しましたが、まだ機能していません。

これまでの私の下手な作業は次のようになります。setofそれは間違いなく間違っています。どのように機能し、このセットから最短のリストを見つける方法を理解していただければ幸いです。ありがとう！

状態空間グラフの深さ優先反復深化検索を実装しようとしています。3 つの頂点を持つグラフがあり、それらは 2 つの活性化エッジと 2 つの抑制エッジです。各ノードにはバイナリ値があり、集合的にこれがグラフの状態です。グラフは、ノードの 1 つがしきい値を超えているか、しきい値を下回っているか (すべての受信ノードの合計から計算) を確認することで、新しい状態に遷移できます。各遷移で最大 1 つのノードが変更されます。それらは 3 つのノードであるため、状態遷移グラフ内の各状態を離れる 3 つの状態遷移エッジがあります。

たとえば、次のクエリを実行できます。

そして、それは私に3つの正しい答えを与えます:

Bratkos Prolog for AI book で与えられた述語 id_path を使用しようとしていますが、質問 11.3 の解決策ですが、使用/適応に問題があります。 ループに入らずに、開始ノードから他のノードへのパスを作成したい - 繰り返し要素を持たせたり、パスが存在しないときに立ち往生したりしたくない. 開始状態と、開始状態からアクセスできる一連の状態を示すパスが必要です。自己ループがある場合は、そこに到達するすべての方法でこれを 1 回含める必要があります。つまり、状態空間に到達した方法を追跡し、状態空間がパスで一意であるだけでなく、これを一意にしたいのです。

たとえば、011 から、長さ 1 の 3 つのパスすべてが円弧で見つかるようにします。

次のレベルでは、ノードに到達するために必要な 2 つのアークを示す 3 つのノードを持つすべてのパスが表示され、次のレベルでは、必要な 3 つのアークを示す 4 つのノードを持つすべてのパスが表示されます。

これが役立つ場合、コードを SWISH に入れましたか? （初めてみる？！）

http://pengines.swi-prolog.org/apps/swish/p/HxBzEwLb.pl#&togetherjs=xydMBkFjQR

BFS はO(b^d)メモリを必要としますが、IDDFS はO(bd)メモリのみで実行されることが知られています。しかし、これら 2 つの実装をプロファイリングすると、まったく同じ量の RAM を使用していることが判明しました。

Treeテストを実行するために、分岐係数または 10のクラスを使用しています。

私の実装iddfs：

BFSは

コードは実際には何もしていません。ツリー全体をループしているだけです。コードのプロファイリングにhttps://github.com/fabianp/memory_profilerを使用しています。

Alpha-Beta プルーニングを使用して Minimax アルゴリズムのパフォーマンスを向上させるために、反復深化を実装しました。

where メソッドiterativeDeepeningは単純にベスト ムーブの ID を返します。

まず、これが Iterative Deepening を実装する正しい方法かどうかはわかりません。

次に、AI が間違った動きをし始めたことに気付きました。反復的深化が意思決定に影響を与える可能性はありますか?

転置テーブルと Iterative Deepening を使用している間、アルゴリズム速度の大幅な改善を測定しますが、速度のために AI の品質を犠牲にしたくはありません。