問題タブ [iterative-deepening]

これは、 Find first null in binary tree with limited memoryのフォローアップです。

ウィキペディアによると、深さ優先検索を繰り返し行うと、最短経路が見つかるとのことです。メモリ内で k ノードに制限され、ツリーへのアクセス回数が最も少ない実装が必要です。

たとえば、私のバイナリ ツリーが次の場合:

また、検索順序よりもメモリの 5 ノードに制限されています。

次の読み取りが 7 の場合、3 を再読み取りする必要があります。しかし、次の読み取りが 14 の場合、まだ 3 を再読み取りする必要はありません。解が 14 の場合、アルゴリズムは少し速くなります!

一般的な解決策を探しています。任意のサイズのメモリとノードあたりのブランチ数で機能するもの。

次の構造が与えられます：

これに到達する方法はありますか：

つまり、高レベルのタイトルを低レベルのタイトルとそれに続くすべてのコンテンツに近づけて、ネストされた構造を作成する方法はありますか。各TITEL1、2、および3タグのコンテンツは、新しい要素に入れる必要があり<TITEL>ます

次の XML 構造が与えられます (これは XML ファイルにあり、他の多くのコンテンツが含ま<p>れています。タグは、他のタグが続く可能性があることを示すためだけに存在します):

PHPを使用してこれに到達する方法はありますか（新しいファイルに書き込みます）：

または、言い換えれば、上位レベルのタイトルを下位レベルのタイトルとそれに続くすべてのコンテンツで囲み、ネスト構造を作成する方法はありますか。各 TITEL1、2、および 3 タグのコンテンツは、新しい要素に入る必要があり<TITEL>ます

フォーラムの XSLT 側で既に同じ質問をしましたが、c# または Java で試すようにアドバイスを受けました。私はこれらの言語を知らず、PHP の基本よりも多少知っているので、そのようにしようと考えました。誰か私を道に立たせてくれませんか?

私は BFS と DFS を理解していますが、一生深化と BFS の違いを理解することはできません。どうやら反復的な深化は DFS と同じメモリ使用量を持っていますが、BFS のように拡張し続けるだけなので、これがどのように可能かはわかりません。誰かがそれを明確にすることができれば、それは素晴らしいことです。

必要に応じて作業するツリー:

解決したい最適化問題があります。ある種のデータ構造があります。

および評価関数：

rateFoo構造体の値を変更して、結果を最適化する必要があります。この特定のケースでは、問題を解決するために反復深化探索を使用することにしました。最適化を最適化するための（無限の）検索ツリーは、別の関数によって作成されます。この関数は、考えられるすべての変更をツリーに再帰的に適用します。

私の検索機能は次のようになります。

私が始める前に私が持っていた質問はこれです：

ツリーは各ポイントのデータによって生成できるので、現在アルゴリズムで必要とされているツリーの部分のみを生成することは可能ですか？メモリを節約するために、必要に応じてメモリを解放し、ツリーを再生成することは可能ですか（レベルnのリーブを生成できO(n)、nは小さいままですが、ツリー全体をメモリに保持するのに十分な小ささではありません）。

これは私がランタイムから期待できるものですか？ランタイムは式を未評価にすることができますか（評価された式を未評価の式に変換します）？または、これのために私がしなければならない汚いハックは何ですか？

私は次の制御構造を使用しています（これは末尾再帰だと思います）

反復深化を行うには

この空きメモリは（技術的には到達できなくなるため）、各反復深化後のようになりますか？そうでない場合は、制御構造をどのように書き直す必要がありますか？

PS 2番目に、末尾再帰構造は、この場合ではなくても、前の値に追加するようにスタック上のものにアクセスできることが多いため、これは失敗するように見えます。– Roman A.Taycher11月28日12:33PPS3番目に、dfsWithMaxDepthが返されるとすぐに、dfsWithMaxDepth内の値を破棄できると思いますが、多くの回答は多くのメモリを消費しません。–ローマンA.タイチャー11月2日

反復ごとに n-1 レベルのノードを再スキャンするのは冗長ではありませんか?

その瞬間、私はこのようなオブジェクトを持っています。

そして、ループを許可しないという事実を除けば、非常によく似た別のオブジェクトに変換しようとしています。

すでにより深い位置に出現しているノードの子を拡張しないことにより、ループを処理する必要があります。反復深化はこれを解決します（深さ優先探索の実装ですが、幅優先探索の順序）が、次の構造を使用した実装に苦労しています。

私が見つけたすべての実装は、ある種のゴールノードを見つけることに依存していますが、ツリー全体を拡張する必要があります。

どんな助けでもいただければ幸いです。：D

iterative deepeningについて読み続けていますが、 depth-first searchとの違いがわかりません。

深さ優先探索がますます深く進んでいることがわかりました。

反復的な深化では、レベルの値を確立します。そのレベルに解決策がない場合は、その値を増やして、ゼロ (ルート) からやり直します。

これは深さ優先探索と同じではないでしょうか?

つまり、解決策が見つかるまで、どんどん増やしていきます。私はこれを同じものと見ています！ゼロからやり直すと、以前と同じブランチにたどり着くので、同じブランチにたどり着きます。

したがって、現在、次の擬似コードを含むDFSがあります

検索の深さを制限する 3 番目の引数を受け入れるようにこの関数を変更するにはどうすればよいですか?