Algorithm Problem Classification
There is great problem in one of the algo contest sites. I am trying to solve it for 5 days. I am not asking you to solve me this for me, as I am new to algorithms I would like to ask you help me with classification of this type problem, did anyone solved problems like this, what is the type of problem NP or not. Please do not think that I asking you to solve this for me, my purpose is just to learn algorithms and this is the problem which is enough difficult for me:
The goal of this puzzle is to determine where to place a set of gas stations so that they are closest to airports. Airports make use of a lot of gas for fueling planes, so placing gas stations close them is of strategical importance.
Input Specification Your program should take one and only one command line argument: the input file (passed in argv, args, arguments depending on the language). The input file is formatted as follows:
the first line contains an integer: n the number of airports the n following lines each contain 2 floating point values xi yi representing the coordinates of the ith airport the following line contains the number p of cases to analyze (p is always less than 5) the following p lines each contain one integer gi giving the number of required gas stations
Output Specifications: You program should output the result to the standard output (printf, print, echo, write): Your output should contain p lines, each line providing the gj coordinates xj,yj of the gas stations. Your solution score will be measured by the quality of the solution. The quality of the solution is measured by the total distance, the total distance D is the square root of the sum of squared distances from each airport to its closest gas station. The lower the total distance D, the higher your score will be.
This problem is the canonical unsupervised k-means classification problem. See here for the full details: http://en.wikipedia.org/wiki/K-means_clustering
For a quick hint (if you want to avoid complete spoilers) k-means simply starts by picking random locations for your gas stations. It improves the solution each iteration thereafter by reducing the cost of each individual gas station one at a time. It does this by moving a gas station with the goal of minimizing its cost for the set of airports that it currently fuels.
This seems to a be variant of the Facility location problem. Finding the optimal locations is NP-hard, but many approximation methods can be applied to find solutions within a certain guaranteed distance of the optimum. Alternatively, soft methods like clustering can be used, as proposed in other answers.
For the case gi=1. It is easy - you would just computer the center of gravity/mass (from all airports, heck you could even weigth each airport with the amount of fuel they consume, so it would place the fuel station closer to heavy consuming airports, but as this is not required you would give all the same weight). This would yield an optimal solution (this is also a good example that Nonlinear, global optimization does NOT necessary imply NP hard).
My idea would be to partition the set of airports into gi sets, and afterwards apply to each set the center-of-gravity/mass. This would be classified as a clustering problem (or maybe a partition, depends how you formulate it). (Practically I would apply a k-means clustering to solve this). (Here it gets indeed NP hard if you want perfect result, but maybe someone come up with another good solution)
链接地址: http://www.djcxy.com/p/54758.html上一篇: 如何在没有Flash / Adobe的情况下在PHP网站上显示PDF
下一篇: 算法问题分类