問題タブ [iterative-deepening]

私は (例えばhttp://radagast.se/othello/Help/order.html ) を読みましたが、最初に各レベルで最良の動きを検索すると (反復的な深化を使用して見つけることができます)、検索がはるかに高速になります。

追加のメモリと CPU 時間をあまり使用せずに、可能な限り最良の動きを検索するにはどうすればよいでしょうか?

誰かがIterative Deepening A*について説明できますか? 私はまだそれがどのように機能するのか理解していません。 Depth First Searchを使用した反復的な深化検索、およびそれでも解決策が見つからない場合。解決策が見つかるまで深度++ を増やします。

Depthを使用した Iterative deepening の場合、Iterative Deepening A* は何を使用して検索を制限しますか?

IDA* がどのように機能するかを説明する必要がある場合は、次の図を参照してください。

(1,2,4,9)などはステップです

0+2=2 はf(n)=g(n)+h(n)

ボードゲームをコーディングしています。アルファベータ法を使用してゲームツリーを生成しました。2つのオプションがあります。

1. 反復深化を使用してアルファベータを最適化し、時間が経過するまでもう1つの層を生成し続けるようにします。
2. 試行錯誤の結果、事前に下層を検査しなくても、制限時間内にすべてのボード構成で到達可能な最大深度がわかりました。

どちらのアプローチが優れており、検索がより深く到達するようになりますか？たとえば、最初は、利用可能なすべての時間を消費する深さXのツリーを生成できることを知っています...反復深化はさらに深さを追加できますか？

もっと明確にできるかどうか教えてください...

ここで尋ねられたこの質問のいくつかのバリエーションを見てきましたが、それらを私の状況に適用する方法がわからないので、誰かがここで私を助けてくれることを願っています.

次のような形式のフラットな XML ファイルがあります。

次のように、id 属性に基づいてタグを階層的に設定しようとしています。

一部の id 値には 2 桁の数字 (「1.2.3.15.1」など) が含まれているため、比較がさらに困難になります。

ヘルプ？

更新: 最初の解決策を検索します。

通常の深さ優先検索の場合は単純で、ハッシュセットを使用するだけです

しかし、深さ制限になると、これだけでは済まされない

その場合、事前に完全な検索を行うことはありません (ある意味で、解決策があれば常に見つけることができるという意味で)。maxdepth

どうすれば直せますか？アルゴリズムにスペースの複雑さが追加されますか?

または、状態をメモする必要がまったくありません。

アップデート：

たとえば、決定木は次のようになります。

状態 A から開始し、G はゴール状態です。明らかに、深さ 3 の下に解があります。

ただし、深さ 4 で私の実装を使用すると、検索の方向がたまたま

A(0) -> B(1) -> C(2) -> D(3) -> E(4) -> F(5)深さを超えると、 に戻りますがA、E訪問された場合、チェック方向は無視されますA - E - F - G

深さ優先探索は、ファイルシステムを検索するための恐ろしい方法です。実際には、ルートに非常に近いディレクトリの下にある可能性のあるファイルは、DFSが別の深さによって気を散らされるため、DFSで検出されるまでに長い時間がかかる可能性があります。ディレクトリの無関係な階層。
ただし、そのリソース要件は非常に優れています。開いたままにしておく必要のあるファイルハンドルの数は、サイズではなく、階層の深さにのみ比例します。

幅優先探索は明らかな解決策です-それは非常に高速です。
（前回の測定では、システムのDFSとほぼ同じ時間で約8秒かかりました。）

しかし、BFSには独自の問題があります。BFSでは、非常に多くの、場合によっては数百万のディレクトリハンドルを開いたままにしておく必要があります。（私のシステムでは、ハンドル数は約100,000で、途方もなく高いです。簡単にそれ以上になる可能性があります。）

これにより、いくつかの問題が発生します。

• 非常に多くのハンドルを開いたままにしておくと、メモリ（とにかく比較的安価）だけでなく、仮想ファイルシステム内のファイル（ネットワーク、マウントされたディレクトリなど）へのハンドルや、場合によっては他の制限されたカーネルなど、他の多くの種類のリソースが消費されます。レベルのリソース。

• また、ユーザーにとって他の実際的な問題も引き起こします。たとえば、開いたままになっている仮想ディレクトリは閉じられなくなります。これは、たとえば、ユーザーがプログラムを閉じたり、デバイスを取り出したり、ある種の外部接続を閉じたりできない可能性があることを意味します。このアプローチでは、あらゆる種類の問題が発生する可能性があります。

反復深化のように見えるかもしれませんが、それが解決策です。

問題？実際には非常に遅いです。問題は、大きなディレクトリ（WindowsのWinSxSなど）が、必要がない場合でも、深度レベルごとに
再列挙されることです。前回これを試したとき、反復深化は私のシステムのDFSよりも約15倍遅くなりました。したがって、8秒の検索には約120秒かかりましたが、これは許容できません。

もちろん、開くべきではないディレクトリを追跡しようとすると（おそらく、もう開く必要がないことに気付いたため）、BFSで発生したすべてのリソースの問題を明らかにすることで、最初に反復深化を使用する目的が無効になります。 。

したがって、質問は非常に単純です。

なじみのないファイルシステムを検索している場合、速度と使いやすさの許容可能なバランスを実現するには、どのように進めればよいでしょうか。BFSよりも良い選択肢はありますか？

私は、 8パズル問題の解決策を見つけるために、反復深化深さ優先探索の実装に取り​​組んでいます。私は実際の検索パス自体を見つけることに興味はありませんが、プログラムの実行にかかる時間を計るだけです。（私はまだタイミング機能を実装していません）。

ただし、実際の検索機能を実装しようとすると問題が発生します（下にスクロールして表示）。これまでに持っているすべてのコードを貼り付けたので、これをコピーして貼り付けると、実行することもできます。これは、私が抱えている問題を説明するための最良の方法かもしれません...たとえば、最初の展開が必要なパズル2（p2）のテストで、再帰中に無限ループが発生する理由がわかりません。解を生成します。コード行の1行の前に「Return」を追加しないことと関係があるのではないかと思いました（以下にコメントがあります）。リターンを追加すると、パズル2のテストに合格できますが、パズル3のようなより複雑なものは失敗します。これは、コードが左端のブランチのみを展開しているように見えるためです...

何時間もこれにいて、希望をあきらめました。私はこれについて別の目で見ていただければ幸いです。私の誤りを指摘していただければ幸いです。ありがとうございました！

反復的な深化アルゴリズムを作成しました。サイクル チェックを追加した場合を除いて機能し、アルゴリズムは必要以上に深いソリューションを返します。しかし、サイクルをチェックしないと正しく動作しますが、時間がかかりすぎます。誰でもバグを見つけることができますか？

編集：ここに展開機能があります

これはアクションの 1 つです。小さな変更を除いてすべて同じです。

述語

I'm looking at the pseudocode on Wikipedia for this and trying to use it to write the algorithm in java. My question comes in a difference in how the result is returned. On wikipedia, one result is returned, and this breaks out of the search. In mine, everytime a relevant node is found, it is added to a list, and that list is to be returned when the tree has been processed. How would I detect the end of the tree in order to break out and return the list?

Wikipedia:

Mine:

Edit: After changes:

ツリー全体を解析し、検索クエリに一致する可能性のあるすべての結果を見つけて、それらすべてをリストとして返すことになっている検索アルゴリズムがあります。これはアルゴリズムの要点ではないことはわかっていますが、幅優先検索と深さ優先検索のテストとしてこれを行って、タイミングを合わせて最速のものを確認しています。他の 2 つの検索は意図したとおりに機能しますが、DFID 検索の目的と同じ検索情報を入力すると、空のリストが表示されます。したがって、データが正しいことはわかっていますが、アルゴリズムの何かが間違っているだけで、何が原因なのかわかりません。ウィキペディアの疑似コードに基づいてこれを書きました。ここに私が持っているものがあります: