鸡汤算法

针对2007年国际数学建模(MCM)大赛A题而推导出来的一种算法。

问题是将一个地图划分成若干个选区，同时要满足划分简单且人口数大致相同（即公平）。

算法的产生受到鸡汤的启发，浮在鸡汤表面的油花，会按照一定的规律，进行相互吞并。将这一事实进行类比，如果我们将地图上的每个小城镇都视作一朵油花，那么通过将相邻的城镇进行一系列的合并，得到我们所希望得到的选区。进一步，面积较小的油花具有较大的边界张力，能够容易地顶入旁边较大的油花。那么，类似地，我们将人口总数较小的城镇看成面积较小的油花，即首先考虑将人口数较小的城镇进行合并成为选区。直到各个选区的人数之间的标准差控制在一定的范围，我们可以认为这些选区的人数达到了平衡，亦即在各选区人数的期望的某个小领域内波动。

在此思想方式的基础上，我们提出了最小单元（unit）与周边(round)的概念。这里unit指的是人口数目少于各选区人口期望的地理单位（如小镇），round是指与该unit接壤的一些unit所组成的集合。因此每一个unit都拥有一个round，若干个unit组成一个选区（district），这里不允许另一个district将一个已经在某个district中的unit加入其中。同时各个district也拥有一个round，且district的round是其中unit的round之并集（注意：这里的并集允许有重复元素，即有重集合）。算法的开始是将round中元素个数最少的unit先加入到district中，即这些unit是位于地图的边界甚至是半岛上的。这样就得到了个district的最初状态，然后寻找各district的round中人口数最少的unit，并将之加入到该district中。