問題タブ [breadth-first-search]

グラフの基本的な幅優先検索トラバーサルについての私の理解は次のとおりです。

ただし、特定のノードから有向グラフをトラバースする必要があり、特定のノードからすべてのノードに (直接的または間接的に) アクセスできるわけではない場合、この状況のグラフをトラバースするために BFS をどのように使用すればよいでしょうか?

このグラフについても説明してください。

ここで、開始ノードが である場合、andbは出力されません。ac

アルゴリズムに何か欠けていますか?

HashMap<String, ArrayList> adj = new HashMap();グラフを保存する隣接リストを作成していました。

与えられた有向非重み付けグラフで2つのノード間のすべての最短経路を見つける必要があるという問題に取り組んでいます。私はBFSアルゴリズムを使用して作業を行いましたが、残念ながら、すべてではなく1つの最短パスしか印刷できません。たとえば、長さが3の4つのパスの場合、アルゴリズムは最初のパスのみを印刷しますが、すべてを印刷したいと思います。 4つの最短経路。次のコードで疑問に思っていたのですが、2つのノード間の最短パスをすべて出力できるように変更するにはどうすればよいですか？

私はあなたのすべての大きな助けに感謝しますありがとう、アンドラ

深さ優先検索に関するウィキペディア:

深さ優先検索 (DFS) は、ツリー、ツリー構造、またはグラフをトラバースまたは検索するためのアルゴリズムです。1 つはルート (グラフの場合はルートとしていくつかのノードを選択) から開始し、バックトラックする前に各ブランチに沿って可能な限り探索し ます。

幅優先探索とは

「開始ノードを選択し、すべてのノードのバックトラックをチェックし、最短パスを選択し、隣接ノードのバックトラックを選択し、最短パスを選択し、連続的なバックトラックにより各パスをトラバースするため、最終的に最適なパスを見つけるアルゴリズム。

Regexfindのプルーニング -- バックトラッキング?

バックトラッキングという用語は、そのさまざまな用途のために混乱を招きます。UNIX のfindSO ユーザーの剪定は、バックトラッキングで説明されました。Regex Buddy は、正規表現の範囲を制限しない場合、「壊滅的なバックトラッキング」という用語を使用します。あまりにも広く使われている包括的な用語のようです。そう：

1. グラフ理論で特に「バックトラッキング」をどのように定義しますか?
2. 幅優先検索と深さ優先検索の「バックトラック」とは何ですか?

[追加した]

バックトラックに関する適切な定義と例

1. ブルートフォース法
2. ストールマン (?) が発明した用語「依存性指向のバックトラッキング」
3. バックトラッキングと正規表現の例
4. 深さ優先検索の定義。

このアルゴリズムがどのように機能するかは知っていますが、どのアルゴリズムをいつ使用するかを決めることはできませんか?

他の考慮事項よりも優れたパフォーマンスを発揮するガイドラインはありますか?

どうもありがとう。

次のHaskellツリータイプがあるとします。ここで、「State」は単純なラッパーです。

また、リーフノードを取得してブランチに展開する関数「expand :: Tree a-> Tree a」、またはブランチを取得して変更せずに返す関数もあります。このツリータイプは、N-ary検索ツリーを表します。

深さ優先探索は無駄です。検索スペースは明らかに無限であり、ツリーのすべてのリーフノードでexpandを使用して検索スペースを簡単に拡張し続けることができ、誤ってゴール状態を見逃す可能性があります。巨大です...したがって、唯一の解決策は幅優先探索であり、ここでかなり適切に実装されています。そこにある場合は解決策が見つかります。

しかし、私が生成したいのは、解決策を見つけるためにトラバースされたツリーです。これは問題です。なぜなら、私はこの深さ優先を行う方法しか知らないからです。これは、最初の子ノードで「expand」関数を何度も呼び出すだけで実行できます...ゴール状態が見つかるまで。（これは、本当に不快なリスト以外のものを実際に生成することはありません。）

誰かが私にこれを行う方法（またはアルゴリズム全体）についてのヒント、またはそれがまともな複雑さで可能かどうかについての評決を教えてもらえますか？（または、これに関する情報源は、かなり少ないので。）

主に、BFS ではなく、グラフ内のサイクルを見つけるために DFS が使用されます。理由はありますか？どちらも、ツリー/グラフをトラバースしているときに、ノードが既にアクセスされているかどうかを確認できます。

幅優先探索のJavaコードは次のとおりです。

同じことをする再帰関数を書くことは可能ですか？

最初は、これは簡単だと思ったので、次のように思いつきました。

それから私はそれが機能しないことに気づきました。それは実際にはこれと同じことをします：

これについて誰かが以前に考えたことがありますか？

私はこのプロジェクトに一人で取り組んでおり、別の目でこれを見て、自分が間違っていることを確認することができます。最初のループは無限に実行されます。

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

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

巨大なグラフ内のノード間の最短経路をリアルタイムで見つける方法を探しています。数十万の頂点と数百万のエッジがあります。この質問は以前に尋ねられたことを知っており、答えは幅優先検索を使用することだと思いますが、それを実装するために使用できるソフトウェアを知りたいと思っています。たとえば、無向グラフで bfs を実行するためのライブラリ (python バインディング付き!) が既に存在する場合、それは完全に完璧です。