問題タブ [graph-theory]

Smalltalkでのグラフアルゴリズムの実装を知っている人はいますか？

モデルオブジェクトなどにインターフェイスを実装でき、推移閉包、推移簡約、トポロジカルソートなどのアルゴリズムを提供できるものが欲しいのですが。

人々はこれらの広く適用可能なアルゴリズムを頻繁に再実装することになります。誰もが使用できる一般的な実装が利用できるのは素晴らしいことです。

移植できる他の（できればOO）言語用の同様のライブラリへのポインタも役立つと思います。

私は誰かが簡単だと思ったプログラムを書くのを手伝おうとしていますが、もちろん決してそうではありません:)

クラスの名簿 (通常は 10 ～ 20 人の学生) を作成し、各クラスメートを効果的に一意にペアにして、一意のグループを作成しようとしています。したがって、10 人のクラスでは、9 つ​​のグループを持つことができます。

奇数の学生も処理できる必要があり、混乱を招きます。

Javaでこれを行うことを検討していましたが、それは柔軟です。a）無限ループではない（すでにパートナーになっている2人で終わる）、およびb）クラスサイズが小さいため、スペースよりも効率的な時間を目指しています！

ありがとう！

Microsoft GLEE (非営利目的) やグラフを描画するための他のライブラリを見てきましたが、インターネットを介した複雑なルートを表示するには、適切な商用目的のグラフ API が必要です。

多数のノードと頂点を表示できるようにする必要があります。何か案は？

ノードのクラスターをリンクするエッジを持つ重み付けされたノードの海があります。このグラフは、典型的なスモール ワールド レイアウトに従います。

ノードが最も有利に重み付けされ、最速のルートが最も重要な要素ではない、可能な限り最良のパスに沿ったパスを見つけるために、プロセッサの電力にコストがかからないパス検索アルゴリズムを見つけたいと思います。このアルゴリズムでは、ロード ベアリングとトラフィックの再ルーティングも考慮されます。

(補足: ここでニューラル ネットワークを使用できますか?)

ありがとう

私はACOを見ています。この種の問題に対して ACO より優れたものはありますか?

A*アルゴリズムは、ロードバランシングなしで、最小コストまたは最速のルートを見つけます。

最速または最短のルートが最も重要なルートではないとしましょう。より重要なのは、重み付けされたノードが特定の値を持つパスをたどることです。いいえ1。

no2. A* を使用すると、そのルートのトラフィックが過負荷になり、突然そのパスが冗長になります。A* と同じくらいクールですが、ACO に固有の負荷分散などの特定の機能はありません。

-- 私が間違ってA*を誤解していない限り

では、ACOに勝るものは何ですか？

本当に ACO と A* の対決のように見えます。A* について非常に多くの肯定的な話がありました。

まず、デビッドに応えて。バックグラウンドで ACO シミュレーションを実行し、最適なパスを見つけることができるので、初期のスタートアップ コストはかかりますが、幸運にもスタートアップは必須ではありません。そのため、シミュレーションを複数回実行する余裕があります。本当の問題の 1 つは、接続されたソース ノードと宛先ノードを見つけることです。A* はこれを非常に簡単に実行できるようです。このネットワークが何百万ものノードのように非常に大きくなるとどうなるでしょうか。A* は簡単にスケーリングできますか?

A*をさらに研究します。しかし、最後に質問をさせてください！

A* は Antnet (ACO) と同様にスケーリングできますか?

約100個のノードと約200個のエッジを持つ無向グラフがあります。1つのノードには「start」というラベルが付けられ、もう1つは「end」というラベルが付けられ、「mustpass」というラベルが付けられたノードが約12個あります。

'start'で始まり、'end'で終わり、すべての' mustpass'ノードを（任意の順序で）通過する、このグラフの最短経路を見つける必要があります。

（http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txtは問題のグラフであり、ペンシルバニア州ランカスターのトウモロコシの迷路を表しています）

178,000 個のノードと 500,000 個のエッジを持つ無向グラフをレンダリングするためのアドバイスが必要です。Neato、Tulip、Cytoscape を試しました。Neato は遠く離れたところまで来ていないし、Tulip と Cytoscape はそれを処理できると主張しているが、できないようだ. (Tulip は何もせず、Cytoscape は機能していると主張し、その後停止します。)

ノードのリモートで合理的なレイアウトを備えたベクター形式のファイル (ps または pdf) が欲しいだけです。

