算法找到多少雷達塔可以在不干擾

Question

我想一個有趣的問題，而無法開機，並想知道如果任何人知道如何解決這個問題：

地球上有很多城市。鮑勃在每個城市建立了雷達塔。 每個城市都應該能夠播放當地的音樂。

不可饒恕的是，所有的雷達塔都會相互干擾，所以Bob 不得不將它們全部關閉。

幸運的鮑勃發明瞭他放在城市之間的盾牌（有些放置在地球核心附近，有些放置在城市邊界上）。

對於所述N個城市中，有N *（N-1）/ 2屏蔽。

遺憾的是，許多盾被毀壞。

您將得到對有他們之間沒有屏蔽的城市。

的任務是找到雷達塔，可以被打開，而不會造成任何干擾的最大數量。

到目前爲止，我已經試圖將其表示爲一個圖表（城市在它們之間沒有屏蔽的情況下是連通的），並且找到最大化最常見顏色數量的圖形着色。基本上我選擇一個起始節點，使它成爲紅色，然後所有周圍的節點變成藍色，然後變成紅色等等。我想知道是否有更快的方法。

Answer 1

這不是一個關於最大獨立集的問題，如http://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29#Finding_maximum_independent_sets？ （NP-complete，但指數時間算法更快，天真的蠻力搜索）

Answer 2

如果兩個雷達塔位於它們之間沒有屏蔽的供應對中，它們不能同時打開。通過找到一個樹的最長深度，其中一個節點指示一個雷達塔打開，您可以找到最大數量的塔，可以在沒有干擾的情況下打開最長深度的分支。一旦你拿到一個節點（即打開一個塔），你必須禁用所有其他沒有該塔防護的塔。