私には座標のある場所がたくさんあります。何か問題が発生したときにそれらの場所を維持する人がいます。私は現場の人を配置する方法を探しています。そうすれば、彼らは大部分の現場に可能な限り近くなります。
アイデアは次のようなものです: 私は緯度と経度を持つ 3000 のサイトを持っています。利用可能な人数を選択し、その情報を使用して、それらを配布するための最適な座標を取得したいと考えています。
私は既存のツールを探しているわけではありませんが (存在する場合はそれを探すことができます)、このようなものから始める方法がわかりません (mysql、php、Gmaps で作業できます。私に役立ちます）。ありがとうございました
任意の数の人々を特定の場所に分散させる問題は、最適化問題です。より具体的には、クラスタリングの問題として解釈できます。JS で実装された優れたクラスタリングの例は、A Curious Animalブログにあります。
上記の例でわかるように、クラスタリングは隣接する場所のグループ化を意味します。言い換えれば、これは、所与の位置セットに対する位置グループ (クラスター) の最適な分布をもたらす計算です。クラスターが場所グループではなく人であると宣言すると、問題のステートメントが得られます。
人数はあなたの入力なので、k-means クラスタリング アルゴリズムをお勧めします (簡単な説明、利用可能なソフトウェア リスト @wikipedia )。
編集：
一般に、最適化アルゴリズムを使用する場合、2 つの注意点があります。
最初のポイントはアルゴリズムの知識が必要ですが、2 番目のポイントは試行錯誤の問題です。また、入力の柔軟な違いは、出力に大きな違いをもたらす可能性があります。
上記のリンクは、k-means アルゴリズムが「非球状クラスターではうまく機能しない」と述べています。
彼の反対から始める方が簡単です-球状星団は次のように定義されます:「より正確な数学的用語は凸状です。これは、2つのクラスターメンバー間に描画できる線がクラスターの境界内に留まることを大まかに意味します。」:
非球状星団 (非凸点集合) は次のようになります。
おそらくあなたの「薄い卵形のクラスター」は凸状ではありませんか？
別の重要な特徴 (上記のリンクにも記載されています) は、k-means が非決定論的アルゴリズムであることです。つまり、複数回実行すると、同じ入力に対して異なる出力が得られる可能性があります (おそらくそうなるでしょう)。
これは、アルゴリズムがクラスターの初期分割をランダムに行うために発生し、最終的な出力はその初期分割に非常に敏感です。使用する実装によっては、ここで変更する余地がある場合があります。
それでも満足のいく結果が得られない場合は、別のアルゴリズムを試すしかありません (場所が与えられているため)。商用製品で使用するQT クラスタリング アルゴリズムを提案します。これは、最小クラスター サイズと、しきい値距離 (クラスターの中心からのポイントの距離) を入力として受け取る決定論的クラスタリング アルゴリズムです。
ただし、このアプローチでは、アルゴリズム自体を変更する必要があります。アルゴリズムは通常、「最小のクラスター サイズを持つクラスターをこれ以上形成できない」場合に停止します。必要な数のクラスターに達したときに停止するようにアルゴリズムを変更する必要があります。クラスター サイズの最小値は 1 で問題ありませんが、距離のしきい値として別の値を試してみることをお勧めします。
これは、私が偶然見つけた C# のコード サンプルです。お役に立てば幸いです。