例えば、私がツリー構造を持っていたとしましょう。当然のことながらツリー コントロールを使用します。その GUI 要素は構造に完全にマップされるからです。

しかし、私が持っているのはグラフで、幅が広すぎて 1 つの Web ページに収まらない可能性があります。構造に本当に一致する GUI の例は思い浮かびません。私が持っているいくつかのアイデアのうち、うまく当てはまらないものは、Web 自体、ハイパーリンク、ブラウザの戻るボタン、および進むボタンです。ただし、これは一度に 1 つのノードを表示するだけです。できるだけ多くのノードを表示し、グラフの新しい領域に移動できるようにしたいと考えています。Google マップのようなものは、どの方向にも自由にスクロールできるという点で、良いモデルかもしれません。

何百万ものノードがあるグラフのドミネーター ツリーを計算するために、Lengauer および Tarjan アルゴリズムとパス圧縮を使用しています。アルゴリズムは非常に複雑であり、完全に理解するのに時間がかかっていないことを認めなければなりません。使用しているだけです。ここで、ルート ノードの直接の子のドミネーター ツリーを計算し、この操作を繰り返して特定の深さまでグラフを再帰する必要があります。つまり、ルート ノードの子のドミネーター ツリーを計算するときに、ルート ノードがグラフから削除されたふりをしたいのです。

私の質問は、ルート ノードの初期ドミネーター ツリーで既に計算されている即時ドミネーター情報を利用する効率的な解決策があるかどうかです。言い換えれば、プロセス全体が非常に時間がかかるため、子供たちのそれぞれについてゼロから始めたくありません。

単純に、グラフの奥深くには、idom が少し上にあり、グラフの上部の変更の影響を受けないノードがたくさんあるため、それは可能であると思われます。

ところで、ドミネーターツリーの主題がコンパイラーの人々によって「所有」されており、古典的なグラフ理論に関する本でそれについて言及されていないのは奇妙です。私が使用しているアプリケーション (私の FindRoots Java ヒープ アナライザー) は、コンパイラ理論とは関係ありません。

明確化: ここでは有向グラフについて話しています。私が参照する「ルート」は、実際には最大の到達可能性を持つノードです。「ツリー」への参照を「グラフ」に置き換えて、上記のテキストを更新しました。形が主に木のような。グラフは実際には Java ヒープ内のオブジェクトであり、ご想像のとおり、適度に階層化されています。OOM リーク分析を行う際にドミネーター ツリーが役立つことが分かりました。答えは最終的にそのドミネーターです。ドミネーター ツリーを使用すると、木ではなく木を<ahem>見ることができます。しかし、時にはたくさんのがらくたが木のてっぺんに浮かぶので、そのすぐ下に何千もの子を持つ根があります。このような場合、ルートの (元のグラフの) 直接の子のそれぞれにルートを持つドミネーター ツリーの計算を試してから、1 つ下のレベルに移動します。（当分の間、バックリンクの可能性について心配しないようにしています:)

有向グラフ内のサイクルを検出するための効率的なアルゴリズムはありますか?

実行する必要があるジョブのスケジュールを表す有向グラフがあります。ジョブはノードであり、依存関係はエッジです。循環依存関係につながるこのグラフ内の循環のエラー ケースを検出する必要があります。

毎年クリスマスに、家族のプレゼント交換のために名前を描きます。これには通常、誰も配偶者を引っ張らなくなるまで、複数回の再描画が含まれます。そこで今年、私は独自の名前描画アプリを作成しました。このアプリは、たくさんの名前と許可されていない組み合わせを取り込んで、選択した贈り先を全員にメールで送信します。

現在、アルゴリズムは次のように機能します (疑似コード):

グラフ理論について詳しく知っている人は、ここでうまく機能する何らかのアルゴリズムを知っていますか? 私の目的では、これは機能しますが、興味があります。

編集: 電子メールはしばらく前に送信されたので、何かを学びたいと思っているだけなので、これをグラフ理論の質問として言い換えます。除外がすべてペアである特殊なケースにはあまり興味がありません (配偶者が互いに得られない場合など)。私は、解決策を見つけるのが難しい部分になるほどの除外がある場合にもっと興味があります。上記の私のアルゴリズムは単純な貪欲なアルゴリズムであり、すべての場合に成功するかどうかはわかりません。

完全な有向グラフと頂点ペアのリストから始めます。頂点ペアごとに、最初の頂点から 2 番目の頂点へのエッジを削除します。

目標は、各頂点に 1 つのエッジが入り、1 つのエッジが出るグラフを取得することです。