国外巡天望远镜光纤定位方式
美国思隆巡天望远镜( Sloan Digital Survey-SDSS)：打孔 式光纤定位系统。每块焦面板上（Tile）根据星表数据预先打 有640个位置孔，观测时将光纤插入孔中，实现观测任务。
澳大利亚AAT望远镜(Anglo-Australian Telescope－ AAT)：磁扣式光纤定位系统。光纤固定在微小的磁扣 (Magnitude button)上,由机器人手臂将磁扣放置在需要观测 星像对应的钢制焦面板位置上，实现观测任务。
(1)选定待求的模型参数并建立起模型参数与观测数 据之间的理论关系。
(2)根据搜索问题的实际要求，选定适当的可接受标 准。
(3)在计算机中按给定的先验范围随机地生成模型。
(4)用观测数据和可接受的标准来检验生成的模 型．舍弃“失败者”，保留“成功者”。
(5)回到第(3)步，再随机地生成新的模型，又进行检 验。
在有碰撞的情况下算法是分两步来完成的 ：一 先用一种算法（friends－friends grouping algorithm） 来寻找无碰撞的星象集合，如右图所示，再调用前面 的网络算法对未发生碰撞的星象进行分配。
有时候某一类星象 更重要些我们更希望得到 它的光谱，这将使得情况 稍稍复杂些。在寻找无碰 撞星象时，应该使得这类 较高优先级的星象被选中， 然后再去考虑优先级低的 星象。
如果任意一个节点的距离标号正好等于残量网 络中从该节点到汇点（节点t）的所有有向路中弧数 最少的有向路所包含的弧数（当令所有弧的长度为1 时, 这就是从该节点到汇点的最短路路长， 因此我 们后面直接称为最短路路长），则称距离函数d关于 流x是精确的（exact），或称距离标号是精确的。
焦面板位置给定
焦面板位置给定
二利用剩余未分配的光 纤来解决焦面板重合区域内 的“碰撞”问题。
这里我们设计了另一个 网络流，只考虑焦面板重合 区内的星象进行再次分配以 解决“碰撞”问题。在两个 星象发生碰撞和三个星象发 生碰撞的情况下网络流的解 就是我们要求的解决碰撞后 的最优分配。
对于更复杂的情况这个方法并不能保证得到可 行的结果，此时我们随机选择一个解决方案，所幸 的是这样的星象只有不到1％。
3、数据处理
数据处理系统是对LAMOST的观测数据进行 处理与分析，得到被观测天体的物理信息，由此 可提供给天文学家进行科学研究。LAMOST的观 测数据是在每次观测后由三十个CCD上采集下来 的原始数据，数据量每天近10GB，每年达数个 TB。对这些数据按照一定的步骤和程序进行处理 后得到每个被观测天体的一维光谱图（即流量与 波长的关系），再对这些光谱进行分析和测量， 得到被观测天体的各种物理信息，如类型、红移、 视向速度、线强比、等值宽度等，从而可直接提 供给天文学家进行大样本天文学的科学研究。
即使这样仍然有得到不可行解的情况，只是很 少见。一组的一部分在重合区内一部分不在，保证 未发生“碰撞”的星象被分配；二组内一些星象被 多个焦面板所覆盖，另一些被较少的焦面板覆盖， 这时会有部分未发生“碰撞”的星象没有被分配光 纤，他们的概率是极小的 。
LAMOST是一台横卧于南北方向的中星仪式 反射施密特望远镜。如图所示，它由在北端的反 射施密特改正板MA、在南端的球面主镜MB和在 中间的焦面构成。球面主镜及焦面固定在地基上， 反射施密特改正板作为定天镜跟踪天体的运动， 望远镜在天体经过中天前后时进行观测。天体的 光经MA反射到MB，再经MB反射后成像在焦面 上。焦面上放置的光纤，将天体的光分别传输到 光谱仪的狭缝上，然后通过光谱仪后的CCD探测 器同时获得大量天体的光谱。
并行可控式定位系统的提出
并行可控式定位系统的模拟计算
解决的问题
1、观测完备性和光纤头利用率
与打孔式和磁扣式光纤定位相比，并行可控 式系统的观测完备性和利用率是使用者关心的问 题，实际计算结果如下：
完备率和利用率
两个有用的结论
1〉光纤头数目 观测星像的面密度〉=4
2〉重合区大小 考虑到机械干涉问题，当观测半径大于18毫米
(3)理解容易，因而容易编制程序。而且编制出 的程序结构清晰简单，占用内存单元较少，很容易 实现。
但是，传统蒙持卡洛搜索方法也有致命的弱点。 其局限性影响了它的广泛应用。
(1)任何一种传统蒙持卡洛搜索方法都不能保证搜 索的彻底性。在搜索过程中任何时候均可以停止按索 或继续搜索。谁也不能保证此时得到的结果已经“完 全”满意了。当然，这一局限性对于只欲求解的共性 而言相对来说要好一些，影响要小—些；而对于欲求 整体极值对应的所谓“最佳”解而言却是致命的、难 以解决的问题，必须另辟途径。
(6)反复不断地重复上述步骤，直至认为满足，可以 结法现实， 就在于它用随机抽样搜索代替了系统搜索。而能进 行这样的代替有一定的理论依据，即概率论中的大 数定理。
大数定理说明只要随机抽样的次数n相当多， 结果的算术平均值与数学期望接近，而随机事件的 频率在它的概率附近摆动。因此只要n足够大，可 以用随机抽样搜索代替系统搜索。若要对收敛的程 度进行研究，作出各种误差估计，则要用到中心极 限定理：
inner loop of the method is based on the push-relabel
algorithm for the maximum flow problem.)
一般的标号推进算法是用来解决最大流问题。
它的基本思想：在残量网络中，选择活跃节点, 并把一定的流量推进到它的邻居。
传统蒙特卡洛搜索方法的特点和局限
首先，传统蒙特卡洛搜索方法的特点可以总结为：
(1)受问题的条件限制影响小，适应能力强。无 论对于多么复杂的非线性搜索问题都可以用它们解 决。多参数联合搜索与单参数搜索方法相同，仅计 算工作量不同而已；非线性搜索与线性搜索均能解 决，特别是当数据与模型之间的理论关系非常复杂， 以至于无法用数学解析或其他方式表现出来时，用 其他搜索方法往往无从下手，仅用蒙特卡洛搜索方 法没有丝毫困难。因此，从某种意义上说，蒙特卡 洛搜索方法是一种十分普遍适用的方法。当用其他 搜索方法无法解决问题时，不妨试一试蒙特卡洛搜 索方法。
如果当前活跃点有多个邻居，那么首先推进到 哪个邻居呢?
由于算法最后的目的是尽可能将流推进到汇(节 点t)，因此算法总是首先寻求把流量推进到它的邻 居中距离节点t最近的节点.
距离标号表示节点与t的距离，因此算法总是将 流量沿着允许弧推进。
如果当前活跃点出发没有允许弧，则增加该节
点的距离标号，使得从当前活跃点出发至少含有一 条允许弧。
焦面板位置给定
我们首先来考虑第二个问题， 在无碰撞的情况下问题等价于如 右图所述的网络流问题。
从左面的source node流入网 络的一个有七个对象的流。我们 的目标是以尽可能小的费用使整 个流流过网络到达右边的sink node。
对象必须流经弧，从一个顶 点到另一顶点。每个弧有一个它 所能传递的最大容量。每一个弧 还有一个相关的费用，单个对象 通过这条弧所必须花费的成本。
时，光纤头的利用率增加不明显。
SDSS中为使得分配星象时效率较高，有一套 完整的算法来解决这个问题。
算法分为两步来实现：一确定观测效率最高 的焦面板分布，使得整个天区尽可能被覆盖，由 于整个天区内星象分配是不均匀的这个问题是一 个“NP-complete”问题；二在焦面板中心位置固 定的情况下分配目标星象给各个焦面板，使得尽 可能多的星象被观测，由于各个焦面板之间存在 覆盖区，这个问题并非无足轻重，但它是个多项 式问题。
(2)收敛速度与问题的维数(即搜索的模型参数个 数)无关。可以看出，在一定的置信水平下，蒙特卡 洛搜索方法的误差除与方差有关之外，只与试验次 数有关，而与模型空间的组成无关。无论模型参数 是几个，只要方差不变且试验次数n相同，则蒙特卡 洛搜索方法对模型空间搜索的程度就是相同的，即 误差不变。问题维数的变化只影响抽样时间的改变 以及演算时间的改变，不影响问题的误差。换言之， 要达到同一精度，搜索到同样程度，用蒙特卡洛搜 索方法需随机选取的点数n与问题的维数无关，计算 时间与维数成比例。因此，蒙特卡洛方法特别适宜 于大规模、多参数问题的搜索。
蒙特卡洛方法
在任何一个阶段使用随机(或伪随机)生成元的方 法，为纪念著名的赌城蒙特卡洛．被命名为蒙特卡洛 方法。蒙特卡洛方法可以解决许多难以解决的问题。
传统蒙特卡洛搜索方法又可以称为“尝试和误 差”方法。它是在计算机中按一定的先验信息给出 的先验限制随机地生成大量可供选择的模型，计算 其理论数据值；将这些理论数据与实际观测数据进 行比较，并对一些先验约束进行检验；若比较和检 验符合了某些可接受的标准，则模型被接受，否则 被“排斥”并“遗忘”。因此，传统蒙特卡洛搜索 方法的主要步骤为：
相应于5度视场，直径为1.75米的焦面上放置 4000根光纤。采用并行可控的光纤定位技术，可 在较短的时间里将光纤按星表位置精确定位，并 提供了光纤位置微调的可能。这将在光纤定位技 术上突破目前世界上同时定位640根光纤的技术。
USTC参与的部分工作
1、科学目标
2、观测控制
观测控制系统是根据LAMOST的巡天战略， 具体安排数千万个待观测天体的观测时间，使其 能分期分批地进行观测；同时在每夜的观测中根 据LAMOST观测程序一步步地实施各项观测步骤， 在每夜完成数次观测后，则将观测数据存储到原 始数据库中，并进行备份。该系统与LAMOST的 科学目标研究、巡天战略的制订密切相关，同时 与望远镜控制系统和焦面仪器控制系统以及数据 处理系统紧密相联 。
这个网络在每个tile上光纤数限制的基础上表示
了所有可能的光纤分配。找到最小费用方案也就是使
分配给tile的对象数达到最大。 SDSS中解决这个问题所使用的算法是变尺度标
号推进方法（Goldberg在1997年提出，the scaling push-relabel method），它可以在多项式时间内解决 这个问题。它是在传统的标号推进方法的基础上进行 了一些改进，从而改善了算法的运行时间而并未改变 最坏情况下的运行上界O（mlog（nC））。(The