8

このプロジェクトの締め切りはすぐに迫っており、残っているものに対処する時間があまりありません。したがって、最良の（そしておそらくより複雑で時間のかかる）アルゴリズムを探す代わりに、グラフ構造にいくつかの操作を実装するための最も簡単なアルゴリズムを探しています。

私がする必要がある操作は次の通りです：

  • 距離Xを指定して、グラフネットワーク内のすべてのユーザーを一覧表示します
  • 距離Xと関係のタイプを指定して、グラフネットワーク内のすべてのユーザーを一覧表示します
  • 関係のタイプを指定して、グラフネットワーク上の2人のユーザー間の最短経路を計算します
  • グラフネットワーク上の2人のユーザー間の最大距離を計算します
  • グラフネットワーク上で最も離れた接続ユーザーを計算します

私のグラフの実装に関するいくつかのメモ：

  • エッジノードには2つのプロパティがあり、1つはタイプcharで、もう1つはですint。これらは、それぞれ関係のタイプと重みを表します。
  • グラフは、頂点とエッジの両方について、リンクリストを使用して実装されます。つまり、各頂点は次の頂点を指し、各頂点は別のリンクリストのヘッド、つまりその特定の頂点のエッジも指します。

私がしなければならないことについて私が知っていること：

  • 上で述べたように、これが最も簡単かどうかはわかりませんが、2人のユーザー間の最短経路については、ダイクストラアルゴリズムが人々によく推奨されているように思われるので、それを使用すると思います。
    • 私は検索と検索を行ってきましたが、このアルゴリズムを実装するのは難しいと感じています。このアルゴリズムを自分で実装できるように、チュートリアルやわかりやすいものを知っている人はいますか？可能であれば、Cソースコードの例を使用すると、非常に役立ちます。数学表記の例をたくさん見ますが、それは私をさらに混乱させます。
    • リンクの重みと関係タイプを表すためにグラフを隣接行列に「変換」すると役立つと思いますか？リンクリストの代わりに、そのアルゴリズムを実行する方が簡単でしょうか？必要に応じて、その変換を行う関数を簡単に実装できます。数ページ読んだ方が楽だと感じたので言っていますが、間違っているかもしれません。
  • 他の4つの操作、提案についてのアイデアはありませんか？
4

3 に答える 3

8

距離Xを指定して、グラフネットワーク内のすべてのユーザーを一覧表示します

X何からの距離？開始ノードから、またはそれらのX間の距離から？例を挙げていただけますか？これは、BF検索を実行したりダイクストラを実行したりするほど単純な場合とそうでない場合があります。

特定のノードから開始し、開始ノードまでの距離を持つすべてのノードを一覧表示する場合は、開始ノードからBFSXを実行するだけです。キューに新しいノードを挿入しようとしているときに、開始ノードから新しいノードを挿入するノードまでの距離+新しいノードを挿入するノードからのエッジの重み新しいノードは<=です。厳密に低い場合は、新しいノードを挿入し、等しい場合は、新しいノードを印刷します（エッジの重みとして0を使用できる場合にのみ挿入します）。X

距離Xと関係のタイプを指定して、グラフネットワーク内のすべてのユーザーを一覧表示します

上記を参照。リレーションのタイプをBFSに考慮してください。親のタイプが、キューに挿入しようとしているノードのタイプと異なる場合は、挿入しないでください。

関係のタイプを指定して、グラフネットワーク上の2人のユーザー間の最短経路を計算します

アルゴリズムは、いくつかの要因に依存します。

  • これを計算する必要がある頻度はどれくらいですか？
  • ノードはいくつありますか？

簡単にしたいので、最も簡単なのはロイフロイドとダイクストラです。

  • Roy-Floydの使用は、ノード数が3次であるため、非効率的です。これは、一度実行してからO（1）の各クエリに答える余裕がある場合にのみ使用してください。隣接行列をメモリに保持する余裕がある場合は、これを使用します。
  • ダイクストラ法は、単純にしたい場合はノード数が2次式ですが、2つのノード間の距離を計算するたびに実行する必要があります。ダイクストラを使用する場合は、隣接リストを使用してください。

Cの実装は次のとおりです。Roy-FloydおよびDijkstra_1、Dijkstra_2。あなたはグーグルでたくさん見つけることができます"<algorithm name> c implementation"。

