Question

Location Allocation Problem（Facility Location Problem）

给定许多个地点，设立 p 个联络站，使得每一个地点皆可被其中一间联络站联络到，而且越有效率越好。

深入地定义“效率”的意义，得以细分许多问题：令联络站离各地点的距离总和最小（p-Median Problem）。令联络站离各地点的距离最大值最小（p-Center Problem）。在各地设立联络站需要成本，但建立联络站后会从周遭地点获得利益，令设立联络站后利益最大（Uncapacitated Facility Location Problem）。令各地点离联络站的中继点不超过一定数量（Range Assignment Problem）。

这些问题在现实生活中的应用，例如超商的物流通路、有线电视的缆线铺设、基地台的设立位置等等。可惜这些问题已经被证明是 NP-hard 问题，无法快速得到精准解答。

以下只讨论一维版本。所有的地点和连络站都在数线上。

p-Median Problem

p-Median Problem

给定许多个地点，设立 p 个联络站，使得每一个地点皆可被其中一间联络站联络到。令联络距离的总和最小。

此处讨论一维版本，地点和连络站落于数线上。

简化问题、观察问题：只有一个连络站

将联络站放在中位数是最好的。如果中位数是在两个位置中间的话，则联络站可以游移于两个位置之间、其上，都不会改变联络距离的总和。所有的联络站都可以挪至地点之上！

证明不难。试著移动联络站，让各个地点的联络距离此消彼长，观察一下就会明白了。动手试试看吧！

另外也得到一个重要的结论：所有的联络站都可以挪至地点之上，而不会改变联络距离的总和。

简化问题、观察问题：只有一个地点

将全部的联络站放在该地点上是最好的。

联络站全部叠在一起，有摩肩接踵、水洩不通的感觉，理当好好分配才对。说到分配，如果联络站数量大于等于地点数量，只要将联络站安排在各个地点上，联络距离的总和就是零了。

简化问题、观察问题：地缘

为了拉近联络距离，所有地点都会连向最近的联络站，而不会有捨近求远的情形。换个角度来看，一个联络站只会连向邻近的地点，而不会有捨近求远的情形。

p-Median Problem 可以重新想成：依照地缘，所有地点分配成 p 个区域，每一区自行设立一个联络站，位于中位数，可挪至邻近地点。

至此，p-Median Problem 就成了如何分区的问题。

简化问题、观察问题：分区

如果有地点选择联络站时捨近求远，表示这种分区方式不好。

各个区域之间相邻越远越好？大家自行观察看看吧。

动态规划

联络距离的总和，可以以区为单位，分别计算，最后再统计——这就是在分割问题。

拿掉最边边的一区、拿掉该区的联络站，如此便缩小了问题范畴，让小问题与原问题类似。接著穷举该区的各种大小，求得递迴式。

注意别让剩下来的地点太少、剩下的联络站太多，而导致连络站重叠。妥善分配重叠的联络站，一定能使联络距离的总和更小。没有必要枚举出让联络站重叠的分区方式。

f(p, n) = 
 { min( f(p-1, p-1) + d(p  , n) ,
 {      f(p-1, p  ) + d(p+1, n) ,
 {      ...                     ,
 {      f(p-1, n-2) + d(n-1, n) ,
 {      f(p-1, n-1) + d(n  , n) )  if p < n  && n >= 0
 {
 { 0                               if p >= n && n >= 0
 { +inf                            otherwise

p：已设立了 p 个联络站。
n：已涵盖了第 1 个到第 n 个地点。
f(p, n)：设立 p 个联络站，涵盖第 1 个到第 n 个地点时，其联络距离的总和。
d(i, j)：第 i 个地点到第 j 个地点所构成的区域，其联络距离的总和最小值。
         可利用中位数算得。

N 为地点个数，P 为联络站个数。总共 O(NP) 个子问题，计算一个子问题需时 O(N)，时间複杂度为 O(N^2 * P)。

p-Center Problem

p-Center Problem

给定许多个地点，设立 p 个联络站，使得每一个地点皆可被其中一间联络站联络到。令联络距离的最大值最小。

也可以想做是：各个联络站各自使用一个圆，以自己为圆心，向外扩张以包住其负责的地点，然后让最大的圆的半径越小越好。

p-Center Problem 的主要应用是设立基地台。基地台放送电波，地点距离越远，就需要越多能量、耗费越多电能；跟地点个数无关。为了节省电能，所以要适当的安排基地台的位置，缩短电波的放送距离。

此处依旧讨论一维版本。

简化问题、观察问题：只有一个连络站

联络站放在相离最远的两个地点的正中央是最好的。应该不用证明了吧？

其他性质皆与 p-Median Problem 类似，不再複述。

p-Center Problem 可以重新想成：依照地缘，所有地点分配成 p 个区域，找出最宽的区域，其宽度的一半，即是答案。

简化问题、观察问题：分区

p-Center Problem 只关心最宽的区域，其馀区域的宽度根本无所谓，不要超过最宽的区域就好了。

动态规划：Monotonicity

p-Center Problem 特性更强。分界线往右移动，一旦左方最宽的区域的宽度（的一半），大于等于右方区域的宽度（的一半），分界线就没有必要继续往右移动。往右移动只会让答案更大。

p-Median Problem 仅掌握分界线的起点。p-Center Problem 同时掌握起点与终点，时间複杂度为 O(NP)。

p-Coverage Problem

每个地点有半径、支出、收入。连络站建好后，涵盖范围为半径、涵盖到的地点有收入、没涵盖到的地点须支出，令总金额最高。