算法问题分类

Question

其中一个竞技场有很大的问题。我试着解决它5天。我不是要你帮我解决这个问题，因为我对算法很陌生，我想请你帮我分类这个类型的问题，有没有人解决过像这样的问题，什么类型的问题NP。请不要以为我要求你帮我解决这个问题，我的目的只是为了学习算法，这是对我来说足够困难的问题：

这个难题的目的是确定在哪里放置一组加油站，使它们离机场最近。机场利用大量的汽油为飞机加油，因此关闭加油站具有重要的战略意义。 输入规范--您的程序应该只使用一个命令行参数:输入文件(根据语言在argv、args、参数中传递)。输入文件的格式如下： 第一行包含一个整数:n表示机场数目，下面n行包含2个浮点值xi，表示ith机场的坐标，下一行包含要分析的案例数p (p总是小于5)，下面的p行都包含一个整数gi，表示所需加油站的数量。 输出规范:您的程序应该将结果输出到标准输出(printf、print、echo、write)：您的输出应该包含p行，每一行提供加油站的gj坐标xj，yj。你的解决方案分数将由解决方案的质量来衡量。解的质量用总距离来衡量，总距离D是每个机场到其最近的加油站的平方距离之和的平方根。总距离D越低，你的分数就越高。

Answer 1

该问题是典型的无监督k-均值分类问题.有关详细信息，请参见这里：聚类

要获得一个快速的提示(如果你想避免完全的破坏者)，k-意思是从为你的加油站随机选择地点开始。通过一次一次降低每个加油站的成本，改进了以后的每一次迭代求解。为了做到这一点，它移动了一个加油站，目的是最大限度地降低它目前为之提供燃料的机场的成本。

Answer 2

这似乎是设施选址问题的变体。寻找最优位置是NP-困难的，但许多近似方法可以用于在一定的保证距离内找到最优解。或者，可以使用软方法(如聚类)，就像在其他答案中提出的那样。

Answer 3

对于gi=1这个例子来说，这很容易--你只需计算重心/质量(从所有机场来看，你甚至可以用它们消耗的燃料量来计算每个机场的重量，所以它会使加油站更接近于消耗大量燃料的机场，但由于这不是必需的，你会给予所有相同的重量)。这将产生一个最优解(这也是一个很好的例子，非线性全局优化不一定意味着NP难)。

我的想法是将机场划分为gi集，然后应用于每一组重心/质量。这将被归类为一个集群问题(或者可能是一个分区，取决于您如何制定它)。(实际上，我会应用k均值聚类来解决这个问题)。(如果你想要一个完美的结果，但也许有人想出了另一个好的解决方案，这确实很难。)