3.3 望远镜、X射线、激光方向瞄准

虽然我们讨论TSP的应用时，一般考虑的情形都需要跨越遥远的空间距离，实际到达远方的地点，但是有些TSP题目产生的背景却不同，无需亲身上路，只是从远处观测目的地而已。通过某种望远镜观测行星、恒星和星系，就是一个很自然的例子。

为了观测，需要把望远镜设备旋转到合适的位置，这一操作称为快动（slew）。大型望远镜的快动由计算机驱动电机调节操控，整个过程复杂耗时。对于一组观测，有一条TSP路线可以让每次快动耗费时间之和达到最小，因此可以用来安排总计划。这道TSP里的城市也就是需要拍摄照片的观测对象，各地之间的旅行费用也就是望远镜在拍摄各个物体之间的快动过程所需的时间。

Shawn Carlson在《科学美国人》上发表了一篇文章，介绍了TSP的启发式解法如何帮他做计划，让一台望远镜每夜能拍摄大约200个星系，而这台机器年岁已久，经不起折腾。Carlson描述自己对TSP的好解法的需求时，这样写道：“这台望远镜在整个天空内大幅摆动时，它的40岁高龄的驱动系统就会虚脱崩溃，因此绝对需要尽可能少移动这位年老体衰的老伙计。”¹现代天文望远镜装置当然并不算年老体衰，不过要想高效使用这些极其昂贵的仪器，TSP的好解法确实是绝对需要的。

_{1. Carlson, S. 1997. Sci. Am. 276, 121–24.}

3.3.1 搜寻行星

美国宇航局在筹划空间望远镜的工作任务时，考虑到了一些有趣的TSP题目。美国喷气推进实验室的Martin Lu称之为另一种TSP——traveling planet-finder problem（旅行行星搜寻者问题），因为空间望远镜的一大目的就是作为“行星搜寻者”，在太阳系附近寻找环绕其他恒星旋转的类地行星。

与地面望远镜类似，空间望远镜的TSP也是为了确定观测的先后顺序。不过这次，观测顺序不能像地面上那样每晚临时确定，而必须在任务开始之前很久就作出决定，因为空间望远镜的快动需要耗费大量燃料，而且研究每颗恒星也需要花费大量时间。据Martin Lu预计，一项为时3年的任务大约可以对50颗恒星完成观测。

对一颗可能是类地行星的星体进行观测时，会遇到困难，因为它附近的恒星发出的强光会向镜头方向直射而来，导致拍摄这颗行星的任何照片都因过度曝光而呈现一片白色。一种推荐解决方案是配备一块大面积遮光板，安置在距离空间望远镜50 000至100 000千米处。普林斯顿大学的Robert Vanderbei介绍说，这就像在望远镜的眼前举起一只硕大的拇指挡住恒星的光一样。空间望远镜沿着固定轨道运行，遮光板则在不同的位置之间移动，从而实现观测。

在普林斯顿大学，Egemen Kolemen和Jeremy Kasdin对于依靠遮光板的空间望远镜进行了详细的研究。¹他们利用一系列优化模型，估计遮光板在各颗恒星之间移动时耗费的燃料量。当使用两块遮光板与一台望远镜共同工作时，他们解得的结果如图3-5所示。望远镜将按照顺序轮流观测各颗恒星，红线和绿线分别代表两块遮光板的移动路线。注意图上有些路线片段看起来像是分离的，但实际是相连的，只不过连线在球面背面，图上看不出来。美国宇航局的目标名单上总共有100颗备选恒星，这次测试解得的路线经过了其中的80颗。

_{1. Kolemen, E., N. J. Kasdin. 2007. Adv. Astronaut. Sci. 128, 215–133.}

图3-5　观测80颗恒星时两块遮光板的移动路线（E. Kolemen和N. J. Kasdin供图）

3.3.2 X射线晶体学

在另一个截然不同的领域里，也出现了类似地面望远镜问题的TSP研究。20世纪80年代中期，Robert Bland和David Shallcross与康奈尔大学的一个研究小组合作，在X射线晶体学实验中，利用TSP的模型来操控衍射仪的移动。¹计算机驱动电机需要移动晶体试样，还要重新让X射线瞄准试样，有时对每个晶体样品需要进行多达30 000次测量。电机完成这些定位步骤所需的时间就是这道TSP题目的旅行费用。Bland和Shallcross报告说，借助TSP方法，他们最多可以缩短总定位时间的46%。

_{1 Bland, R. G., D. F. Shallcross. 1989. Op. Res. Let. 8, 125–228.}

3.3.3 激光雕刻水晶工艺品

另一种方向瞄准类的TSP起源于制造业使用的脉冲激光。脉冲激光可以用来制作模型，或者在坚硬透明的水晶内部蚀刻图案，比如图3-6的pla85900摆件¹，作者为Precision Laser Art公司的Mark Dickens。从激光的这类用途中产生了一道不错的TSP题目。激光束射向水晶内部，焦点使水晶的特定部位发生细微的爆裂，产生许多极小的白点，因此可以透过清澈透明的水晶看到这些点。TSP的作用就是设计激光经过各点的顺序，使制作所需时间最短。

_{1. 这里的pla85900参见1.3节图1-7，就是之前提到的那道包含85 900座城市的芯片TSP题目。——译者注}

图3-6　激光在水晶内部雕刻的图案

把精美的美术作品临摹到水晶上时，为了得到高品质的图案，需要刻画的点非常多。为此，Dickens采纳了Concorde代码给出的启发式方法。如果TSP有光荣榜，这一应用必然榜上有名，因为它为TSP带来了若干工业实例，有些题目是有史以来规模最大的，包含的城市数甚至超过100万。