整数位置が指定されたn 個のオブジェクトのセットがあります。オブジェクトのグループは、同じ位置にあるオブジェクトのセットです (必ずしもすべてのオブジェクトがその位置にあるとは限りません: 1 つの位置に複数のグループが存在する場合があります)。オブジェクトは左または右に移動できます。目標は、これらのオブジェクトを移動してk 個のグループを形成し、移動距離が最小になるようにすることです。
例えば：
私は貪欲なアプローチを使用しようとしてきました (どの移動が最短になるかを計算することによって) が、すべての移動にはどちらの方向にも移動できる 2 つの要素が含まれているため、うまくいきません。私はまだ動的プログラミングのアプローチを定式化できていませんが、それに取り組んでいます。
この問題は、次のように述べることができるk-medians 問題の 1 次元インスタンスです。ポイント x_1...x_n のセットを指定して、これらのポイントを k セット S_1...S_k に分割し、k 個の位置 y_1...y_k を選択して、|x_i - y_f(i)| のすべての x_i の合計を最小化します。ここで、y_f(i) は、x_i が割り当てられるセットに対応する位置です。
中央値は絶対距離 (つまり、L_1 ノルム)の母集団の最小値であるという事実により、各位置 y_j は、対応するセット S_j 内の要素 x の中央値になります (したがって、k-medians という名前が付けられます)。整数値を見ているので、S_j に偶数個の要素が含まれている場合、中央値は整数ではない可能性があるという技術がありますが、そのような場合、中央値の上または下の次の整数のいずれかを選択すると、同じ合計が得られます絶対距離。
k-medians (および関連するより一般的なk-means問題) を解決するための標準的なヒューリスティックは反復的ですが、これは最適な解決策または優れた解決策を生成することを保証するものではありません。一般メトリック空間の k 中央値問題を解くことは NP 困難であり、k 中央値の効率的な近似を見つけることは未解決の研究課題です。たとえば、「k-medians approximation」をグーグルで検索すると、近似スキームを示す一連の論文が表示されます。 http://www.cis.upenn.edu/~sudipto/mypapers/kmedian_jcss.pdf http://graphics.stanford.edu/courses/cs468-06-winter/Papers/arr-clustering.pdf
1 次元では物事がより簡単になり、動的計画法のアプローチを使用できます。関連する 1 次元の k-means 問題に対する DP ソリューションは、この論文で説明されており、R のソース コードはこちらで入手できます。詳細については論文を参照してください。ただし、アイデアは本質的に @SajalJain が提案したものと同じであり、k-means ではなく k-medians 問題を解決するために簡単に適用できます。j<=k および m<=n の場合、D(j,m) は、x_1...x_m に対する最適な j 中央値解のコストを示します。ここで、x_i はソートされた順序であると想定されます。再発があります
D(j,m) = min (D(j-1,q) + Cost(x_{q+1},...,x_m)
ここで、q の範囲は j-1 から m-1 でCost、中央値からの絶対距離の合計に等しくなります。の単純な O(n) 実装ではCost、これにより、問題全体に対する O(n^3k) DP ソリューションが得られます。ただし、並べ替えられたシーケンスの場合、次の事実を使用して、コストを毎回最初から計算するのではなく、一定の時間で更新できるため、これは O(n^2k) に改善できます。
Cost(x_1,...,x_h) = Cost(x_2,...,x_h) + median(x_1...x_h)-x_1 if h is odd
Cost(x_1,...,x_h) = Cost(x_2,...,x_h) + median(x_2...x_h)-x_1 if h is even
詳細については、書き込みを参照してください。Cost 関数の更新が異なるという事実を除いて、k-means と k-medians の実装は同じです。 http://journal.r-project.org/archive/2011-2/RJournal_2011-2_Wang+Song.pdf
私が理解しているように、問題は次のとおりです。
直線上に n 個の点があります。ライン上に k 位置を配置します。私はそれらを目的地と呼んでいます。距離の合計が最小になるように、n 個の点のそれぞれを k 個の目的地の 1 つに移動します。私はこれを総費用と呼んでいます。宛先は重複できます。
明らかな事実は、各ポイントについて、左側で最も近い目的地を探し、右側で最も近い目的地を探して、最も近い目的地を選択する必要があるということです。
もう 1 つの重要な事実は、すべての目的地がポイント上になければならないということです。合計距離を増やさずにポイントに到達するために、ライン上でそれらを右または左に移動できるためです。
これらの事実により、次の DP ソリューションを検討してください。
DP[i][j] は、j 個の目的地しか使用できず、i 番目のポイントに目的地を配置する必要がある場合に、最初の i ポイントに必要な最小総コストを意味します。
DP[i][j] を計算するには、i 番目のポイントの前に目的地を固定し (i の選択肢があります)、各選択肢 (たとえば、k 番目のポイント) について、i 番目のポイントとの間のポイントに必要な距離を計算します。追加された新しいポイント (k 番目のポイント)。これに DP[k][j - 1] を追加し、すべての k の最小値を見つけます。
初期状態の計算 (例: j = 1) と最終的な答えは演習として残します!