私は解決するのに苦労している次の問題があります。
直線があり、その上に M 個の村のリストがあります。鉄道駅から村までの平均距離が最小になるように、これらの村に N 個の鉄道駅を割り当てる必要があります。例：
村: ------1--------------2--3---------4--5----------- -6---------7--- 3 つの鉄道駅があります。
動的計画法を使おうとしましたが、できませんでした。誰でもこの問題を解決する方法を提案できますか? （すべてのオプションを試す明白な方法を除いて）？
各村について、すべての鉄道駅ではなく、その村から特定の鉄道駅までの距離のみを気にしていると思います。したがって、各村に鉄道駅を配置できれば、たとえ村が何千マイルも離れていたとしても、「村から鉄道駅までの平均距離」はゼロになるため、ある村から別の鉄道駅までの距離は別の村は大きいでしょう。
すべて同じ鉄道駅を使用する必要がある村のグループがある場合、その鉄道駅の最適な位置は、村の列の中央の位置 (村の数が奇数の場合) または中央の 2 つの村の間のどこかです。行 (村の数が偶数の場合)。これは、鉄道駅が他の場所にある場合、中央値に向かって移動すると、グループ内の大多数の村までの距離が短くなり、少数派までの距離だけが長くなるためです。
したがって、この問題への簡単なアプローチは、M 個の村を N 個の隣接する村のグループに分割する方法を考え出すことです。各グループは、中央の村、またはグループ内の最も中心にある 2 つの村の間の任意の場所に配置された鉄道駅によってサービスを提供されます。
これは、村の列に沿って作業し、k 村を j グループに分割する最適な方法と、その最適な方法のコストを k 村で計算する動的計画問題です。これを行うには、i ごとに、最後の i 村からグループを作成するコストを確認し、最初の k - i 村から j-1 グループを作成するコストを追加します。
すべての村とすべての鉄道駅の間の平均距離を本当に意味する場合は、1 つの鉄道駅の位置が別の鉄道駅を配置するコストに影響しないため、一度に 1 つの鉄道駅を扱うことができることに注意してください。次に、中央分離帯に N 個の鉄道駅を重ねて建設するか、村の数が偶数の場合、中央の 2 つの村の間のストリップに沿って配置しますが、これはあまり意味がありません。