問題タブ [spanning-tree]

スパニングツリープロトコルの実装中にスイッチのMACアドレスを取得するにはどうすればよいですか？

スパニングツリーアルゴリズムを使用せずに最小コストのブロードキャストルーティングスキームを取得できる方法はありますか？

これについて私を導くための参照は、私にとって非常に役立ちます。

無向連結グラフ G が与えられたとき、直径が最小の全域木を見つけます。

それぞれ黒または白のエッジと整数 k を持つ接続された無向グラフがあります。正確に k 個の黒いエッジを持つスパニング ツリーが存在するかどうかを示すアルゴリズムを作成しようとしています (必ずしも実際のツリーを見つける必要はありません)。

Kruskal のアルゴリズムを使用して、スパニング ツリーの黒エッジの最小数と最大数を見つけました。k がこの範囲外の場合、k 個のエッジを持つスパニング ツリーは存在できません。

しかし、その範囲内のすべての k に対して必ずしもスパニング ツリーが存在するかどうかについて、私は頭を悩ませています。私の直感はイエスと言っており、私が試したすべての例でうまくいきましたが、それを証明する方法がわかりません.

何かアドバイス？前もって感謝します。

私は分散システムの世界全体に不慣れです。この環境でクラスターを形成する方法と、どれが CH (クラスター ヘッダー) であるかを決定する方法について助けが必要です。スパニング ツリーを使用して、エネルギーが最も高いノードを CH に選択します。CH が選択されると、他のすべてのノードはその情報を CH に送信し、CH はそれを基地局 (赤いノード) に送信する必要があります。

問題は、アルゴリズムがどうあるべきか分からないことです。これが私がやろうとしたアルゴリズムです

クラスタリング アルゴリズム

• 1 時間ごとに、ノードはスパニング ツリーを開始して、最も多くのエネルギーを含むノードを見つけます。

• 「検索」メッセージを受信したノードの場合:

  -送信者からのエネルギーがそれ自体よりも低い場合、各ノードの残りのエネルギーを比較します。独自の ID で応答します。送信者からのエネルギーがそれ自体よりも高い場合。送信者 ID で応答し、それを他のネイバーに渡します

• ノードが独自の ID を受け取ると、それを自己クラスター ヘッダーにします。
• 他のノードがクラスター ヘッダーが選択されたことを認識したら、クラスター ヘッダーへの情報の送信を開始します。

環境：

これがルーターネットワークであると仮定します

数字は各ノードのエネルギーパワー

赤いノードは基地局です。

私は親と子だけのn-aryツリー構造を持っています。スパンツリー自体は、ルートという1つのノードのみを保持します。次に、他のノードまたはルートにリンクされたノードが作成されます。各ノード（ルートを含む）には、最大MAXCHILDRENの子ノードを含めることができます。構造は次のとおりです。

視覚的な画像：

ツリーを作成した後、すべての割り当てを解除したいのですが、どちらの方法で行うのかわかりません。ツリーが壊れてしまうため、ルートから割り当て解除を開始できません。だから私は葉から始めて根まで上がらなければならないと想像しますか？しかし、それは私が最初に最も深い葉を見つけなければならないことを意味しますね？どうやって始めたらいいのか、かなり戸惑いました。

必要だとは思いませんが、保険のために、新しいノードを作成する必要があるたびに使用するものを次に示します。

私はこれにかなり困惑しています。投稿するのは初めてなので、これがばかげた質問である場合はご容赦ください。

重み付けされたエッジを持つグラフ G=(V,E) が与えられたとします。ターゲット コストが c の G のスパニング ツリーを作成したいと考えています。ここで、スパニング ツリーのコストは、すべてのエッジ コストの合計として定義されます。コスト c の G の全域木が存在するかどうかを判断するにはどうすればよいでしょうか?

アンバランス ツリーを (バランスのとれた) スパニング ツリーに変換する方法は? ツリーがあるとします（異なるノードで異なる（必ずしも異なる）数の子を持つ）。k-aryスパニングツリーになるようにツリーを操作したい。

ツリーでのさまざまな反復が許可されます。制限は、すべてのノードを 1 か所に集めて、それらからスパニング ツリーを作成することはできないということです (これは簡単な方法です)。むしろ、指定されたツリーからスパニング ツリーを作成する必要があります。つまり、子は親 (および必要に応じて祖父母) と情報 (子ノードの数や子ノードの ID など) を交換でき、親は子の間でノードを移動することを決定します (順番に木のバランスをとります）。

並列コンピューティング環境でこれを行おうとしていることは理解できたかもしれません。ここで、ノードが知っているのは、その親、その子のID、およびその子をルートとする各サブツリー内のノードの数だけです。

(ツリーのバランスをとろうとすると、親と子が変わります)。この問題にアプローチする方法についてのヒントはありますか?

なぜこの問題が重要なのか、検討する価値があるのか​​というコメントに返信してください。

1. 理論的には、スパニング ツリーを構築するために (自明なアプローチで使用される) O(N) 未満のスペースを使用するアルゴリズムを開発することは困難です。

2. 大規模な代替ソリューション アプローチについて考えるのは興味深いことです。

3. 数値に関する限り、N=100,000 (これは今日のスーパーコンピューターでは一般的ですが、N は次の BG/Q では 1000,000 になります)。含まれる単純なアプローチの手順は、a) all-reduce、b) スパニング ツリーを構築するための O(N)、および c) 最後に 1 対多のブロードキャストです。

別の分散型アプローチではあまり改善されないかもしれませんが、好奇心から試してみる価値があるかもしれません。

私は Van Jacobson の講演を見てきました.Van Jacobsonは、IP がスパニング ツリー上でルーティングしようとしているとさりげなく主張しています。彼は続けて、ここでの欠点の 1 つは、アイドル リンクを表す接続グラフから一部のエッジを削除することになるため、容量が失われることだと述べています。

スパニング ツリーの概念と、スパニング ツリーにエッジを追加すると循環が生じることを知的に理解しています。ただし、各ノードで発生する/データのループにつながるルーティング状態のコンテキストで、これが IP で実際にどのように機能するかの例を見たいと思います。私の理解を明確にするために、誰かが小さな孤立した例を提供できますか?

最小スパニング ツリー (重み付きグラフの場合) を見つけ、グラフにハミルトニアン パスがあるかどうか (ハミルトニアン サイクルの存在に依存する) を見つけるためのアルゴリズムを調べていました。私はすべてを台無しにしました。では、ハミルトニアン パスとスパニング ツリーの違いは何でしょうか? どちらもグラフのすべての頂点をカバーしています。スパニング ツリー (おそらく最小スパニング ツリー) を見つけるための効率的なアルゴリズムを使用できますが、ハミルトニアン サーキットを見つけるためのアルゴリズムを使用できないのはなぜですか?? サイクルに到達するまで、一度に 1 つのエッジを追加および削除し続けることができます。おそらく、ハミルトニアン サイクルを見つけることができますか??