幅優先検索アルゴリズムが間違っています

php エディターのイチゴ幅優先検索アルゴリズムは、一般的に使用されるグラフ走査アルゴリズムですが、場合によっては、間違った結果が生成される可能性があります。幅優先探索アルゴリズムは、通常、グラフの最短経路問題を解決するために使用されます。その中心的な考え方は、開始ノードから開始して、ターゲット ノードが見つかるか、すべてのノードが探索されるまで、グラフ内のノードを層ごとに探索することです。ただし、グラフ内にサイクルがある場合、またはターゲット ノードが複数ある場合、幅優先検索アルゴリズムは正しい結果を取得できない可能性があります。したがって、幅優先検索アルゴリズムを使用する場合は、その制限に注意し、特定の問題シナリオに基づいて適切なアルゴリズムを選択する必要があります。

質問内容

昨日、dfsについて質問させていただきました。今日はbfsを実装してみます。

このスレッドに記載されていない .java クラスは、前の質問から引用したものです。

私がこのクラスを書きました:

breadthfirstsearch.java

リーリー

main.java クラスに次のコードを追加しました:

リーリー

breadthfirstsearch.java のコンストラクターの場合、次の行列が得られます:

リーリー リーリー

これらの条件は最初はどれも当てはまらないため、スキップできます。

リーリー

ノードをposition=visitedで設定したので、再度確認する必要はありません。

これらの条件のうち、(1) と (3) のみが真であるため、2 つの int[] 配列を両端キューに追加します。 リーリー

最後に、訪問したノードを削除します:

リーリー

出力で得られる内容は次のとおりです:

リーリー

それでは、コードはどこにあるのでしょうか?

解決策

ポジションを正しく処理していません。このコードの突然変異

i: リーリー

あなたは、

c が array の copy であると考えているようですが、そうではありません。 i によって参照される配列のみを参照するため、c[0] を実行すると、その single 配列にはそのインクリメントされた値が含まれます。次回そのようなコードを (次の if ブロックの 1 つで) 適用するときは、元の位置からではなく、すでに変更された i から開始します。 「道に迷ってください。

正直に言うと、前の質問に対する

私の回答 で、配列型の位置を使用するという考えがあまり洗練されていないコードになることをすでに指摘しました。そして今、それがいかに簡単にバグを持ち込むかがわかります。それ。

このような配列を使用する場合は、実際に新しい配列を構築し、元の配列の内容をコピーする必要があります。

コードのこの部分の修正は次のとおりです:

リーリー

以上が幅優先検索アルゴリズムが間違っていますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。