算法:在直线上的M个村庄分配N个火车站 [英] Algorithm : allocation of N railway stations in a M villages which are on a straight line

问题描述

下一个问题是我很难解决的.

I have the next problem I'm having a hard time solving.

我有一条直线，上面有M个村庄.我需要在这些村庄中分配N个火车站，以便使村庄到火车站的平均距离最小. 例如:

I have a straight line , and a list of M villages on it. I need to allocate the N railway stations in these villages, so that the average distance of a village from a railway station, will be minimized. example:

村庄:----- 1 -------------- 2--3 --------- 4--5 -------- ---- 6 ---------- 7 --- 我们有3个火车站.

villages: -----1--------------2--3---------4--5------------6----------7--- and we have 3 railway stations.

尝试使用动态编程，但不能这样做.谁能提出解决这个问题的方法? (除了尝试所有选项的明显方式之外)?

tried to use dynamic programming, but couldn't do it. can anyone suggest a way to solv this problem? (except the obvious way of trying all the options)?

推荐答案

我假设，对于每个村庄，您只关心从该村庄到特定火车站的距离，而不是所有火车站的距离.因此，如果您可以在每个村子里都建一个火车站，那么即使两个村子相距数千英里，从一个村子到火车站的平均距离"也将为零，因此从一个村子到另一个村子的距离是一个不同的村庄会很大.

I assume that, for each village, you care only about the distance from that village to a particular railway station, not all railway stations. So if you could put a railway station in each village the "average distance from a village to a railway station" would be zero, even if the villages were thousands of miles apart, so that the distance from one village to a different railway station in a different village would be large.

如果您有一组必须全部使用同一火车站的村庄，则该火车站的最佳位置是村庄线上的中间位置(如果村庄数为奇数)或中间位置一行中有两个村庄(如果村庄数为偶数).这是因为如果火车站在其他任何地方，将其移至中间位置将缩短到该组中大多数村庄的距离，而仅增加到少数村庄的距离.

If you have a group of villages which must all use the same railway station then the best position for that railway station is the median position on the line of the villages (if the number of villages is odd) or anywhere between the middle two villages in the line (if the number of villages is even). This is because if the railway station is anywhere else, moving it towards the median will shorten the distance to the majority of the villages in the group, while increasing the distance only to the minority.

因此，解决此问题的一种简单方法是弄清楚如何将M个村庄分为N个连续村庄，每个村庄由一个火车站提供服务，分别位于中间村庄或该村庄中两个最中心村庄之间的任何地方.组.

So an easy approach to this problem is to work out how to divide the M villages into N groups of contiguous villages, each served by a railway station, placed at the median village, or anywhere between the two most central villages in the group.

这是一个动态的编程问题，您在沿村庄的线工作，在k村庄进行计算，是将k个村庄分为j组的最佳方法，以及这种最佳方法的成本.为此，您可以检查每个i，从最后i个村庄创建一个小组的成本，然后加上从前k个i村庄创建j-1个小组的成本.

This is a dynamic programming problem where you work along the line of villages, computing at village k the best way to divide those k villages up into j groups, and the cost of that best way. You can do this by checking, for each i, of the cost of creating a group from the last i villages and adding on the cost of creating j-1 groups from the first k - i villages.

如果您真的是说每个村庄与每个火车站之间的平均距离，请注意，您一次只能处理一个火车站，因为一个火车站的位置不会影响另一个火车站的定位成本.然后，如果有偶数个村庄，则可以得到N个火车站，它们在中间位置彼此叠置，或者沿着长条放置在两个中心村庄之间的地带上-这实际上是没有意义的.

If you really mean the average distance between every village and every railway station then note you can just deal with the railway stations one at a time, because the position of one railway station does not affect the cost of positioning another railway station. Then you get N railway stations built on top of each other at the median, or placed along the strip between the two central villages, if there are an even number of villages - which doesn't really make sense.

这篇关于算法:在直线上的M个村庄分配N个火车站的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！