問題タブ [breadth-first-search]

次の非効率的な疑似Pythonコードによって値が与えられるものを計算する必要があります。

言い換えると、ノードのすべてのペアが与えられると、foo = a *（E =エッジの数）+ b *（EE =ネイバーではないが、共通のネイバーを持つペアの数）+ c *（N（N-1 ）/ 2-EE-E）。

ある種の幅優先探索を考えようとしましたが、できませんでした。

編集：詳細

• グラフは静的ではありません。私は常にエッジを追加および削除しているので、これを一度だけ計算することはできません。私は常に「次の隣人のリスト」を更新しなければなりません。
• グラフを隣接行列として保存します。

BFS と DFS の実行時間が O(V+E) である理由は、特に次のサイトのこの例のように、頂点から到達できるノードに有向エッジを持つノードがある場合です。

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm

これは私の初めてのC++プログラミングであり、このクラスが与えられた場合に幅優先探索をコーディングするように求められました

sportstring nameとで構成される構造体int playersです。誰かが私にBFSの作成方法を説明してもらえますか？

前もって感謝します！

編集：

私はBFSのアルゴリズムを理解していますが、Cをプログラミングしたことがあるので、オブジェクト指向プログラミングを理解することは非常に混乱します。このBFSをどこから始めればよいのか、BFSを比較する新しい関数を作成するのでしょうか。start stringと_target string

wordnet から synset を取得し、それを配列として返します。これは私のコードの一部です

この行まで、synset を正常に取得しました。これから行うことは、WordNet synset の検索に幅優先検索を実装することです。すべての類義語を wordnet に格納する RiWordnet ライブラリからメソッド getAllSynsets を呼び出しています。ループ (if.​​.else) を使用してみましたが、検索を停止する場所がわかりません。BFS を使用すると、検索の範囲を知ることが期待されます。検索シノニムは、アクセスされたノードとしてマークされます。これは、同義語の検索で BFS を使用して実装したい概念です。

例えば：

また、BFS の代わりに HashSet を適用することを提案する人もいました。誰でも私を助けることができますか？前もって感謝します..

私は現在この論文を読んでおり、5ページで、一般的な知識と見なされるバイナリヒープのプロパティについて説明しています。しかし、彼らの指摘の1つは、私がこれまで見たことがなく、理解できないことです。著者は、バランスの取れたバイナリヒープが与えられた場合、標準の幅優先探索を使用して、そのヒープの要素を要素ごとのO（log n）時間でソートされた順序で一覧表示できると主張しています。元の文言は次のとおりです。

バランスの取れたヒープでは、新しい要素を対数時間で挿入できます。幅優先探索を使用するだけで、ヒープの要素を重み順に一覧表示できます。対数の時間をかけて各要素を生成します。

著者がこれによって何を意味するのかわかりません。「幅優先探索」と言うときに最初に頭に浮かぶのは、ルートから始まるツリー要素の幅優先探索ですが、要素を並べ替えた順序で一覧表示することは保証されておらず、対数時間もかかりません。要素ごと。たとえば、この最小ヒープでBFSを実行すると、関係をどのように解除しても、要素が順不同で生成されます。

これは常に11または12の前に100をリストしますが、これは明らかに間違っています。

私は何かが足りないのですか？ヒープ上で実行して、それぞれの対数時間を使用して要素をソートされた順序で取得できる、単純な幅優先探索はありますか？明らかに、毎回最小要素を削除してヒープを破壊的に変更することでこれを行うことができますが、作成者の意図は、これを非破壊的に行うことができるように思われることです。

CLRS で説明されている BFS アルゴリズムを実装しようとしています。そして、次のものを用意してください。

ただし、これを実行すると、次の出力しか得られず、その後segfaultにキューが初期化されたときにa が続きます。

次のコマンドでコンパイルしています。

