其中一个算法竞赛网站存在很大问题。我试图解决它 5 天。我不是要你帮我解决这个问题，因为我是算法的新手我想请你帮我对这类问题进行分类，有没有人解决过这样的问题，NP 问题的类型是什么。请不要以为我让你帮我解决这个问题，我的目的只是学习算法，这对我来说已经够难了:
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.
最佳答案
这个问题是典型的无监督 k-means 分类问题。有关详细信息，请参见此处:http://en.wikipedia.org/wiki/K-means_clustering
为了快速提示(如果您想避免完全剧透)，k-means 只需从为您的加油站选择随机位置开始。通过一次降低每个加油站的成本，此后每次迭代都会改进解决方案。它通过移动加油站来做到这一点，目标是最大限度地降低目前为其加油的一组机场的成本。
关于算法问题分类，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7333396/