問題タブ [spanning-tree]

コ スパニング ツリーとは何かを知っている人はいますか。いくつかの良い答えがある場合は、例もあると本当に良いでしょう.

私はこれまでにこの論文を見つけました。時代遅れですか？より速く、より良い実装はありますか？

ちなみに、ウィキペディアによると、無向グラフにはn^n-2のスパニングツリーが存在する可能性があります。有向グラフにはスパニングツリーをいくつ含めることができますか？

スパニングツリーを見つけるためにC++でBFSアルゴリズムの実装を行っています。スパニングツリーの出力は事前に表示する必要がありますが、実装に疑問があります。正確にわからない場合にツリーを構築する方法多くの子供が各ノードを持っていますか？ツリー構造を再帰的に検討するツリーのデータ構造は次のように記述できます。

ただし、前述のようにこの実装が機能するとは思わないでください。

これは、ツリーを事前順序で返すための私の関数です。

また、ツリー構造を使用せずにノードの事前順序付けを行う方法はないかと思います。

宿題用に BFS アルゴリズムを実装しようとしています。BFS を使用したスパニング ツリー アルゴリズムを見つけました。これが私のソリューションコードです：

この入力の場合:

私のアルゴリズムは出力として[0 1 2 3 4 7 5 6 8 9]を生成します。次の図に示すように、レベルごとのノードを出力して BFS ツリーを表します。

ただし、正しい出力 (順序どおり) は[0 1 3 4 5 6 2 7 8 9]である必要があり、その結果、ツリーは順序どおりに走査されます。コードの解決策が必要です。ツリーを使用する必要がないため、つまり、ツリーを配列 BFS_tree に直接事前注文で格納できるため、コードを修正するにはどうすればよいですか? 私はこれで立ち往生しています。ここで同様の質問を読みましたが、効率対策のためにツリーを実装できず、許可されていません。どうすればこれを行うことができますか? 可能ですか?...英語ですみません。

グラフを作ってみましょう。エッジを削除すると、エッジの各頂点から1つずつ、2つの「車」が作成されます。これらの2台の車が出会うと停止します。問題は、各頂点を通過する車の数の合計が最小になるようにスパニングツリーを作成することです。

追加の難しさは、頂点からn台の車が通過する場合、コストはK ^ nであり、n*Kではないことです。

いくつかの考え。最短のコードレスサイクルを開始点として見つけることができましたが、それらのコードレスサイクルの位置、つまり、それらが互いに接触しているかどうかによって、メトリックが変化し、したがって最短サイクルが何であるかが変わります。

これは最小スパニングツリーの問題ではありません。各車は変数を表し、スパニングツリーは最適化問題を計算するための最も効率的な方法であるため、これを解決したいと思います。同じエッジから2台の車が出会って停止すると、最適化から1つの変数が削減されます。

編集：

プロセスはこのようなものです。グラフをスパニングツリーにするために、いくつかのエッジを削除します。削除された各エッジは、削除されたエッジの各頂点に1つずつ、2台の車を作成します。これらの車は互いに交わる必要があります。これらのツインカーのそれぞれのパスを修正します。次に、（削除したすべてのエッジから）各頂点を通過する車の数を確認します。頂点から通過する車の数がnの場合、コストはK ^ nです。ここで、Kは定数です。次に、すべてのコストを追加します。これは、最小化する必要があるグローバルコストです。

不明な点があれば教えてください。 https://mathoverflow.net/questions/86301/spanning-tree-that-minimizes-a-dynamic-metric

各ベクトルに負でないコストがあり、各頂点に負でない利益がある有向グラフが与えられた場合、利益が最大になるグラフのスパニング サブツリーをどのように見つけますか? コストを特定の予算に抑える必要があります。多項式時間の複雑さと理論上の近似係数の問題の近似アルゴリズムを探しています。

固定料金輸送問題 (FCTP) の優れた解決策を見つけるために、メタヒューリスティックを使用してコードを作成する作業を行っています。

私が抱えている問題は、基礎となる二部グラフのスパニング ツリーを見つけることに基づいて、開始ソリューションを生成することです。

同じ問題に対して手順を複数回実行し、異なる解決策を得ることができるように、ランダム スパニング ツリーにしたいと考えています。

私はこれを行うのにいくつかの困難を抱えています。私がこれまで行ってきたアプローチは、弧をランダムに並べ替えてから、このリストを繰り返し処理し、サイクルが作成されない場合はそれらを順番に基礎に置くことです。

アークを含めるとサイクルが作成されるかどうかを確認するための高速な方法を見つける必要があります。大きな問題が発生した場合、このアプローチにはかなりの時間がかかる可能性があるため、「ブルートフォース」はしたくありません。

