其中一个算法竞赛网站存在很大问题.我试图解决它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越低,得分越高.
对于gi=1的情况。这很简单 - 你只需计算重心/质量（来自所有机场，哎呀，你甚至可以用每个机场消耗的燃料量来衡量它们，所以它会将加油站放置在靠近高消耗机场的地方，但因为这样不要求您给予所有相同的权重）。这将产生一个最优解（这也是一个很好的例子，非线性、全局优化不一定意味着 NP 困难）。
我的想法是将机场集划分为 gi 集，然后将重心/质量应用于每个集。这将被归类为聚类问题（或者可能是分区问题，取决于您如何表述它）。（实际上我会应用 k 均值聚类来解决这个问题）。（如果你想要完美的结果，这里确实会变得 NP 困难，但也许有人想出了另一个好的解决方案）