問題タブ [breadth-first-search]

特定のフォルダー内のすべてのファイルとフォルダーの幅優​​先走査を実行するイテレーターを作成しようとしています。私はすでに深さ優先トラバーサルでこれを実行しました。これは、たとえば次のように戻ります。

等

今、私は代わりに幅優先で結果を返すプログラムを作ろうとしています:(またはレベルごとに）

同じ階層に対して。しかし、私はつまずきに遭遇しました。これらを正しい順序で（具体的には逆の順序ではなく）実行したい場合、最終的にO（n）メモリを必要とせずにこのアクションを実行する方法を見つけることができません。nは、ドライブ上のファイル/フォルダーの数です。これは、ある時点でドライブ階層全体をメモリに保持する必要があるように思われるためです。一方、DFSの場合、以前に列挙したすべてのエントリを完全に無視できます。階層内の同じレベル。

だから私の質問は：フォルダをトラバースするためにメモリを使用するための線形よりも優れた方法はありますか？

パズル ゲームを解くプログラムを作成しています。ボード上で考えられるすべての動きを見つけ、結果として得られるすべてのボードをオブジェクトに配置します。次に、結果のボードで可能なすべての動きを見つけます。オブジェクトは次のようになります。

トップレベルのボードから可能な動きを追加する方法を理解することはできますが、2 番目のレベルで結果として得られるすべてのボードをループしてそれらの可能性のある動きを把握し、次にすべての 3 番目のレベルのボードをループする方法を理解できません。等々。可能な移動を追加し、幅優先検索を使用してオブジェクトをトラバースするにはどうすればよいですか?

私はcでbfsを実装しようとしています

これらはデータ構造です

これは私の検索コードです

このsegfaultsは、なぜか私の実装が間違っているのかわかりません。

タイトルが少し乱雑であることは知っていますが、それをよりよく説明する方法がわかりません。

私がやろうとしていること：

テキストファイルで見つかったグラフを使用して、頂点Aから頂点Bまでの最短経路（頂点の最小量）を見つけて印刷します。

注：ダイクストラ法ではなく、幅優先探索を使用します。

私が持っているもの：

グラフにBFSを適用する実用的なアルゴリズムですが、実際に最短経路を印刷する良い方法はありません。

最短経路の頂点と、アルゴリズムを介して実行されるが最短経路ではない頂点を区別するのに苦労しています。

例：0と4の間の最短パスを見つけます。0は1,2と3に接続します。1は4に接続します。私のパスは[0,1、1ではなく[0,1,2,3,4]になります。 4]。

同じ質問をしているスレッドや、これを含むBFSのウォークスルーを見つけることができなかったので、これを実際よりもはるかに難しくしているのかどうかわかりません。

編集：興味があるかもしれない人のためのコード（私がサークルを避けているかどうかはまったくわかりませんか？）

編集2：スタックへのパスを保存する方法を変更しました。

変数とメソッドの説明：

v=原点

w=ターゲット頂点

g=グラフ

vi=vの近傍を反復処理する通常の反復子

読んでくれてありがとう！

他の場所で入手して少し変更したBFSの実装がありますが、その入力に問題があります。
グラフを取り、'（（abc）（bc）（cd））として受け取りますが、私が与えている入力は加重グラフです... BFSには役に立たないことはわかっていますが、加重を使用しています後でさらに下の行。この入力は、などの ようになります。
'(
(a (b 3) (c 1))
(b (a 3) (d 1))
(c (a 1) (d2) (e 2))
)

私のコード：

新しいスタイルリストを受け入れるためにどこを変更する必要があるのか​​、またはヘルプ関数を作成して正しくフォーマットする必要があるのか​​がわかりません。

私は数日連続で Haskell のスペース リーク (当然のことながら、スタック オーバーフローのようなもの) に頭を悩ませてきました。自然に再帰的ではない CLR から直接 BFS アルゴリズムを模倣しようとしているので、イライラします。注意: BangPatterns を有効にし、この問題を分岐してバインドしようとして、可能なすべての場所の前に bang を配置しましたが、効果はありませんでした。私は以前にスペースリークと戦ったことがあり、これをあきらめて助けを求めて泣くのは嫌ですが、この時点で行き詰まっています. 私は Haskell でのコーディングが大好きで、関数型プログラミングの禅をよく理解していますが、スペース リークのデバッグは、画鋲でいっぱいの床を転がるのと同じくらい楽しいものです。

とはいえ、私の問題は、典型的な「アキュムレータ」の種類のスペース リークのようです。スタックは明らかに、以下のコードの bfs' への呼び出しの周りに構築されます。スペースリークのヒントは大歓迎です。

山登り法の検索を行うために変換しようとしているBFSのLisp実装があります。

私のBFSコードは次のようになります。

これで、BFSのように常に左側のノードを拡張するのではなく、目標状態に最も近いと思われるノードを拡張する必要があることがわかりました。
私が使用しているグラフは次のようになります。

上記のBFS実装でこれを機能させるための変換関数がありますが、このグラフ形式を使用してこれを山登り法に変換する必要があります。

どこから始めればいいのかわからず、何の役にも立たないように努力してきました。主に関数を変更して最も近いノードを展開する必要があることはわかってexpand-queueいますが、どのノードが最も近いかを判別する関数を作成できないようです。

助けてくれてありがとう！

Seq[X]現在、かなり高価な再帰アルゴリズムを使用して を生成するコンポーネントをリファクタリングしようとしています。Stream[X]代わりにを生成するためX、オンデマンドでロード/計算することができ、プロデューサーはどのように事前に推測する必要がありません。消費者を満足させるためには、多くの掘り下げが必要です。

私が読んだことから、これは「展開」の理想的な使用法であり、それが私が取ろうとしてきたルートです。

これは、特定のモリス氏によって精査されたDavid Pollak の exampleunfoldから派生した私の関数です。

そして、ここに運試し用の小さなツリーがあります:

最後に、展開を使用する幅優先トラバーサルで失敗した試みを次に示します。

すべてのノードが返されるように、トラバーサル ロジックを修正 (または書き換え) する方法について、誰かヒントを教えてもらえますか? ありがとう！

私は試してみました。検索して検索しましたが、私の問題を解決するアルゴリズムを実際に見つけることができませんでした。ツリー内のすべてのパス (単純なパスだけでなく) を列挙したいと思います (ただし、これは簡単な制約です)。

たとえば、ツリーの場合。

次のパスを生成できるようにしたい:

それだけだと思います。

次の解決策を試しました深さ優先検索を使用してすべての単純なパスを見つけることの複雑さ? . ただし、単純なパスしか検索されないため、4-2-5-2-1-3-6 などのパスは検索できませんでした。

あなたが私を導くことができる方法はありますか、おそらくアルゴリズムはありますか?