問題タブ [prims-algorithm]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
c++ - STL プライオリティ キュー C++ での reduceKey の実装
Prim のアルゴリズムを実装しようとしています。そのためには、優先度キューの reduceKey メソッドが必要です (優先度キューのキー値を更新するため)。これを STL Priority Queue に実装できますか?
それが役立つ場合、これは私が従っているアルゴリズムです:
- グラフ G の各頂点 u に対して
- u のキーを INFINITY に設定
- u の親を NIL に設定する
- ソース頂点のキーを 0 に設定
- 上記のキーを使用して、グラフ内のすべての頂点を優先度キュー Q にキューに入れます。
- Q は空ではありません
- Q の最小キーで頂点 u をポップする
- u の各隣接頂点 v について
- (v がまだ Q にある) かつ (key(u) + weight-function(u, v) < key(v)) の場合
- u を v の親に設定する
- update v's key to equal key(u) + weight-function(u, v) // この部分で問題が発生します。これは、優先度キューに reduceKey を実装する方法がわからないためです
- (v がまだ Q にある) かつ (key(u) + weight-function(u, v) < key(v)) の場合
c++ - C++、リストから値を取得すると、内部の配列が何も返されません
私のアルゴリズム クラスのプロジェクトでは、ディズニーランド マップのすべてのポイントを .txt ファイルから読み取り、プリム アルゴリズムを使用して MST 問題を解決するとします。
私の問題は、ファイルの値を ' ' 区切り文字を使用して一時配列に解析し、それらをリストにプッシュすることです。配列をリストにプッシュするまで、すべてがうまく機能しており、プログラムの後半で値を受け取ったときに値が返されません。私はそれがばかげていることを知っていますが、うまくいけば皆さんが助けてくれます.
私のコード: http://pastebin.com/rS6VJ6iJ
ディズニーランド.txt: http://pastebin.com/f78D0qrF
これがばかげていることはわかっていますが、現時点では理解できません。
編集:
プログラムがファイルの最後に空白行を読み込んでいるため、今はおかしくなっています。 ����TomorrowlandTerrace��� ��ӿ��� ��
エラーの原因となっているコードの更新された部分:
algorithm - エッジを含め、エッジを持つものの中で重みが最小のスパニング ツリーを生成する
エッジ e を含み、その重みがエッジ e を持つすべてのスパニング ツリーの中で最小になるように、グラフ G の最小スパニング ツリーを見つけたいと考えています。
algorithm - エッジの重みが 0 から 1 のプリムまたはクラスカルに一様に分布している場合
グラフ G の辺の重みが [0,1] に一様に分布しているとします。どちらのアルゴリズム プリムまたはクラスカルが高速になりますか? ソートはクラスカルアルゴリズムのボトルネックステップであるため、特定のソートアルゴリズムを利用できるため、クラスカルになると思います。
algorithm - 非平面グラフに最小全域木はありますか?
非平面グラフに最小全域木はありますか? プリム アルゴリズムと三角形の不等式について読みましたが、グラフが三角形の不等式を満たしていませんか?
algorithm - プリムのアルゴリズムのヒープ内の要素の優先順位を更新する方法は?
プリムのアルゴリズムを勉強しています。コード内に、カットを横切る次の頂点が に属する頂点のセットになる部分がありますMST
。それをしている間、「出発する頂点に隣接する他のセットのすべての頂点を更新する」必要もあります。これは からのスナップショットですCLRS
:
興味深い部分は行番号にあります。11. でも、ここではヒープを使っているので、最小限の要素しかアクセスできませんよね ( heap[0]
)? では、ヒープから頂点を検索して更新するにはどうすればよいでしょうか? 頂点が最小の頂点ではなく、線形検索を除いて頂点がどこにあるかを知っている場合でも、どうすればよいでしょうか?
algorithm - このアルゴリズムの複雑さを軽減できますか (NGenerics を使用しています)
NGenerics の Prim のアルゴリズムを使用して、いくつかの頂点を接続する最小スパニング ツリーを見つけています。これは、すべての頂点が他のすべての頂点に接続されているグラフで MST を検索するようなものです。つまり、頂点よりも多くのエッジがあり、(Kruskal ではなく) Prim のアルゴリズムを使用する必要があります。Prim のアルゴリズムは、適切に実装されている場合、O(|E| + |V| log |V|) 時間の計算量を持ちます。NGenerics はよく知られているライブラリであるため、Prim のアルゴリズムの最適な実装、または少なくとも O(|V|^2) よりも優れた実装が含まれている可能性があります。
ただし、問題があり
ます。NGenerics ライブラリを使用したい場合は、グラフのすべてのエッジを NGenerics グラフ データ構造に追加する必要があります。このようなもの (これは疑似コードです):
ただし、コードのその部分には明らかに O(|V|^2) 時間の複雑さがあり、アルゴリズムの実装が優れているライブラリを使用するという目的に反しています。定数も違いを生むので、そうではありませんが、私のアルゴリズムが O(|V|^2) になっていることにまだイライラしています。
とにかく、私はここで何かを見逃していますか?これを O(|E| + |V| log |V|) で動作させることはできますか?