問題タブ [graph-theory]

プリムのアルゴリズムのウィキペディアのエントリを見ていましたが、隣接行列を使用した時間の複雑さが O(V^2) であり、ヒープと隣接リストを使用した時間の複雑さが O(E lg(V)) であることに気付きました。ここで、E はV はグラフの頂点の数です。

Prim のアルゴリズムはより密なグラフで使用されるため、E は V^2 に近づくことができますが、近づくと、ヒープの時間計算量は O(V^2 lg(V)) になり、O(V^2) よりも大きくなります。明らかに、ヒープは単に配列を検索するよりもパフォーマンスを向上させますが、時間の複雑さはそうではありません。

改善によってアルゴリズムの速度が実際にどのように低下​​するのでしょうか?

したがって、グラフ内の最長の単純なパスを見つける問題は NP 困難であることを理解しています。これは、エッジの重みを 1 に設定し、最長の単純なパスの長さがエッジ。

私の質問は次のとおりです。グラフを取得し、最大エッジ ウェイト を見つけ、各エッジ ウェイトをmに置き換え、標準の最短パス アルゴリズムを実行した場合、どのようなパスが得られますか? これは明らかに最長の単純なパスではありません。そうであれば、NP = P であり、そのようなものの証明はもう少し複雑な =P になると思います。wm - w

誰かが以下の種類の問題を解決するための幅優先探索を説明できますか

4 と 7 の間のすべてのパスを見つける必要があります

私はある種のソーシャル ネットワーク データを操作するアプリケーションを書いているので、理想的な基礎となるデータ構造は重み付き有向グラフです。最初にグラフ全体をメモリにロードしてからシリアル化せずに、データを直接操作 (および検索) したいと思います。

これは、標準の SQL データベースまたはキー/値ストアを使用してシミュレートできますが、非常に非効率的です (使用したいグラフ トラバーサル アルゴリズム、たとえば最短パスなど)。

グーグルが有用な結果をもたらさなかったので、私は自分自身を書くことに半分気になっていますが、車輪を再発明するよりも、既存のソリューションを使用したいと思っています（もしあれば、それを逃しました）。このプロジェクトは趣味/個人的な研究のためのものであるため、ソフトウェアはオープン ソースである必要があります (Linux で実行できることが望ましい)。

では、上記の説明に当てはまるプロジェクトはありますか?

ありがとう！

CFG (制御フロー グラフ)を描画できる (無料の) ライブラリを探しています。yFilesのようなものですが、無料またはできればオープンソースですか? 理想的には、このライブラリにより、ユーザーはグラフをナビゲート (および変更) できるようになります。つまり、グラフはアプリオリにレンダリングされた単なる静的なビットマップではありません。アイデア？

更新:上記の QuickGraph ライブラリと組み合わせた
グリーは、かなりうまく機能するようです。どうも

Update2:現在、 Graph#が最も強力なライブラリのようです。それを使用する方法に関する素晴らしいチュートリアルもあります。

ノードが接続される保証がないことを考慮して、宛先ノードに最も近くなるパスを見つけることができるグラフ検索アルゴリズムを作成（または既存の拡張）しようとしています。

これを現実的に適用するために、オンタリオ州ブランプトンからオンタリオ州ハミルトンに行く必要があるとしましょう。出発点で可能な選択肢は、ローカルトランジット、GOバス、またはウォーキングです。目的地に行くには徒歩が一番嫌いな方法だと知っているので、まずGOバスを見てみます。ハミルトンに近い地点までGOを利用できることはわかっていますが、その時点でGOバスが曲がり、その最も近い地点で別の方向に進むのは、選択肢がない場所です（歩く以外、アルゴリズムは歩くことだけを考慮します）短距離の場合、それ以外の場合はルートが実行不可能と見なされます）

この同じ例を使用して、アルゴリズムが、より長い方法でそこに到達できるが、より高い重み付けされたパスである宛先ノード（または宛先ノードで可能）に近づくことができることを検出した場合（重み付けは行われません）検索中は非常に重要ですが、結果が配信された場合にのみ、宛先に最も近いパスが昇順で一覧表示されます）。たとえば、1つのGOバスで目的地のノードから3 kmの距離になり、3つの公共交通機関のバスで500mの距離になります。

したがって、私の質問は2つあります。1）どのアルゴリズムから始めれば、同様のことができます。2）ノードが接続されていなくても、ノードAからノードRにジャンプしないように、プログラムで説明するにはどうすればよいでしょうか。最後から始めて、逆方向に作業することでこれを達成できますか

編集：特に大きなグラフでは、この問題の解決策が何百万もある可能性があるため、最良の近似解を目指す方法を尋ねるのを忘れました。

ありがとう、マイケル

グラフの関係を作成するための単純な Java API を見つけようとしています。addEdge()、addNode()、isConnected(node1, node2)、などの機能がfindPaths(node1, node2)必要です。UI は必要なく、ロジックだけが必要です。

アカデミックなプロジェクトをたくさん見つけましたが、どれも「The Definitive Graph API」のようには見えません。

そのようなAPIについて知っている人はいますか？

いくつかのタイルが壁で、他のタイルが歩きやすいタイルベースのマップがあります。歩きやすいタイルは、経路計画で使用したいグラフを構成します。私の質問は、グラフ内のすべてのノードを訪問し、繰り返しの訪問を最小限に抑えるパスを見つけるための優れたアルゴリズムはありますか?

例えば：

地図の例 http://img220.imageshack.us/img220/3488/mapq.png

一番下の黄色のタイルが開始点である場合、繰り返しが最も少ないすべてのタイルにアクセスするための最適なパスは次のとおりです。

パスの例 http://img222.imageshack.us/img222/7773/mapd.png

このパスには 2 回の再訪があります。悪い道は、最初のジャンクションで左折し、すでに訪れた 3 つのタイルを引き返すことです。

終了ノードは気にしませんが、開始ノードは重要です。

ありがとう。

編集：

質問に写真を追加しましたが、表示時にそれらを見ることができません。どうぞ：

http://img220.imageshack.us/img220/3488/mapq.png

http://img222.imageshack.us/img222/7773/mapd.png

さらに、グラフでは最小繰り返し数 = 0 という状況は決してないため、これが必要です。つまり、マップ内のすべてのタイルを踏むには、プレイヤーは自分のパスを少なくとも 1 回横断する必要があります。

メンバ std::list を持つクラス "Class" があります。そのリスト/ツリーで項目、具体的には特定の名前の項目を検索したいと考えています。私のクラスの基本的な表現は次のとおりです。

Class::findItem で次のようなことができます。

しかし、私がやりたいのは、findItem() が検索元に「最も近い」アイテムを返すことです。たとえば、これが私のツリーの場合、各文字はリスト階層の 1 つのレベルを表し、各数字はアイテムの「値」を表します。findItem(3) が C(3) ではなく B(3) を返すようにします。