概述
針對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中。