4

グラフの実装に必要な一般的な関数のほとんどを実装した後、いくつかの関数 (頂点の削除、頂点の検索、頂点の取得) には「最適な」実装がないことに気付きました。

グラフの実装にリンクされたリストを含む隣接リストを使用しています。必要な頂点が見つかるまで、次々と頂点を検索していました。私が言ったように、私は「最良の」実装を使用していないことに気付きました。10000 個の頂点を持つことができ、最後の頂点を検索する必要がありますが、その頂点には最初の頂点へのリンクが含まれている可能性があり、これにより作業が大幅に高速化されます。しかし、これはあくまでも仮説であり、実際に起こるかもしれないし、起こらないかもしれません。

では、検索ルックアップにはどのアルゴリズムをお勧めしますか? 私たちの教師は、主に幅優先と深さ優先について話しました (そして、Dikjstra のアルゴリズムですが、それはまったく別の主題です)。その2つのうち、どちらがおすすめですか?

両方を実装できれば完璧ですが、そのための時間がありません。第 1 フェーズの締め切りが近づいているので、どちらかを選択して実装する必要があります...

私の推測では、Depth-first を使用することであり、実装が容易であり、それらの動作方法を見ると、それが最善の策のようです。しかし、それは本当に入力に依存します。

しかし、あなたたちは何を提案しますか？

4

8 に答える 8

5

隣接リストがある場合、頂点を検索することは単にそのリストをトラバースすることを意味します。リストを並べ替えて、必要なルックアップ操作を減らすこともできます。

グラフ トラバーサル (DFS や BFS など) は、パフォーマンスの観点からこれを改善しません。

于 2010-03-18T16:53:01.170 に答える
2

グラフ内のノードの検索と削除は、グラフの問題ではなく「検索」の問題であるため、O(n) = 線形検索、BFS、DFS よりも優れたものにするために、検索用に最適化された別のデータ構造にノードを格納する必要があります。またはそれらを並べ替えます。これにより、検索操作と削除操作の O(log n) が得られます。候補データは、b ツリーやハッシュ テーブルのようなツリー構造です。自分でコーディングしたい場合は、通常は非常に優れたパフォーマンスを提供し、実装がかなり簡単なハッシュテーブルを使用します。

于 2010-03-18T22:09:54.667 に答える
1

BFSは通常、平均して高速になると思います。DFSとBFSの wiki ページを読んでください。

BFS の方が速いと言う理由は、開始ノードからの距離の順にノードに到達するという特性があるためです。そのため、グラフにNノードがあり、検索フォームを開始するノードである nodeNと node1を検索する場合、リンク先はNすぐに見つかります。ただし、これが発生する前に、DFS がグラフ全体を拡張する可能性があります。DFS は運が良ければ高速になりますが、BFS は検索するノードが開始ノードに近い場合に高速になります。要するに、どちらも入力に依存しますが、私は BFS を選択します。

また、DFS は再帰を使用せずにコーディングするのが難しく、BFS は反復アルゴリズムであるため、実際には少し高速になります。

ノードを正規化 (1 から 10 000 までの番号を付け、番号でアクセス) できる場合はExists[i] = true if node i is in the graph and false otherwise、O(1) ルックアップ時間を簡単に維持できます。それ以外の場合、正規化が不可能な場合、または正規化したくない場合は、ハッシュ テーブルの使用を検討してください。

于 2010-03-18T17:11:40.610 に答える
0

深さ優先アルゴリズムと幅優先アルゴリズムは、1 つのスタック (DFS)、もう 1 つのキュー (BFS) の使用、およびいくつかの必須メンバー変数を除いて、ほとんど同じです。それらの両方を実装するのに、それほど時間はかかりません。

さらに、頂点の隣接リストがある場合は、とにかく O(V) でルックアップします。他の 2 つの検索のいずれかを使用しても得られるものはほとんどありません。

于 2010-03-18T16:55:52.710 に答える
0

深さ優先検索が最適な理由

  1. メモリ使用量がはるかに少ない
  2. 実装が容易
于 2010-03-18T16:54:40.997 に答える
0

Konrad の投稿にコメントしたいのですが、まだコメントできないので...リストの単純な線形検索で DFS または BFS を実装しても、パフォーマンスに違いはありません。グラフ内の特定のノードの検索は、グラフの構造に依存しないため、グラフ アルゴリズムに限定する必要はありません。コーディング時間に関しては、線形検索が最良の選択です。グラフ アルゴリズムのスキルを磨きたい場合は、DFS または BFS のどちらか好きな方を実装してください。

于 2010-03-18T17:09:09.447 に答える
0

特定の頂点を検索し、それが見つかったときに終了する場合は、ベスト ファースト検索であるA*を使用することをお勧めします。

ソース頂点から処理中の現在の頂点までの距離を計算し、現在の頂点からターゲットまでの距離を「推測」するという考え方です。

ソースから始めて、距離 (0) と推測 (それが何であれ) を計算し、優先度が距離 + 推測である優先キューに追加します。各ステップで、最小の距離 + 推測値を持つ要素を削除し、隣接リスト内の各頂点について計算を行い、それらを優先キューに入れます。目的の頂点が見つかったら停止します。

ヒューリスティック (「推測」) が許容できる場合、つまり、常に過小評価である場合は、最初にターゲット頂点にアクセスしたときに、ターゲット頂点への最短パスを見つけることが保証されます。ヒューリスティックが許容できない場合は、最短パスを見つけるためにアルゴリズムを最後まで実行する必要があります (ただし、最短パスは気にしないように聞こえますが、パスは何でも構いません)。

幅優先検索よりも実装が難しいわけではありませんが (実際にはヒューリスティックを追加するだけです)、おそらくより高速な結果が得られます。唯一の難しい部分は、ヒューリスティックを理解することです。地理的な位置を表す頂点の場合、一般的なヒューリスティックは、"as-the-crow-flies" (直接距離) ヒューリスティックを使用することです。

于 2010-03-18T21:49:15.613 に答える
0

線形検索は、BFS や DFS よりも高速です。しかし、線形検索よりも高速なのは、ステップ コストがゼロに設定された A* です。ステップ コストがゼロの場合、A* はゴール ノードに最も近いノードのみを展開します。ステップ コストがゼロの場合、すべてのノードのパス コストはゼロであり、A* はパスが短いノードを優先しません。最短パスは必要ないので、それが必要です。

線形検索は O(n/2) 回の反復後に完了する可能性が高いため (各ノードが目標ノードになる可能性は等しい)、A* は線形検索よりも高速ですが、A* は目標ノードになる可能性が高いノードを優先します。 .

于 2019-05-15T21:59:20.180 に答える