0

私は興味深い問題を考え、誰かがそれを解決する方法を知っているかどうか疑問に思いました：

地球上には多くの都市があります。ボブは各都市にレーダー塔を建設しました。各都市は地元の音楽を演奏できるはずでした。

許せないことに、すべてのレーダータワーが互いに干渉しているため、ボブはそれらをすべてオフにする必要がありました。

幸いなことに、ボブは都市の間に配置した盾を発明しました（地球の中心近くに配置されたものもあれば、都市の境界に配置されたものもあります）。

Nの都市には、N *（N-1）/2の盾があります。

残念ながら、多くの盾が破壊されました。

あなたはそれらの間に盾がない都市のペアを与えられます。

タスクは、干渉を引き起こさずにオンにできるレーダータワーの最大数を見つけることです。

これまで、これをグラフとして表現し（都市間にシールドがない場合は都市が接続されます）、最も一般的な色の数を最大化するグラフの色を見つけようとしました。基本的に、開始ノードを選択して赤にし、周囲のすべてのノードを青、次に赤などにします。もっと速い方法があるかどうか疑問に思いました。

4

2 に答える 2

2

これは、 http：//en.wikipedia.org/wiki/Independent_set_%28graph_theory%29#Finding_maximum_independent_setsのような最大独立集合に関する質問ではありませんか？（NP完全ですが、指数時間アルゴリズムを使用すると、素朴な力ずくの検索よりも高速になります）

于 2012-05-01T04:47:40.753 に答える
1

2つのレーダータワーが付属のペアにあり、間にシールドがない場合、2つのレーダータワーを同時にオンにすることはできません。ノードがレーダータワーがオンになっていることを示すツリーの最長の深さを見つけることにより、最も長い深さのブランチを取得することにより、干渉なしにオンにできるタワーの最大数を見つけることができます。ノードを取得したら（つまり、タワーをオンにすると）、そのタワーにシールドがない他のすべてのタワーを無効にする必要があります。

于 2012-05-01T04:14:14.867 に答える