空间填充曲线的一些组合应用

# 空间填充曲线及其应用主页 来源：https://www2.isye.gatech.edu/~jjb/research/mow/mow.html ## 空间填充曲线的一些组合应用 空间填充曲线提示了一种点集启发式遍历路径 图1：旅行商问题的一种启发式解法是按谢尔宾斯基空间填充曲线的顺序访问各点。 空间填充曲线是从低维空间到高维空间的一种连续映射。著名的曲线之一是谢尔宾斯基曲线，它通过反复复制并缩小一个简单图案（图1中蜿蜒的路径）形成。 空间填充曲线的一个有用特性是：一旦进入某个区域，它往往会访问该区域内的所有点。因此，平面上距离很近的点在曲线上的出现顺序往往也相距较近。 这构成了我和L. Platzman发明的启发式方法的基础，用于生成n个给定位置的合理短路径（即所谓的旅行商问题解）：只需按空间填充曲线的顺序访问它们。例如，图中以红色标记的点的一条短路径由绿色线条表示，这些线条按点在空间填充曲线上出现的顺序连接它们。 空间填充曲线启发式（SFC）具有许多优点，前提是你愿意接受比最优解长约25%的解（对于随机点集，这是期望值）。这些优点包括： - SFC算法速度快：构建n个点的路径只需O(n log n)计算量，而添加或删除点以更新解只需O(log n)计算量。 - SFC启发式不需要点之间的显式距离，因此无需像大多数其他启发式方法那样计算或测量这些距离。 - 该算法可并行化。（相比之下，类似的最近邻算法显然不可并行化。） - 对于随机点，SFC路径中链接的长度期望较小且方差较小，因此路径中约1/k的站点贡献约1/k的行程时间。这意味着只需将SFC路线分成k段，即可轻松将SFC路径转换为k辆车的路径。 空间填充曲线启发式已被用于许多应用，包括： - 为亚特兰大富尔顿县的“送餐上门”项目构建路由系统，该项目每天为体弱或年老无法自行购物的数百人送餐。我们是在两个旋转式卡片文件上构建的。 - 为美国红十字会向亚特兰大都市区的医院配送血液的路线规划。 - 为“战略防御倡议”（俗称“星球大战”计划）中的天基激光器进行目标定位。该应用由TRW系统公司的科学家告知我们，他们是SDI的承包商，选择空间填充曲线启发式是因为它经过充分分析、可并行化，并且可以在能够发射到轨道的计算机上运行。 - 控制笔式绘图仪绘制地图。（M. Iri及其东京大学的同事展示了如何通过高效规划绘图笔路径来减少大型道路地图的绘制时间。他们给出的一个例子将绘制时间从十小时减少到半小时。） 随后，基于空间填充曲线进行路径规划的思想已融入ARC/Info地理信息系统、Baan Systems的CAPS物流工具包以及其他管理二维数据的商业系统中。 有关这些思想的总结（不含技术细节，但包含指向技术文献的指引）可在我的课堂笔记《基于空间填充曲线的路由系统》（https://www2.isye.gatech.edu/~jjb/research/mow/mow.pdf）[pdf格式，22页]中找到。随附有一张100x100网格点的谢尔宾斯基索引表（https://www2.isye.gatech.edu/~jjb/research/mow/mow-tbl.pdf）[pdf格式，22页]，你可以在一个下午内利用它搭建自己的路由系统。有关算法性能的技术细节以及相关引用，请参见与L. K. Platzman合著的《空间填充曲线与平面旅行商问题》，*Journal of the Association for Computing Machinery* **36**(4):719-737 (1989)。 德国15,112个城市问题的空间填充曲线解（https://www2.isye.gatech.edu/~jjb/research/mow/sfc-tour-of-german-cities.png） 图2：德国15,112个城市的TSP路径。该路径由谢尔宾斯基空间填充曲线在不到一秒内生成，长度比最短可能路径长约三分之一。 将这种轻量级启发式方法与重量级优化软件包（如D. Applegate、R. Bixby、V. Chvatal和W. Cook开发的软件包（http://www.math.princeton.edu/tsp/index.html））进行对比是很有趣的。他们的TSP软件包是数学优化技术的杰作，已被用于求解德国15,112个城市的旅行商问题。这是已生成可证明最优解的最大非平凡问题。Applegate等人描述了所用的计算资源：“计算在位于莱斯大学和普林斯顿大学的110个处理器网络上进行。按500 MHz的Compaq EV6 Alpha处理器换算，计算总耗时22.6年。最优路径长度为1,573,084（以TSPLIB单位计）；这相当于穿越德国约66,000公里的行程。” 相比之下，Paul Goldsman使用空间填充曲线启发式求解了同一实例。我们的解长约34%（图2）。以每天悠闲行驶600公里计算，总驾驶时间约为147天，而最优解为110天。但我们的计算在一台廉价笔记本电脑上花费了不到一秒。因此这里的权衡是：使用我们的启发式方法，你立即得到一条路线，但需要多行驶一个月的路程。或者，配置一个110个处理器的网络并花两个月时间计算最短路径——以节省一个月的驾驶时间。 一个不规则三角网，其中的三角形已排序形成一条路径（https://www2.isye.gatech.edu/~jjb/research/mow/continuously-indexed-triangulation.png） 图3：通过寻找三角形的哈密顿路径或回路，并用适当定向的空间填充曲线填充每个三角形，可以实现不规则三角网中所有点的连续索引。 Bill Nulty、Paul Goldsman和我在几个方向上扩展了这些想法： - J. Bartholdi和W. Nulty的“基于空间填充曲线的鲁棒多维搜索”，*第六届国际空间数据处理研讨会论文集*，苏格兰爱丁堡，1994年9月。 - J. Bartholdi和P. Goldsman的“地球层级剖分的连续索引”（https://www2.isye.gatech.edu/~jjb/research/mow/papers/hglobec.pdf）（2000年）。该文稍作修订后发表于*Int. J. Geographical Information Science* **15**(6):489-522 (2001)。 - J. Bartholdi和P. Goldsman的“希尔伯特空间填充曲线的顶点标记算法”（https://www2.isye.gatech.edu/~jjb/research/mow/papers/hilbert.pdf）（2000年）。该文稍作修订后发表于*Software – Practice and Experience* **31**:395-408 (2000)。 - J. Bartholdi和P. Goldsman的“不规则三角网的顶点-邻接对偶具有哈密顿圈”（https://www2.isye.gatech.edu/~jjb/research/mow/papers/2004_ORL_Bartholdi_Goldsman.pdf），*Operations Research Letters* **32**(2004)。Perouz Taslakian为其中的思想和算法制作了非常精美的图示（http://cgm.cs.mcgill.ca/~perouz/cs507/vertexdual/introduction.htm）。