Function to calculate smallest set of zip codes in which all zip codes are within x miles
I need a function (in any language but preferably a script) that can take an array of objects (lets say zipcodes) with latitude/longitude coordinates and return the smallest subset in which all the elements of the origin开发者_如何学Cal array are within x (lets say 20) miles of at least 1 member of the subset.
Here is a greedy algorithm to get you started.
- Start with an empty result set R and let S be the set of all zipcodes.
- For each zipcode Zn in S, calculate the set Vn of zipcodes which are within 20 miles of Zn.
- Find the set Vmax with the most elements - Add the corresponding zipcode Zmax into the result set R, and remove all the elements of Vmax from S.
- With the remaining elements in S, repeat from step 2 until S is empty. Then the final set is R.
精彩评论