m*****g
发帖数: 226 | 1 应该是amzn的，不知是否有人还记得
placing m hospitals in n cities. n>m. the distance between cities minimum.
最近又在careercup上面看到，至今不解题意。
http://careercup.com/question?id=1816665 |
s********l
发帖数: 998 | 2 没进去careercup的link
看你的描述 我觉得应该用min spanning tree |
m*****g
发帖数: 226 | 3 讲一下题目吧
如果简单点，城市都在一直线上
那医院总该建在城市里面了吧。
这个mst是如何建立呢 |
b******v
发帖数: 1493 | 4 如果是两个城市，一个医院，那么应该建在两城市的中点吧
【在 m*****g 的大作中提到】
: 讲一下题目吧
: 如果简单点，城市都在一直线上
: 那医院总该建在城市里面了吧。
: 这个mst是如何建立呢
|
l***i
发帖数: 1309 | 5 damn, this looks like k-median, but k-median is NP-hard, and not even
approximable within a ratio of 2. |
b******v
发帖数: 1493 | 6 假设城市是P1, .., PN, 医院是X1, ..., XM
离城市Pi最近的医院距离是d_i = min{|Pi-Xj|, j=1,...,M}
感觉题目是求sum d_i或者max d_i的最小值
【在 m*****g 的大作中提到】
: 应该是amzn的，不知是否有人还记得
: placing m hospitals in n cities. n>m. the distance between cities minimum.
: 最近又在careercup上面看到，至今不解题意。
: http://careercup.com/question?id=1816665
|
m*****g
发帖数: 226 | 7 最直观是这么想
但是按照城市和医院来说，总不能把医院放到荒郊野外吧
所以后来我想是不是挑m个城市建医院这样，这样就看上去像个dp的
【在 b******v 的大作中提到】
: 假设城市是P1, .., PN, 医院是X1, ..., XM
: 离城市Pi最近的医院距离是d_i = min{|Pi-Xj|, j=1,...,M}
: 感觉题目是求sum d_i或者max d_i的最小值
|
s*********t
发帖数: 1663 | 8 是说所有城市到最近医院的距离之和最短？
【在 m*****g 的大作中提到】
: 应该是amzn的，不知是否有人还记得
: placing m hospitals in n cities. n>m. the distance between cities minimum.
: 最近又在careercup上面看到，至今不解题意。
: http://careercup.com/question?id=1816665
|
c*********n
发帖数: 1057 | 9 好象和一道DP题很象
【在 m*****g 的大作中提到】
: 应该是amzn的，不知是否有人还记得
: placing m hospitals in n cities. n>m. the distance between cities minimum.
: 最近又在careercup上面看到，至今不解题意。
: http://careercup.com/question?id=1816665
|
z*j
发帖数: 42 | 10 I am not very sure about this problem. Just some thoughts using voronoi
diagram in computation geometry. |
d****j
发帖数: 293 | 11 ....
很像machine learning中的k-means clustering or k-median clustering
虽然不一定是最优，但收敛很快啊 |
m*****g
发帖数: 226 | |
h**6
发帖数: 4160 | 13 如果是求城市到医院的最大距离最短，那么等同于用半径最小的m个圆去覆盖已知坐标
的n个点，其中m
设半径为r，则0
点。如果圆的个数x<=m，则减小r，x>m，则增大r，用二分法可以解决。
那么需要用多少个半径为r的圆才能覆盖这n个点呢？
以每一个点为圆心画一个半径为2r的圆，假设这个大圆覆盖了s个点，这s个点构成了一
个集合，对所有2^s个子集判断是否能被一个半径为r的圆覆盖，如果可以，把该子集加
入数组，取名为数组A。注意，如果数组A中有子集和超集，则只保留超集。
此时，得到了数组A，每一个元素都是某些点的集合，且互不为子集。然后构造一个长
度为2^n的数组，存储覆盖以位表示的点所需最少圆数。
然后用动态规划可以求出数组最后一项，即覆盖所有点所需要的圆数x，和m比较然后调
整r即可。 |
