动态规划加速算法和轮廓探测算法.pdf

《动态规划加速算法和轮廓探测算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、万方数据指导小组成员RudolfFleischer教授MordecaiGolin教授万方数据摘要在这篇论文中，我们详细地研究了动态规划加速领域和几何探测领域的一些算法设计问题。在图像处理，语音识别，网络路由选择以及其它数学，计算机，计算生物领域的很多问题都可以用递归公式表示出来，从而用动态规划的方法来解决。而当这些公式又具有一些特殊的性质时，例如凸性或凹性时，我们可以进一步降低这些算法的时间复杂度。而凸性或者凹性在很多实际的问题中也是普遍存在的。在论文的第一部分中，我们讨论了对以下递归式进行动态规划加速的算法：vii]_rai

2、n{D,+g(Li—Lr))u＼，＼●其中研的值I主tC[1]，c【2]，⋯，cp一1]的值所决定，厶是一个非递减函数，而夕是一个给定的“失效”函数。以上的动态规划公式由于在很多领域都有应用所以已经被广泛地研究过。在通常情况下，要计算C[n】的值需要O(n2)的时间复杂度，但是当夕为凸函数或凹函数，或是分段的rs／N函数时，很多论文都证明这个问题的时间复杂度可以降低D(no(n))，在某些情况下，甚至可以达到线性的时间复杂度。其中Q(他)也就是逆阿克曼函数(InverseAckernmanfunction)，是一个递增极其缓慢

3、的函数，但所有时间复杂度包含了这个函数的算法都非常复杂，以至于难以理解和实现。而在本文中，我们会介绍一个简单的，新的几何方法，使得我们算法的时间复杂度可以消去逆阿克曼函数这个参数。我们的算法主要是把动态规划的公式转化为几何学中求解下包络(10werenvelope)的问题，通过这种转换，不仅整个算法的时间复杂度可以降低至线性，而且相比之前的算法，尤其是59为凸函数的情况下，更简单且容易实现。此外我们把这一方法做了进一步扩展，使其可以应用到当函数夕由分段的凸函数或凹函数组成的情况下，假设函数g一共分成了后段，我们只需要O(nk)

4、的时间复杂度，之前这类问题的最好算法是Eppstein给出的O(nkol(n／k))的算法，且该算法只能应用在Lt=i情况下。万方数据动态规划加速算法和轮廓探测算法在本文的第二部分中我们提出了几何探测领域的一个新的问题一一轮廓探测(CameraProbe)问题：假设在一个半径为1的圆内放置了一个未知凸多边形，轮廓探测研究的问题就是至少需要在圆周上放置多少个探测仪器才能保证任意形状、任意放置的凸多边形可以被重构出来以及至多需要在圆周上放置多少个探测仪器就能保证任意形状、任意放置的凸多边形可以被重构出来。这个理论模型的提出是基于我

5、们参与的一个“863”项目，其中一个问题是要通过位置固定的探测仪器来重构出未知物体的位置、形状。几何探测正是研究这类问题的领域。几何探测最早mCole和Yap在1987年提出了手指探测的模型而引入了计算几何学中，之后各种几何探测，包括Greschak等人提出的超平面探测，Rao等人提出的侧影探测，Skiena等人提出的X-光线探测等被人们广泛研究。但这些模型都要求探测仪器的位置是不固定的，即下次探测的方向和仪器放置位置可以根据之前探测结果来决定。而我们的轮廓探测模型可以适用于探测仪器事先固定好的环境下。此外，不同于其它的几何探

6、测问题中所需要的探测次数一般都与物体的顶点数有关，在我们的轮廓探测中，所需要的探测仪器数量取决于未知凸多边形的最大内角值a。在二维通常情况下，即任意两个探测仪器的探测线都不重合时，我们证明了最优解需要f熹1个探侧仪器；否则在任意情况下，我们证明了至多需要『兰]个探测仪器就能够重构出圆内最大内角不超过Q的任意凸多边形。在三维情况下，当未知凸多面体位于一个球的内部，所有的探测仪器放置在球面上时，我们需要的探侧仪器的数量仅取决于未知凸多面体内的最大面面角的值。通过分析未知凸多面体的一个顶点被探测到的特性，以及结合Hardin等人的球

7、面覆盖理论，我们证明了对于最大面面角不超过＆的凸多面体，至多只需要(面1而30-丌)个探测仪器就可以重构出球内任意放置、任意形状的未知凸多面体。但是，在三维的情况下，以上的结论还有改进的空间，针对不同探测仪器个数带来的不同放置位置的特性，在最后一章节中，我们给出了4个以及6个探测仪器的最优放置情况下更好的上界。关键词：动态规划，凸函数，凹函数，失效函数，几何探测，轮廓探测中图分类号：TP309万方数据AbstractInthisthesis，westudiedthedynamicprogrammingspeedupsandca

8、meraprobeproblemsinboth2dand3dcases．Manyproblemsincludingimageprocessing，networkrouting，speechrecogn卜tionandothersintheareaofmathematics，c