这是一个创建于 2456 天前的主题，其中的信息可能已经有所发展或是发生改变。
You are given a map of cities with roads connecting some of them, as well as the length of each road. You have to choose cities in which you will build schools, such that the distance from any city to the nearest city with a school is at most 10 miles, and so that the total number of schools is as small as possible.
题目要求用贪心找出一个解，并证明这个解并不是最优的。
第一反应是求 Minimal Spanning Tree，然后在 Tree 上任意取一个 Vertex，建一个学校，然后把这个节点可以覆盖的 Vertices 去掉，重复，直到没有未覆盖的 Vertex。但是想了以下觉得不对，然后又想是不是对每个 Vertex 作为起点做一次 Dijkstra shortest path，然后每做完一次，从起点建学校，逐步覆盖所有的，然后取所有情况下最优的。无论上述哪一种，都觉得有问题。顺便求教最优解应该怎么求。
题目要求用贪心找出一个解，并证明这个解并不是最优的。
第一反应是求 Minimal Spanning Tree，然后在 Tree 上任意取一个 Vertex，建一个学校，然后把这个节点可以覆盖的 Vertices 去掉，重复，直到没有未覆盖的 Vertex。但是想了以下觉得不对，然后又想是不是对每个 Vertex 作为起点做一次 Dijkstra shortest path，然后每做完一次，从起点建学校，逐步覆盖所有的，然后取所有情况下最优的。无论上述哪一种，都觉得有问题。顺便求教最优解应该怎么求。
 |
1
geelaw 2018-04-02 15:59:58 +08:00
考虑一个特殊情况：任意两个直接连接的城市的距离都是 10 miles。此时问题是 minimum dominating set 问题，这是一个 NP-Hard 的问题，因此目前你随便想一个多项式时间的算法都不是最优的。
一个 naïve 的算法是这样的：随便选一个点建立学校，然后删除所有已经被 cover 住的点。 |
Select Language