アークAがランダムに置換された配列であるとすると、どのように選択手順を実行しますか?

私はこれに数時間取り組んできましたが、私が試したことは何もうまくいきませんでした。アプリケーションに関しては、ほとんどが無意味です...

2つのデータセンターにそれぞれ1つずつ、1組のスイッチを構成しています。サイト間には1対のリンクがあり、1つは専用のプライベートファイバーで、もう1つはバックアップの100Mbps接続です。立ち入る価値のない理由で、リンクを介して多数のVLANをプッシュする必要があり、STP（または同等のもの）を使用してパスの冗長性を管理し、スイッチングループとそれに関連するメルトダウンを回避する必要があります。

現在、ルートプライマリとセカンダリの両方のバックアップリンクに4096のパスコストを設定しています。これは正常に機能します。スイッチはファイバを選択し、ファイバがダウンするまでバックアップリンクをブロックします。また、関連するVLANのネット直径を2に設定しました。これにより、コンバージェンス時間が14秒（転送時間の2倍）に短縮されました。

RSTPを使用すると、約1秒で収束する可能性があることを読みました。これが当てはまる場合は、その方法を知りたいと思います。

これが私がこれまでに持っているものです（この構成は多かれ少なかれ両方のスイッチにミラーリングされています）：

この質問は、interviewstreet.com から見つけました。

マシンが再びシオンの王国を攻撃しました。Xions 王国には、N 個の都市と N-1 個の双方向道路があります。道路網は、都市の任意のペア間に固有の経路があるようなものです。

モーフィアスは、K マシーンが王国全体を破壊する計画を立てているというニュースを受け取りました。これらのマシンは当初、王国の K 個の異なる都市に住んでおり、いつでも攻撃を計画して開始できます。そのため、彼はネオにいくつかの道路を破壊してマシン間の接続を中断するように依頼しました。つまり、これらの道路を破壊した後は、2 つのマシン間にパスがあってはなりません。

攻撃は今からいつでも可能であるため、ネオはこのタスクをできるだけ早く実行する必要があります. 王国の各道路は破壊されるまでに一定の時間がかかり、一度に 1 つしか破壊できません。

マシン間の接続を切断するのに必要な最小時間を Neo に伝えるプログラムを作成する必要があります。

サンプル入力 入力の最初の行には、スペースで区切られた 2 つの整数 N と K が含まれます。都市には 0 から N-1 の番号が付けられます。次に、それぞれがスペースで区切られた 3 つの整数 xyz を含む N-1 行をたどります。これは、都市 x と都市 y を結ぶ双方向の道路があることを意味し、この道路を破壊するには z 単位の時間がかかります。次に、それぞれが整数を含む K 行をたどります。i 番目の整数は、i 番目の Machine が現在位置している都市の ID です。

出力形式 マシン間の接続を中断するのに必要な最小時間を 1 行で出力します。

サンプル入力

サンプル出力

説明 Neo と重み 5 の都市 2 と都市 4 を結ぶ道路、および重み 5 の都市 0 と都市 1 を結ぶ道路を破壊できます。一度に破壊できる道路は 1 本だけなので、合計で最小時間は 10 単位時間です。 . これらの道路を破壊した後、マシンはどのパスからでも他のマシンに到達できなくなります。

制約

誰かが解決策にアプローチする方法を教えてもらえますか?

私の質問：

G(V,E) を全結合グラフとします。ここで、V はノードの集合であり、E はリンクの集合です。スパニング ツリーが辞書順でソートされている場合、グラフ内のすべてのリンクをカバーするために必要なスパニング ツリーの最小数の上限 (最悪の場合) は?

例として、|V|=4、したがって |E|=6 の場合、G(V,E) には次の 16 個のスパニング ツリーが含まれます (辞書順)。リンクに異なるラベルを付けると、スパニング ツリーの順序が異なる場合があることに注意してください。

1 2 3

1 2 4

1 2 6

1 3 4

1 3 5

1 3 6

1 4 5

1 5 6

2 3 4

2 3 5

2 4 5

2 4 6

2 5 6

3 4 6

3 5 6

4 5 6

この場合、グラフ内のすべてのリンクをカバーするために必要なスパニング ツリーの最小数は、5 つのスパニング ツリー ({1 2 3}、{1 2 4}、{1 2 6}、{1 3 4}、{ 1 3 5})。したがって、すべてのリンクはこれら 5 つのスパニング ツリーに含まれます。

小さなグラフのスパニング ツリーの数を数えるのは簡単ですが、大きなサイズのグラフ (たとえば |V|>4) では問題があります。

グラフ内のすべてのリンクをカバーするスパニング ツリーの上限数を計算する式はありますか?

どうもありがとう