最远优先遍历

在计算几何中，紧致度量空间的最远优先遍历（）是该空间中的一个点序列。首个点任意选取，此后每次都选取距已有点集最远的点。这个概念也适用于有限几何点集，即只需将候选点限定在该点集中。也可等价地将这些点视为一个有限度量空间。对于有限度量空间或有限几何点集，由此得到的序列是全部点的排列，又称贪心排列。

最远优先遍历的任一前缀都能得到一组彼此疏离、又接近其余各点的点集。更确切地说，任何规模相同的点集，其点间距至多为该点集的两倍。而其余点到点集的最远距离，也不可能缩短至该点集的一半以下。得益于这些性质，最远优先遍历用途广泛，可用于近似求解旅行推销员问题、问题等。它可在多项式时间内构造，此外在低维欧几里得空间中，还可用近线性时间求得近似结果。

定义与性质
最远优先遍历是紧致度量空间中的一个点序列，每个点至多出现一次。若空间有限，则每个点恰好出现一次，因此该序列是空间中全部点的一个排列。序列首项可任取空间中的一点，此后每个点都须与此前已选点集相距最远。点到集合的距离定义为该点与集合内各点两两距离的最小值。同一空间可能有多种最远优先遍历，具体取决于首个点的选择，以及后续选择中最大距离并列时的取舍。

最远优先遍历可由以下性质刻画。任取正整数，考察任一度量空间最远优先遍历前个点构成的前缀，并以表示该前缀末点到其余各点的距离。则这个子集具有以下两项性质：
*所有已选点两两相距至少
*度量空间中任一点到该子集的距离至多为
反之，任何序列若对所有都满足上述性质，就必为最远优先遍历。这两项正是的定义性质，因此最远优先遍历的每个前缀都是德劳内集。
应用
D·J·罗森克兰茨（）等人1977年的研究以最远优先遍历为基础，提出求解旅行推销员问题的最远插入启发式算法。该算法先在部分点上构造巡回路线，再按最远优先遍历的次序逐点插入。每次插入新点时，删去原路线的一条边，改用经过新点的两条边，并使路线增加的代价尽可能小。该研究人虽然只证明该算法具有对数近似比，但实验表明这一算法往往比其他理论近似比更优的插入算法表现更好。

后来T·F·冈萨雷斯（）1985年的研究推广了这一点序列，并将其用于两类聚类问题的贪心近似算法。这两类问题都要求将点集划分为个簇，其中一类旨在最小化最大簇直径，另一类称为问题，旨在最小化最大簇半径，即各簇中心到簇内最远点的距离。例如，中心问题可用于规划城市消防站的位置，确保消防车能迅速抵达市内各处。对于这两类问题，该研究都取最远优先遍历的前个点作为簇中心，再将每个输入点分配给最近的中心。设这个中心到遍历中第个点的距离为，则所得聚类中，每个点距所属中心至多为，每个簇的直径至多为。另一方面，这个中心连同第个点两两相距至少。任何划分为个簇的方案，都必将其中至少两个点归入同一簇，因此至少有一个点距簇中心不小于，该簇直径也不小于。由此该研究启发式算法对这两类聚类问题的近似比均为2。

戴尔（）弗里兹（）和在研究度量中心问题时重新发现冈萨雷斯启的发式算法，并将其推广至加权中心问题。同一时期，霍赫鲍姆（）和施莫伊斯（）也提出近似比为2的中心算法，但采用的方法不同。尽管如此，冈萨雷斯的启发式算法及“最远优先遍历”这一名称仍常被误归于霍赫鲍姆和施莫伊斯。对于极小化最大簇直径的聚类问题和度量中心问题，近似比为2已是最优结果。因为若存在近似比小于2的多项式时间算法，则可推出P=NP。

除聚类外，最远优先遍历还可用于另一类设施选址问题，即最大最小设施分散问题。该问题要求从给定度量空间或候选点集中选出个设施位置，使所选位置尽可能彼此远离；更确切地说，就是最大化所选点之间的最小两两距离。这一问题同样可取最远优先遍历的前个点作近似解。设第个点到此前各点的距离为，则度量空间或候选集中的每个点，到前个已选点中至少一点的距离不超过。根据鸽巢原理，无论最优解如何选取，其中必有两个点同时距前个已选点中的同一点不超过。再由三角不等式可知，这两个点之间的距离不超过。因此，最远优先遍历所得启发式解与最优解至多相差两倍。

最远优先遍历还可用于色彩量化（将图像颜色聚类为较少的一组代表色）、（安排点显示顺序，使序列任一前缀都能呈现整幅图像的低分辨率版本，而非从上到下逐行填充）、在的法中选点、简化、生成图像掩模、、计算相似曲面之间的相似度、为水下机器人勘探选择多样且价值较高的观测目标、的故障檢測、建立模型、将多车型车队车辆与客户配送请求匹配、在地球表面均匀布设观测站或其他传感器网络、在计算机图形学的实时辐射度法中生成虚拟点光源，以及构建几何的。

算法
贪心精确算法
有限点集的最远优先遍历可用求得。算法维护各点到已选点集的距离，并依次执行以下步骤：
*将已选点序列初始化为空序列，并将各点到已选点集的距离初始化为无穷大。
*在所有点均已选出前，反复执行以下步骤：
**扫描尚未选取的点，找出到已选点集中距离最大的点。
**将从未选点中移除，并添加到已选点序列末尾。
**对于每个仍未选取的点，将所存距离更新为原值与到距离两者中的较小值。
对于含个点的点集，该算法需执行步，并计算次距离。
近似算法
2006年，哈尔佩莱德（）和门德尔（）提出一种更快的近似算法，适用于倍增维数有界的度量空间中任意点子集，其中包括维数有界的欧几里得空间。该算法求得一个点序列，其中每个后继点到已选点集的距离，至少为当前最远距离的倍，且可取任意正数。算法的时间复杂度为O(n\log n)。

有界倍增维数下的结果并不适用于高维欧几里得空间，因为这些算法在大O符号中的常数因子取决于空间维数。另一种基于约翰逊-林登斯特劳斯定理和的近似算法，运行时间为O(\varepsilon^{-2} n^{1+1/(1+\varepsilon)^2+o(1)})。对于以加权无向图最短路径定义的度量，基于戴克斯特拉算法的可在O(\varepsilon^{-1} m\log n\log\tfrac{n}{\varepsilon})时间内完成，其中和分别为输入图的顶点数和边数。
增量式沃罗诺伊插入
若要从等连续空间中选点，而非从有限候选点集中选取，上述方法便无法直接应用，因为需要维护的距离有无穷多个。此时，每个新点都应选为已有点集所确定的圆心。该圆心必位于已有点集的某个顶点，或沃罗诺伊图边与区域边界的交点。以这种方式构造最远优先遍历的方法又称“增量式沃罗诺伊插入”。它与生成的方法相似，但每一步选取哪个沃罗诺伊顶点插入有所不同。

参考文献