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-complete，但指数时间算法比简单的蛮力搜索更快）

于 2012-05-01T04:47:40.753 回答
1

如果两个雷达塔在提供的对中且它们之间没有屏蔽，则它们不能同时打开。通过找到节点指示雷达塔已打开的树的最长深度，您可以通过采用具有最长深度的分支找到可以在不受干扰的情况下打开的塔的最大数量。一旦你采取了一个节点（即打开一个塔），你必须禁用所有其他没有与该塔盾的塔。

于 2012-05-01T04:14:14.867 回答