アルゴリズムの問​​題分類

Question

アルゴコンテストサイトの1つに大きな問題があります。私は5日間それを解決しようとしています。私はあなたにこのタイプの問題の分類を手伝って欲しいと思っていますが、誰かがこのような問題を解決したのか、NPの問題のタイプか、そうではないのか、私のためにこれを解決するように頼んだとは思っていません。私の目的はアルゴリズムを学ぶことだけです。これは私にとっては難しい問題です。

このパズルの目的は、ガスのセットは空港に最も近いように ステーションになります。空港は航空機に燃料を供給するために多くのガスを使用するので、ガソリンスタンドを閉じることは戦略的に重要なのは です。

入力の指定プログラムは1つのコマンド を引数として取る必要があります：入力ファイル（言語に応じてargv、args、引き数 が渡されます）。次のように、入力ファイルはフォーマットされ：

最初の行は整数が含ま：N空港の数N 次の行各々はi番目の空港の座標を表す2つの浮動小数点値のXI YI を含む次の行 が含ま例数pは 必要なガソリンスタンド

出力仕様の数を与える1つの整数GIが含まれている各 次のp行（pは常に5未満である）を分析します あなたのプログラムはずの結果を出力 標準出力（printf、print、echo、write）：あなたの 出力はp行を含む必要があり、各行はガソリンスタンドのxj、yjの座標を提供します。ソリューションのスコアは、 のソリューションの品質によって測定されます。ソリューションの品質は、 の合計距離で測定されます。合計距離Dは、各空港から最も近いガソリンスタンドまでの平方根の平方根です。 の合計距離Dが小さいほど、得点は高くなります。

Answer 1

gi = 1の場合。それは簡単です - コンピュータの重心・質量（すべての空港から、あなたが消費する燃料の量で各空港の重量を測定することもできますので、燃料ステーションを重く消費する空港に近づけるでしょうが、同じ重量をすべて払う必要はありません）。これは最適解を生み出すでしょう（これはNonlinear、グローバルな最適化が必要でないことはNPを意味する良い例でもあります）。

私の考えは、空港のセットをgiセットに分割し、その後、それぞれのセットに重心/質量の重心を適用することです。これは、クラスター化の問題（またはパーティションを作成する方法によって異なります）に分類されます。 （実際には、これを解決するためにk-meansクラスタリングを適用します）。 （ここで完璧な結果が得られるのであれば、実際にはNPは難しくなりますが、誰かが別の良い解を考え出すかもしれません）

Answer 2

この問題は、標準的な教師なしのk平均分類問題です。 http://en.wikipedia.org/wiki/K-means_clustering

簡単なヒント（完全なスポイラーを避けたい場合）は、ガソリンスタンドのランダムな場所を選択するだけで簡単に始まります。各ガスステーションのコストを一度に1つずつ減らすことによって、それ以降、各繰り返しを改善します。これは、現在燃料を供給している空港のためのコストを最小限に抑えるという目的でガソリンスタンドを移動することによってこれを行います。

Answer 3

これはFacility location problemの変形であるようです。最適な場所を見つけることはNP困難ですが、最適な距離の保証された距離内で解決策を見つけるために、多くの近似方法を適用することができます。あるいは、他の回答で提案されているように、クラスタリングのようなソフトメソッドを使用することもできます。