我有下一个我很难解决的问题。
我有一条直线，上面有 M 个村庄的列表。我需要在这些村庄分配N个火车站，这样一个村庄到火车站的平均距离就会最小化。例子：
村庄：-----1-------------2--3----------4--5------------ -6----------7--- 我们有 3 个火车站。
尝试使用动态编程，但无法做到。任何人都可以提出解决这个问题的方法吗？（除了尝试所有选项的明显方式）？
问问题
632 次
1 回答
3
我假设，对于每个村庄，您只关心从该村庄到特定火车站的距离，而不是所有火车站。因此，如果您可以在每个村庄放置一个火车站，那么即使村庄相隔数千英里，“村庄到火车站的平均距离”也会为零，因此从一个村庄到另一个火车站的距离一个不同的村庄会很大。
如果您有一组必须使用同一个火车站的村庄，那么该火车站的最佳位置是村庄线的中间位置（如果村庄的数量是奇数）或中间两个村庄之间的任何位置线（如果村庄的数量是偶数）。这是因为如果火车站在其他任何地方，将其移向中线将缩短与该组中大多数村庄的距离，而只会增加与少数村庄的距离。
因此，解决这个问题的一个简单方法是计算出如何将 M 个村庄分成 N 个相邻的村庄组，每组由一个火车站提供服务，位于中间的村庄，或组中两个最中心村庄之间的任何地方。
这是一个动态规划问题，您沿着村庄线工作，在村庄 k 计算将这 k 个村庄分成 j 组的最佳方式，以及该最佳方式的成本。您可以通过检查每个 i 从最后 i 个村庄创建一个组的成本并加上从前 k - i 个村庄创建 j-1 个组的成本来做到这一点。
如果您真的是指每个村庄和每个火车站之间的平均距离，请注意您可以一次处理一个火车站，因为一个火车站的位置不会影响定位另一个火车站的成本。然后，如果有偶数个村庄，那么您会在中间建有 N 个火车站，或者沿着两个中央村庄之间的地带放置 - 这真的没有意义。
于 2013-01-17T05:27:46.503 回答