breadth-first-search

1熱

1答えて

私は15のゲームでアルゴリズムBFS、DFS、A *（2つのヒューリスティックスを持つ）のストローク数を比較するプログラムを構築しようとしています。私のカウンタは、BFSとDFSの両方のカウンタの2つのアレイと同じ結果をカウントします。しかし、実際には、メイン（クラスProject）から4つの異なる配列を使用しています。これらのストロークに対して4つの異なる変数を割り当てています。私の考えでは

0熱

1答えて

BFS最短経路を得るために経路を再構築

私は幅優先探索から最短経路を構築したいと考えています。私はJavaコードでBFSを実装しましたが（下図参照）、コードの実装から最短パスを得るためにパスを再構築する方法はわかりません。私は親の配列を保持しなければならないことは分かっていますが、私はどこにコードを入れるべきかわかりません。基本的には、スタートポイントからゴールポイントまでのBFSを使用して最短パスをトレースしたいと思います。私は2D

1熱

1答えて

最大深さを有する実装BFSアルゴリズムとそのすべての最短経路を印刷

これは私がグラフ内の他のノードにルートノードからのすべての最短経路を印刷することを思い付いたBFSアルゴリズムである： d = deque() d.append(root) level = 0 while len(d) >= 0 and level <= max_depth: u = d.popleft() print(adjacency_list[u]) fo

0熱

1答えて

BFSがパスを返さない

開始点と終了点を指定して2次元配列にBFSを実装しようとしています。私は、グリッド上に2点の関数を与えようとしましたが、パスがないことを意味する空の配列を返します。誰かが間違っていることを指摘してください、可能であれば、私のエラーを修正するのに役立ちますか？ありがとう。 public Point[] bfs2(Point start, Point end) { boolean[][]

1熱

1答えて

横方向の最初の探索と無向グラフの比較

有向グラフと無向グラフのbfsはどのように実装が異なりますか？私は以下の擬似コードをWeb上に見つけました。私は無向グラフで大丈夫です。有向グラフのためにそれを実装する方法を理解することはできません。 frontier = new Queue() mark root visited (set root.distance = 0) frontier.push(root)

-3熱

1答えて

bfs中の各レベルでのノード数の検索

N個のノードで構成されるツリーが指定されています。ツリーは、N個のノードとN-1個のエッジとからなる完全に接続されたグラフである。このツリーのノードは、1からNまで索引付けされます。索引付けされたノード1をこのツリーのルート・ノードとみなします。ルートノードはツリー内のレベル1にあります。あなたは木と1つの整数xを与えられます。レベルxに横たわっているノードの数を調べる必要があります。入力形式

1熱

1答えて

エッジがソートされたウェイトの順序で両端キューに挿入されない場合、0-1 BFSは正解を生成しますか？

0-1 BFSアルゴリズムの一般的な傾向は次のとおりです。エッジに重み= 0がある場合、ノードは両端キューの前にプッシュされ、エッジの重み= 1の場合、バックにプッシュされますデュークのランダムにエッジをプッシュすれば、0-1 BFSは正しい答えを計算できますか？両端キューにエッジが入力されている場合、その重みのソート順ではありません。これは一般的な0-1 BFSアルゴリズムです。最後のifと

0熱

2答えて

与えられた迷路のデータ構造を選択するにはどうしたらいいですか？

私は迷路の問題を以下の図に示すように持っています。これは6x6マトリクスと見なすことができますが、目標は特定の着色ブロックの出口を見つけることです。私が見た迷路の問題に基づいて、dfsを使うのではなく、bfsを適用するのが良いアイデアかもしれないと思います。しかし、私は、2つ以上のノードを保持できるツリーをどのように実装できるのか混乱しています。木の代わりに使うことができる他のデータ構造はありま

0熱

1答えて

ポイントからポイントへの効果的な道を得る（行列上のBFS）

私は0とXのマトリックスを持っています（0は歩き、Xは壁を意味します）。私は始点と終点を持っています。 BFSを使用して、開始から終了までの最短経路（長さ）を見つけました。しかし、今私は効果的な道路を見つける必要があり、私はそれを行う方法がわかりません。（私はLeeアルゴリズムの再帰を使うことができると思った）。 Example: 5 5 SXXXF 0XX00 0XX0X 00

-3熱

1答えて

BFSアルゴリズムでキューが使用されるのはなぜですか？

私はウィキペディア Breadth-First-Search(Graph, root): 2 3 for each node n in Graph: 4 n.distance = INFINITY 5 n.parent = NIL 6 7 create empty queue Q 8 9 root.distance = 0 10 Q.enqueue(