編集：隣接行列と同様に、Roy-Floydは18000ノードの問題外です。構築に時間がかかりすぎ、メモリが多すぎます。最善の策は、クエリごとにダイクストラのアルゴリズムを使用することですが、できればヒープを使用してダイクストラを実装します。提供したリンクでは、ヒープを使用して最小値を見つけます。各クエリで従来のダイクストラを実行すると、非常に長い時間がかかる可能性があります。

もう1つのオプションは、各クエリでベルマンフォードアルゴリズムを使用することです。これにより、クエリごとのO(Nodes*Edges)実行時間が可能になります。ただし、ウィキペディアの指示どおりに実装しない場合、これは大幅に過大評価されます。代わりに、BFSで使用されているものと同様のキューを使用してください。ノードがソースからの距離を更新するたびに、そのノードをキューに挿入し直します。これは実際には非常に高速であり、負の重みでも機能します。従来のダイクストラは18000ノードで長い時間がかかる可能性があるため、これまたはヒープ付きのダイクストラのいずれかを使用することをお勧めします。

グラフネットワーク上の2人のユーザー間の最大距離を計算します

最も簡単な方法は、バックトラッキングを使用することです。すべての可能性を試し、見つかった最長のパスを維持します。これはNP完全であるため、多項式の解は存在しません。

18 000のノードがある場合、これは本当に悪いことです。非常に多くのノードで適度に高速に動作するアルゴリズム（単純またはその他）はわかりません。欲張りアルゴリズムを使用して近似することを検討してください。または、グラフに利用できる特定のプロパティがある場合もあります。たとえば、それはDAG（有向非巡回グラフ）ですか？

グラフネットワーク上で最も離れた接続ユーザーを計算します

グラフの直径を求めたいという意味です。これを行う最も簡単な方法は、各2つのノード間の距離を見つけることです（すべてのペアの最短経路-各2つのノード間でRoy-FloydまたはDijkstraを実行し、最大距離の2つを選択します）。

繰り返しますが、これをノードとエッジの数で高速に行うのは非常に困難です。グラフに悪用できる特別なプロパティがない限り、これらの最後の2つの質問はうまくいかないのではないかと思います。

リンクの重みと関係タイプを表すためにグラフを隣接行列に「変換」すると役立つと思いますか？リンクリストの代わりに、そのアルゴリズムを実行する方が簡単でしょうか？必要に応じて、その変換を行う関数を簡単に実装できます。数ページ読んだ方が楽だと感じたので言っていますが、間違っているかもしれません。

いいえ、アプリケーションがスーパーコンピューターを対象としない限り、隣接行列とRoy-Floydは非常に悪い考えです。

于 2010-04-15T17:09:37.227 に答える
5

これは、許容可能な実行時間であると想定しO(E log V)ています。オンラインで何かをしている場合、これはそうではない可能性があり、より強力な機械が必要になります。

  • 距離Xを指定して、グラフネットワーク内のすべてのユーザーを一覧表示します

ダイクストラのアルゴリズムは、これに1回だけ使用するのに適しています。結果を保存して、将来使用するために、すべての頂点を線形スキャンすることができます（さらに良いのは、並べ替えと二分探索）。

  • 距離Xと関係のタイプを指定して、グラフネットワーク内のすべてのユーザーを一覧表示します

上記とほぼ同じかもしれません-正しい関係にない場合、重みが無限大になる関数を使用してください。

  • 関係のタイプを指定して、グラフネットワーク上の2人のユーザー間の最短経路を計算します

上記と同じように、基本的に、2人のユーザーが一致するかどうかを早期に判断します。（または、「途中で会う」こともできます。ツリーにまたがる最短パスの両方で誰かを見つけた場合は、早期に終了できます）

  • グラフネットワーク上の2人のユーザー間の最大距離を計算します

最長パスはNP完全問題です。

  • グラフネットワーク上で最も離れた接続ユーザーを計算します

これはグラフの直径であり、MathWorldで読むことができます。

隣接リストと隣接行列の質問については、グラフがどれだけ密集しているかによって異なります。また、結果をキャッシュしたい場合は、マトリックスが最適な方法かもしれません。

于 2010-04-15T17:04:20.143 に答える
1

2つのノード間の最短経路を計算する最も簡単なアルゴリズムはFloyd-Warshallです。forループはトリプルネストされています。それでおしまい。

のALLペアの最短経路を計算するO(N^3)ため、必要以上の作業を行う可能性があり、N巨大な場合は時間がかかります。

于 2010-04-15T17:16:18.237 に答える