私はDFSとBFSについて何度も読んだことがありますが、長い間、この疑問が頭に残っています。多くの記事で、DFSが無限ループに陥る可能性があると述べられています。

私の知る限り、この制限は、訪問したノードを追跡することで簡単に取り除くことができます。実際、私が読んだすべての本で、この小さなチェックはDFSの一部です。

では、なぜ「無限ループ」がDFSの欠点として言及されているのでしょうか。元のDFSアルゴリズムに、訪問したノードに対するこのチェックがなかったという理由だけですか？説明してください。

単純な2次元配列で整数値のグラフの場所を検索、識別、およびマークするプログラムを構築しています。

最初の例を手作業でトレースしたところ、正確に機能しているように見えました。そうは言っても、私は自分が思っていることを実行しないコードを書いたか、手のトレースが不正確でした。

私のコードは近いと思います。デバッグの支援や一般的なスタイルなどについての考えを探しています。

最終的に、このアルゴリズムは、OCRの文字のピクセルのグラフを見つけるように変更されます。画像を処理するためのコードで物事を複雑にする前に、アルゴリズムの実装が正確であることを証明したいだけです。

入力配列は次のようになります。

期待される結果は次のとおりです。

別の同様の可能性は次のとおりです。

アウト：

基本的なルール：

1. 入力ファイルの配列サイズは、.cppファイルで定義されているGSと一致する必要があります（HはWがGSに等しい）。
2. グラフは、互いに隣接する1つ以上の「1」値として定義されます。
3. 検索は、単純なキューを使用した基本的なBFS手法を使用して実行されます。
4. グラフが見つかると、その値は「1」から「2」に更新されます。
5. グラフの最終値が決定されると、「3」の値の境界ボックスがグラフの周囲に描画されます。ボックスの最小のXは、グラフの最小のXから2を引いたものに等しく、ボックスの最小のYは、グラフの最小のYから2を引いたものに等しくなります。ボックスの最大のXは、グラフの最大のXに2を加えたものに等しく、ボックスの最大のYは、グラフの最大のYに2を加えたものに等しくなります。ボックスを描画できるように、すべてのグラフに境界線から少なくとも2行/列のバッファーがあると想定します。

この配列を処理する最新の試み：

この出力を生成します：

1桁のグラフはうまく機能しますが：

出力を生成します：

これが私のコードです：

私はコーメンから次のBFS関数を持っています。

頂点sから頂点vまでの任意のパスのエッジの最小数としてのsからvまでの最短経路距離パス（s、v）の定義、またはsからvへのパスがない場合。長さパスのパス（s、v）sからvへは、sからvへの最短経路であると言われています。

以下は与えられた補題です

G =（V、E）を有向または無向のグラフとし、sがVに属するものを任意の頂点とします。次に、任意のエッジ（u、v）Eについて、

path（s、v）<= path（s、u）+1。

私の質問は、なぜ上記の式に<=が必要なのかということです。私は、「=は大丈夫です。なぜ<=が必要なのか、1つのシナリオを教えてもらえますか？」と教えました。

以下はBFSアルゴリズムです

リーマ2：

G =（V、E）を有向または無向のグラフとし、BFSが特定のソースからG上で実行されると仮定します。頂点sはVに属します。次に、終了時に、各頂点vがVに属する場合、値d [v ]BFSによって計算されたものはd[v]>= path（s、v）を満たします。

証拠：

頂点がキューQに配置される回数に帰納法を使用します。帰納法の仮説は、すべてのvのd [v]> = path（s、v）がVに属するというものです。

誘導の基礎は、sがBFSの8行目のQに配置された直後の状況です。

すべてのvのd[s]= 0 = path（s、s​​）およびd [v] = path（s、v）は、V-{s}に属するため、帰納的仮説がここに当てはまります。

私の質問は、「頂点がキューQに配置される回数に誘導を使用する」とはどういう意味ですか？そしてそれは帰納的仮説とどのように関連していますか？

ありがとう！