算法问题分类

Question

在一个算法竞赛网站上有一个大问题，我试图解决了五天。我不是要求你替我解决问题，因为我对算法很新，我想请你帮我分类这种类型的问题，是否有人解决过这样的问题，这是 NP 问题还是非 NP 问题。请不要认为我让你替我解决这个问题，我的目的只是学习算法，而这个问题对我来说足够困难：

这个谜题的目标是确定在哪里放置一组加油站，以便它们最靠近机场。机场使用大量的燃料来给飞机加油，因此将加油站放置在机场附近具有战略重要性。

输入规范：您的程序应该只需要一个命令行参数：输入文件(通过语言的 argv、args、arguments 传递)。输入文件格式如下：

第一行包含一个整数：n 表示机场数 接下来的 n 行每行包含两个浮点数 xi yi 表示第 i 个机场的坐标 下一行包含要分析的案例数 p(p 总是小于 5) 以下 p 行每行包含一个整数 gi，表示所需加油站数量

输出规范：你的程序应该输出结果到标准输出(printf、print、echo、write)：你的输出应该包含 p 行，每行提供 gj 的坐标 xj,yj。你的方案得分将通过解决方案的质量来评估。解决方案的质量是通过总距离来衡量的，总距离 D 是每个机场到其最近加油站的平方距离之和的平方根。总距离 D 越低，您的得分就越高。

- user873286

---

机场数量最多为1000个，加油站数量为256个。 - user873286

这个问题不属于NP，因为它不是一个决策问题。然而，回答“是否存在至少与k一样好的解决方案”的问题可能是NP难的。 - templatetypedef

Answer 1

这个问题是典型的无监督k-means分类问题。详细信息请参见这里：http://en.wikipedia.org/wiki/K-means_clustering。

简单提示（如果你想避免完全剧透）：k-means首先随机选择加油站的位置，然后通过逐个减少每个单独加油站的成本来改善解决方案。它通过移动加油站的位置，以最小化其当前供应的所有机场的成本。

- Nate

Answer 2

这似乎是设施选址问题的一个变种。寻找最优位置是NP难问题，但可以应用许多近似方法在一定保证距离内找到解决方案。或者，可以使用聚类等软方法，如其他答案中所提出的。

- mitchus

Answer 3

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

我的想法是将机场集合分成gi组，然后对每组应用重心/质心。这将被归类为聚类问题（或者可能是分区问题，取决于你如何表述它）。 （实际上，我会应用k-means聚类来解决这个问题）。 （如果你想要完美的结果，这里确实变得NP难，但也许有人能想出另一个好的解决方案）。

- flolo