問題タブ [iterative-deepening]

このリンクから反復的深化を研究しています。私の主な関心事はOverheadです。そのリンクはそれを言う

分岐係数が高いほど、繰り返し展開される状態のオーバーヘッドが低くなります

この声明についての説明はなく、そのリンクには説得力のある議論もありません。このステートメントの背後にある理由を探しています。なぜなら、分岐係数が増加するにつれてオーバーヘッドが増加するはずであり、それはノードが増加していないことを意味し、オーバーヘッドがどのように減少しているのか?

今まで、合理的で役立つものは何も見つかりませんでした。誰かが私の概念を修正するのを手伝ってくれるなら、私はあなたに感謝します.

6x6 Rush Hour パズルを解くための反復的な深化アルゴリズムを作成するという学校の課題があります。練習する必要があるので、すべてのことで JavaScript を使用することにしました。ただし、アルゴリズムを大幅に最適化するのに問題があります。

私はパズルを解こうとしましたが、その解はツリーの 8 レベルにあり、7,350,669 個のノードにアクセスし、コンピューターで解くのに約 13 分かかりました。

アルゴリズム自体を理解するためのヒントとヘルプを探しています。

NodeとVehicleの2つのクラスを作成しました。これらの実装が問題の一部である可能性があります。

グリッド用の「2次元」配列と車両の配列の両方を持つことはやり過ぎだと思いますか? 動きの可能性をチェックするときは、車両配列を反復処理しますが、ガードを使用して、車両の前方に自由な道があるかどうかをすばやく確認します。これで私が見た問題に戻ります。

アルゴリズムのコードを公開することはできませんが、IDDFS を理解し、アルゴリズムを実装する方法は次のとおりです。

1. 現在のノードが最終状態であるかどうかを確認し、そうである場合はソリューション配列に追加して true を返します。
2. それ以外の場合は、maxDepth に到達したかどうかを確認し、到達した場合は false を返します。
3. そうでない場合は、この状態の車両ごとに、実行できるすべての移動用の新しいノードを作成します (最後の移動で移動されたものを除く)。
4. 作成したばかりのすべての子にアクセスし (手順 1 に戻ります)、false が返された場合は削除します。
5. どの子ノードも最終状態にならなかった場合は、親ノードに戻ってその隣接ノードを調べます。それ以外の場合は、真の連鎖反応が発生します。
6. 最終状態が見つかるまで繰り返します。トップに戻ったら、maxDepth を 1 増やして、プロセス全体を繰り返します。

私が目にする 1 つの問題は、私のデータ構造が少し複雑である可能性があることです。JavaScript はオブジェクトとオブジェクトの配列を参照として渡すため、以下を使用してディープ コピーする必要があります。

ここでの主な質問は、何か見逃したことがありますか? 「悪い」子ノードを削除し、反復深化アルゴリズムでツリー全体を何度も繰り返し続けるのは正しいですか、それとも誤解していましたか? ツリー全体を再度生成する必要がないように、それらは「チェック済み」としてマークされてから返され、後で通過するだけですか?

Tic-Tac-Toe をプレイする AI を作成する必要がある人工知能クラスを受講しています。

インストラクターは、AI が次の動きを出すときに、AI の意思決定プロセスにアルファ ベータ プルーニングを使用するように指定しました。この時点で私が直面している問題は、AI が意思決定ツリーを作成して移動するのにかかる時間です。通常の 3x3 は問題なく、3x4 と 4x3 は少し時間がかかりますが、4x4 は最初の移動に数分かかります。

私が使用したソースコード：

必要に応じてソースリンク

インストラクターも反復深化検索を使用することを提案しましたが、私はその方法がわからないダミーです。

検索手法の反復深化について質問があります。私の質問は、通常の深さ優先検索と指定された深さ制限のない反復的深化の違いは何ですか? したがって、目標ノードを持つツリーがありますが、反復的な深化検索に指定された制限はありません。これは、通常の深さ優先検索を行った場合と同じトラバーサル シーケンスを出力しますか?

Iterative Deeping A* Search を実装しようとしています。問題は、彼が私が望むようにではなく、規則正しく行くことです。

ノードを宣言したとき、彼がいるレベル (adancime) も書きました。

したがって、私の論理は、(彼が取得したレベルが課題のレベル(adancime)と同じである) 場合は、そこで試してください。

私のグラフはこれです：

ソース: S 目的地: G

彼が与えるべきパスは次のとおりです: SBDHFH F.... (彼はノードを見つけられないはずです) ある時点で常に最小値 H または F を取得するためです。

これが私のコードです：

最初にツリー形式にして、このグラフに IDDFS を適用しようとしましたが、結果は次のようになりました。

パスで繰り返されるノードについて混乱しています。それらを削除できますか?それとも最終パスに表示されますか?

これは、グラフをトラバースして GOAL に到達する正しいアプローチですか? そして、グラフで次にどのノードにアクセスするかをどのように知るようになるか (たとえば、ツリーのように、左から右に開始します)。

同じグラフに DFS と BFS を適用すると、パスはどうなるでしょうか?

DFS の結果と IDDFS に違いはありますか? 似てるらしい

Java で 8 パズル問題の深さ優先検索 (再帰) を実装しました。

反復的な深化深度検索に変換するために何を変更する必要があるのか​​ わかりません。深さはラウンドごとに増加するため、深さに制限がないことはわかっています。これを試しました：

必要なIDSに変更する方法を知っている人はいますか? 前もって感謝します！

プロローグの人工知能に関する Ivan Bratko の著書の例を以下に示します。

「Prolog Programming for Artificial Intelligence - 3rd Edition」 (ISBN-13: 978-0201403756) (1986 年 Addison-Wesley による初版、ISBN 0-201-14224-4)

私は、多くの例が最後まで実行されず、スタックしたように見えることに気付きました。私は手紙に従っていくつかの異なる実装を試みましたが、うまくいきませんでした。誰かがコードをざっと見て、どこに欠陥のあるロジックがあるか、または私が間違いを犯したかどうかを確認できますか?

これは、本に示されているブロック世界のSTRIPS スタイル プランナーの完全なプログラムです。

私は 7 つのブロックと 4 つの場所を追加し、すべてのブロックが位置 1 に a から g までアルファベット順に積み上げられる表現でテストしました。目標は、位置 2 に同じ順序で積み上げることです。

プログラム呼び出しを実行するにはplan(StartState,GoalState, Sol).

参考文献:

• 動きの定義: http://media.pearsoncmg.com/intl/ema/ema_uk_he_bratko_prolog_3/prolog/ch17/fig17_2.txt
• 終了は、目標回帰を伴うプランナーを意味します: http://media.pearsoncmg.com/intl/ema/ema_uk_he_bratko_prolog_3/prolog/ch17/fig17_8.txt

アドバイスをいただければ幸いです。