算法问题分类
其中一个竞赛网站存在很大问题。 我试图解决它5天。 我不是要求你为我解决这个问题，因为我是算法新手，我想请你帮我分类这个问题，有没有人解决过这样的问题，问题类型是NP还是不是。 请不要以为我要求你为我解决这个问题，我的目的只是为了学习算法，这是对我来说足够困难的问题：
这个难题的目标是确定在哪里放置一组加油站，以便它们离机场最近。 机场利用大量的天然气来加油，所以加油站关闭它们具有战略意义。
输入规范你的程序应该只有一个命令行参数：输入文件（根据语言，在argv，args，参数中传递）。 输入文件格式如下：
第一行包含一个整数：n机场的数量n个后续行每个包含2个浮点值xi yi表示第i个机场的坐标，以下行包含要分析的案例数p（p始终小于5）以下p行每个包含一个整数gi，给出所需加油站的数量
输出规格：你的程序应该输出结果到标准输出（printf，print，echo，write）：你的输出应该包含p行，每行提供加油站的gj坐标xj，yj。 您的解决方案分数将通过解决方案的质量来衡量。 解决方案的质量由总距离来衡量，总距离D是从每个机场到最近的加油站的平方和距离之和的平方根。 总距离D越低，得分越高。
这个问题是典型的无监督k均值分类问题。 请参阅此处了解详细信息：http://en.wikipedia.org/wiki/K-means_clustering
对于一个快速提示（如果你想避免完整的破坏者）k-means只是开始为你的加油站选择随机位置。 它通过逐个降低每个加油站的成本来改进每次迭代的解决方案。 它通过移动一个加油站来实现这一目标，目的是最大限度地降低其目前燃料所在机场的成本。
这似乎是设施位置问题的一个变种。 找到最佳位置是NP难度，但是可以应用许多近似方法来在最佳值的某个保证距离内找到解。 另外，像其他答案中提出的那样，可以使用像聚类这样的软方法。
对于情况gi = 1。 很容易 - 您只需计算重心/质量（从所有机场出发），甚至可以用每个机场消耗的燃油量来计算重心/质量，因此它可以将加油站靠近耗资较高的机场，但是因为这样不需要你会给所有相同的重量）。 这将产生一个最佳解决方案（这也是一个很好的例子，非线性，全局优化并不一定意味着NP很难）。
我的想法是将这组机场划分为gi组，然后再应用于每组重心/质量。 这将被归类为聚类问题（或者可能是分区，取决于你如何制定它）。 （实际上我会应用k-means聚类来解决这个问题）。 （如果你想得到完美的结果，这确实是NP难，但也许有人想出另一个好的解决方案）
链接地址: http://www.djcxy.com/p/54757.html上一篇: Algorithm Problem Classification
下一篇: Eclipse returns error for the code for which g++ doesn't