問題タブ [graph-algorithm]

私はプリムのアルゴリズムとその実装を知っていますが、いつも私が今聞きたい部分をスキップします。フィボナッチヒープを使用したプリムのアルゴリズムの実装は次のとおりであると書かれておりO(E + V log(V))、私の質問は次のとおりです。

• 簡単にフィボナッチヒープとは何ですか?
• それはどのように実装されていますか？と
• Prim のアルゴリズムをフィボナッチ ヒープでどのように実装できますか?

私のグラフは有向で非常に大きいです。グラフの頂点は町を表し、端は町から町へのバスの移動ルートを表します。目標は、ある頂点から別の頂点へのパスを見つけることです。アルゴリズムがバス間の転送時間を考慮に入れることは非常に重要です。

ダイクストラのアルゴリズムを使用しますが、グラフ全体から 1 つの方法を見つけます。頂点から頂点への「最良の」方法をいくつか見つける必要があります。「最高」とは、乗り換え時間が最短であることを意味しますが、これは最も重要なポイントではありません。

頂点の重みがW（V）の無向循環平面グラフG（V、E）、E（G）を埋め込んだ固定平面、および2つのノードsとtが与えられた場合、2つの連結成分に分割するGの分割を見つける必要があります。 S（G）とT（G）。sはS（G）にあり、tはT（G）にあります。頂点sとtは両方とも、埋め込みE（G）の外面に属します。

パーティションのバランスをうまく取りたいのですが、頂点の重みの合計がほぼ等しい必要があります。

良いアルゴリズムのアイデアはありますか？

私はグラフ検索アルゴリズムを研究しています (この質問のために、アルゴリズムを DFS、BreadthFS、ID のみに制限します)。

これらのアルゴリズムはすべて、前方検索 (開始ノードから終了ノードまで) または後方検索 (終了ノードから開始ノードまで) として実装できます。

私の質問は、後方検索が前方検索よりも優れたパフォーマンスを発揮するのはいつですか? そのための一般的なルールはありますか？

2 つのグラフを入力として受け取り、グラフ内の各ノードを比較するアルゴリズムの疑似コード (ラテックス) を作成しようとしています (比較関数を入力します)。しかし、それらが 1 つのグラフのノードである場合は 0 を返します。が他のグラフのノードと等しい場合、そうでない場合は 1 を返します。グラフのノードは別のグラフである可能性があります。したがって、チェックは再帰的です。

java awt.

問題は、ノードの位置が明示的に指定されていない場合、またはランダムに作成された場合、グラフが非常に乱雑になり、エッジが交差して頂点が衝突することです。

再配置のアルゴリズムを実装して、より均一でクリーンな方法でノードをより適切に分散したいと考えています。

誰かが私を助けることができますか？

これは、Vazirani による Algorithms book の問題です。

この問題への入力は、エッジに整数の重みを持つツリー T です。重みは、負、ゼロ、または正のいずれかです。T で最短の単純なパスを見つけるための線形時間アルゴリズムを与えます。パスの長さは、パス内のエッジの重みの合計です。頂点が繰り返されない場合、パスは単純です。パスの終点は制約されていないことに注意してください。

ヒント: これは、ツリー内で最大の独立集合を見つける問題と非常によく似ています。

この問題を線形時間で解決するにはどうすればよいですか?

これが私のアルゴリズムですが、深さ優先と何ら変わらないので、線形時間であるかどうか疑問に思っています:

1. トラバース ツリー (深さ優先)
2. インデックス (ノード) を保持する
3. 値を追加します
4. (1) ツリーの終わりまで行う
5. 合計を比較し、パスと合計を出力します

この問題はこのトピックに似ていますが、特定の答えはありません。

多くの状態間の伝達行列を導き出したアルゴリズムの問​​題があります。次のステップはそれを累乗することですが、非常に大きいので、いくらか削減する必要があります。具体的には、多くの対称性が含まれています。以下は、単純な観察によっていくつのノードを排除できるかの例です。

私の質問は、以下で手動で行った方法と同様に、有向グラフの対称性を効率的に排除するアルゴリズムがあるかどうかです。

いずれの場合も、初期ベクトルはすべてのノードで同じ値になります。

最初の例では、b、c、dおよびeすべてが および から値を受け取ることがわかりますa。したがって、それらは常に同じ値を含み、それらをマージできます。

aこの例では、グラフが、b、cおよびの観点から同一であることがすぐにわかりdます。また、それぞれのサイドノードについては、それがどの内部ノードに接続されているかは問題ではありません。したがって、グラフを 2 つの状態だけに減らすことができます。

更新:一部の人々は、「状態転送マトリックス」の意味がよくわからないほど合理的でした。nここでの考え方は、組み合わせ問題を、再帰ごとにいくつかの状態タイプに分割できるということです。n-1行列は からへの行き方を教えてくれますn。

通常は、状態の 1 つの値だけに関心がありますが、他の状態も計算する必要があるため、いつでも次のレベルに進むことができます。ただし、場合によっては、複数の状態が対称的です。つまり、常に同じ値になります。これらすべてを計算するのは明らかに無駄なので、すべてのノードが「一意」になるまでグラフを縮小します。

以下は、例 1 の縮小グラフの伝達行列の例です。

論文への提案や参照は大歓迎です。

私は次の関数を書き込もうとしています: すべてゼロでオブジェクトの外側の境界 (1 に等しい) を持つ行列を指定して、境界チェーン コードを生成したいと考えています。穴オブジェクトはマトリックス内になく、外側の境界だけです。

*例の図では、すべての行列セルは 0 ですが、青いセルは 1 です。

どんな助けでも大歓迎です！

A* アルゴリズムを考えてみましょう。

Google では、適切な疑似コードを見つけることができます。

よくわからないことが 1 つあります。次のような状況を考えてみてください。

A* はどのようにして a->b->c から a->d... に変更できますか? ??? つまり、A* はノードから開始し、ノード間を移動します。ある時点で、ノードには複数の隣接ノードがあり、A* は隣接ノードによって生成されたパスをたどることができますが、ある時点で切り替えることができます...そして、前のステップから始まるそのステップに戻ることができます放棄された道がその道を横切らなかったとしても...

コードでは、この環境を有効にする条件は何ですか?