アルゴリズムは、誰もがそれを解決する方法を知っている場合、私は興味深い問題を考え干渉

Question

ずにオンにすることができると思っていたどのように多くのレーダー塔見つけるために：地球上の

は、多くの都市があります。ボブは各都市にレーダータワーを建てました。 各都市は地元の音楽を演奏できるはずだった。

容赦なく、すべてのレーダータワーが互いに干渉しているので、Bob はすべてオフにしなければなりませんでした。

彼は都市間に配置された幸いにもボブを発明した（一部は が地球の中心近くに配置され、いくつかは都市の境界に置かれていた）。

N都市では、N *（N-1）/ 2個のシールドがあります。

残念ながら、多くのシールドが破壊されました。

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

タスクは干渉を発生させることなくオンにすることができるレーダタワーの最大数を見つけることです。

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

Answer 1

これは、http://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29#Finding_maximum_independent_setsのような最大独立したセットについての質問ではありませんか？ （NP完結だが、素早く素早く指数関数的なアルゴリズムを使って素早く素早く探索できる）

Answer 2

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