問題タブ [breadth-first-search]

このコードスニペットは、bfsツリーを構築することによって値nとmのノードの距離b / wを計算しますが、どういうわけか、外側のwhileループの最初の反復で構築されたbftツリーはそのvlaueを保持し、whileループのそれ以上の反復はbftに影響を与えません

ここでグラフはタイプですvector<list<gnode>>

bfsはクラスbft_dataのオブジェクトです。

私はプロローグが初めてで、スキルを向上させるためにエクササイズをしようとしています。現時点で私は BFS で立ち往生しています。ツリーが次のようなものであると仮定しましょう:

私のクエリの後、私は次のようなものを持っています

または、少なくとも:

次のような深さレベルで結果を並べ替える方法について疑問に思っています。

または、最良の場合、次のようなものです。

ヘルプ！

ロンドンの地下鉄を検索するための幅優先グラフ検索アルゴリズムを構築中です。

アルゴリズムを理解しましたが、ご存知かもしれませんが、このアルゴリズムでは、検索が必要なすべてのエッジを (正しい順序で) 追跡するために Queue ADS が必要です。

私は、キューと大量または非常に多数のキューに入れられたアイテム (エッジ) の管理に関する効率性の問題について読んでいます。

Java ArrayList に基づいてキューを実装する方法を教えてください。これは、ヘッドとテールを追跡でき、メモリの成長中に効果的にメモリを管理しますか?

どんなヒント/ポインタも大歓迎です!!

グラフ データの隣接リスト表現を使用した幅優先探索アルゴリズムのデバッグの途中ですHashMap<String, ArrayList<Edge>>。各 String キーは地下鉄駅の名前であり、各 ArrayList はその駅のエッジのリストです。

キューを使用して、グラフのノードをトラバース順に格納しています。そのため、キューの次の子の名前を調べます。次に、次のようなものを使用して、 adjacencyList からエッジの子の ArrayList を取得したいchildEdges = stationsAdjacencyList.get(childNodeName);と思います。

私の構文は少し異なりますが、以下のコードを確認してください。

現時点では、.get() 関数は ArrayList を返していませんが、null代わりに毎回返しています。HashMap ルックアップが正しいキーを受け取っていることはわかっています。関連するバケットから値を提供することを拒否しているだけです。

コードがきれいでない場合や適切なコメントがない場合は、お詫び申し上げます。コードは常に変更されています。ArrayList<Edge> nextNodeEdges = adjacencyList.get(endpointName);うまくいけば、誰かが何もフェッチしない理由を教えてくれます。

ありがとう！！

グラフ内の任意のノードとルート/ソース間の最小距離を見つけることに興味があります。すべてのリンクには重みがあります。各ノードの親を知る必要がないため、ウィキペディアの記事previous[]に示されているを使用する必要はないと思います。あれは正しいですか？さらに、重みがすべて 1 に等しい場合、BFS を実行できますか?

私は現在、フィットネス関数を使用して 15 のパズルを解くプロジェクトに取り組んでいます。使えるフィットネス機能は3種類あり、

1. 適合度関数 1 = 1 - (置き忘れたタイルの数/タイルの総数);
2. フィットネス関数 2 = 1- (ゴール位置からのすべての間違ったタイルの距離の合計/64)
3. フィットネス関数 3= (フィットネス 2+ フィットネス 1 )/2

ソルバーは、パズル ボード全体が解決されるまで (フィットネス関数 = 1)、フィットネス関数 VALUE を改善する可能な動きを検索することを目的としています。ソルバーが失敗した検索ルートを実際のルートと一緒に出力するため、動きを生成しようとしているときにストックされます。たとえば、W、S、W、N、S、N、S、N、S、N、S、N、S、N、S ,N,S,N (逆順) で、NWSW を意味します。ただし、ソルバーは何度か前後に検索し、不要なルートも出力します。再帰で以前に訪れた場所を除外し、失敗した動きではなく有効な動きのみを出力したいと思います。コードは以下で入手できます。

AIMA（Artificial Intelligence：A modernapproach）のNorvigによると、下降するサブツリーが無限大になる場合があるため、深さ優先アルゴリズムは完全ではありません（常に解が得られるとは限りません）。

一方、幅優先アプローチは、分岐係数が無限でない場合に完了したと言われます。しかし、それは、DFSでサブツリーが無限である場合と同じ「もの」ではないでしょうか。

ツリーの深さが有限である場合、DFSは完全であるとは言えませんか？BFSの完全性は分岐係数が有限であることに依存しているため、BFSは完全であり、DFSはそうではないのはどうしてですか。

Python で幅優先検索アルゴリズムを使用して、3 文字の単語から別の単語への最短の「パス」を見つけています。私はそれを機能させましたが、パフォーマンスはひどいものであり、私の単語の子世代機能を疑っています.

基本的に、キューからポップするすべての単語に対して、1 文字を交換して形成できる他のすべての 3 文字の単語を生成します。関数は次のように機能します。

通常、これには約 0.03 秒かかります。これを行うより速い方法はありますか？

エッジが重み付けされていないグラフ内の 2 つのノード間のパスを見つけようとしています。

パスの存在を見つけるために、ターゲットを見つけると停止するBreadth First Searchを使用していますが、パス自体を取得する方法がわかりません。

訪問したノードのリストを調べてみましたが、これは役に立たないようです。Prolog を使用してこの質問に答える人を見ましたが、私は C++ プログラマーです。

も見ましたDijkstras algorithmが、単純な幅優先検索でほとんどすべてを理解できたので、これはやり過ぎのようです。

幅優先探索を使用して 2 つのノード間のパスを取得する方法は?

これは私が持っているものです。先行予約も同じだと思って深みのあるものを先に混ぜました！