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

【摘要】在这篇论文中,我们详细地研究了动态规划加速领域和几何探测领域的一些算法设计问题。在图像处理,语音识别,网络路由选择以及其它数学,计算机,计算生物领域的很多问题都可以用递归公式表示出来,从而用动态规划的方法来解决。而当这些公式又具有一些特殊的性质时,例如凸性或凹性时,我们可以进一步降低这些算法的时间复杂度。而凸性或者凹性在很多实际的问题中也是普遍存在的。在论文的第一部分中,我们讨论了对以下递归式进行动态规划加速的算法：其中Dr的值由C[1],C[2],…,C[r-1]的值所决定,Li是一个非递减函数,而g是一个给定的“失效”函数。以上的动态规划公式由于在很多领域都有应用所以已经被广泛地研究过。在通常情况下,要计算C[n]的值需要O(n2)的时间复杂度,但是当g为凸函数或凹函数,或是分段的凸／凹函数时,很多论文都证明这个问题的时间复杂度可以降低O(na(n)),在某些情况下,甚至可以达到线性的时间复杂度。其中α(n)也就是逆阿克曼函数(InverseAckernmanfunction),是一个递增极其缓慢的函数,但所有时间复杂度包含了这个函数的算法都非常复杂,以至于难以理解和实现。而在本文中,我们会介绍一个简单的,新的几何方法,使得我们算法的时间复杂度可以消去逆阿克曼函数这个参数。我们的算法主要是把动态规划的公式转化为几何学中求解下包络(lowerenvelope)的问题,通过这种转换,不仅整个算法的时间复杂度可以降低至线性,而且相比之前的算法,尤其是当g为凸函数的情况下,更简单且容易实现。此外我们把这一方法做了进一步扩展,使其可以应用到当函数g由分段的凸函数或凹函数组成的情况下,假设函数g一共分成了k段,我们只需要O(nk)的时间复杂度,之前这类问题的最好算法是Eppstein给出的O(nka(n/k))的算法,且该算法只能应用在Li=i情况下。在本文的第二部分中我们提出了几何探测领域的一个新的问题——轮廓探钡(CameraProbe)问题：假设在一个半径为1的圆内放置了一个未知凸多边形,轮廓探测研究的问题就是至少需要在圆周上放置多少个探测仪器才能保证任意形状、任意放置的凸多边形可以被重构出来以及至多需要在圆周上放置多少个探测仪器就能保证任意形状、任意放置的凸多边形可以被重构出来。这个理论模型的提出是基于我们参与的一个“863”项目,其中一个问题是要通过位置固定的探测仪器来重构出未知物体的位置、形状。几何探测正是研究这类问题的领域。几何探测最早由Cole和Yap在1987年提出了手指探测的模型而引入了计算几何学中,之后各种几何探测,包括Greschak等人提出的超平面探测,Rao等人提出的侧影探测,Skien等人提出的x-光线探测等被人们广泛研究。但这些模型都要求探测仪器的位置是不固定的,即下次探测的方向和仪器放置位置可以根据之前探测结果来决定。而我们的轮廓探测模型可以适用于探测仪器事先固定好的环境下。此外,不同于其它的几何探测问题中所需要的探测次数一般都与物体的顶点数有关,在我们的轮廓探测中,所需要的探测仪器数量取决于未知凸多边形的最大内角值α。在二维通常情况下,即任意两个探测仪器的探测线都不重合时,我们证明了最优解需要[3π/π-α]个探侧仪器；否则在任意情况下,我们证明了至多需要[4π/π-α]个探测仪器就能够重构出圆内最大内角不超过α的任意凸多边形。在三维情况下,当未知凸多面体位于一个球的内部,所有的探测仪器放置在球面上时,我们需要的探侧仪器的数量仅取决于未知凸多面体内的最大面面角的值。通过分析未知凸多面体的一个顶点被探测到的特性,以及结合Hardin等人的球面覆盖理论,我们证明了对于最大面面角不超过α的凸多面体,至多只需要(130-π/180·cosα/2)2个探测仪器就可以重构出球内任意放置、任意形状的未知凸多面体。但是,在三维的情况下,以上的结论还有改进的空间,针对不同探测仪器个数带来的不同放置位置的特性,在最后一章节中,我们给出了4个以及6个探测仪器的最优放置情况下更好的上界。
【作者】王怡慧；
【导师】RudolfFleischer；
【作者基本信息】复旦大学，计算机软件与理论，2012，博士
【关键词】动态规划；凸函数；凹函数；失效函数；几何探测；轮廓探测中图分；

【参考文献】
[1]张瑞菊.空间数据挖掘方法及其与GIS集成模式的应用研究[D].山东科技大学,2003.
[2]韩振峰.焦裕禄精神与社会主义核心价值观[J].中国高等教育,2014,09:4-7.
[3]张市芳.直觉模糊多属性群决策的VIKOR方法[J].西安工业大学学报,2015,03:182-185.
[4]郑晓宇.汽车CAN模块功能测试系统设计及其实时性研究[D].哈尔滨工业大学,电气工程,2013,硕士.
[5]塔娜.对产细菌素的粪肠球菌群体感应现象的研究[D].内蒙古农业大学,农产品加工及贮藏工程,2013,硕士.
[6]贺梦丽.疏水性全氟烷基磺酰亚胺固体酸的合成及催化应用[D].华中农业大学,应用化学,2014,硕士.
[7]刘元彬.Disc-FX系统经皮髓核钳夹、射频消融术与椎间盘内亚甲蓝注射术治疗椎间盘源性腰痛的对比研究[D].河北医科大学,外科学,2013,硕士.
[8]李泉.湖南省郴州地区农村小学体育教师生存现状调查分析[D].湖南师范大学,运动训练学（专业学位）,2014,硕士.
[9]张玮娜.2-12岁汉语儿童情绪词使用情况的研究[D].辽宁师范大学,基础心理学,2011,硕士.
[10]金子.湘西地域宗教文化图像研究[D].湖南大学,设计学,2014,硕士.
[11]邓允长.基于TMS320F2812单相逆变器的研究与设计[D].安徽大学,模式识别与智能系统,2013,硕士.
[12]唐秦崴.镀层纸纸病检测系统研究[D].浙江大学,控制理论与控制工程,2013,硕士.
[13]罗啸啸.恩格斯晚年关于资本主义新变化的思想研究[D].中南民族大学,马克思主义基本原理,2013,硕士.
[14]彭绿原.论文化消费时代小说的影像化[D].安徽大学,中国现当代文学,2014,硕士.
[15]黎华栋.超声波作用下铝合金表面钎料液滴的动态铺展及润湿行为研究[D].哈尔滨工业大学,材料加工工程,2013,硕士.
[16]王毅敏.我国房地产信贷风险评估的实证研究[D].郑州大学,企业管理,2013,硕士.
[17]隋竹银,韩宝航.石墨烯气凝胶的水蒸汽活化法制备高比表面积多孔碳材料[A].中国化学会.中国化学会第29届学术年会摘要集——第27分会：多孔功能材料[C].中国化学会:,2014:1.
[18]王贺林.叠前时间偏移技术在关家堡地区地震资料处理中的应用[J].石油地球物理勘探,2006,S1:1-6+142-143.
[19]李晓雪.我国制造业对外直接投资对其自主创新的影响[D].首都经济贸易大学,国际贸易学,2013,硕士.
[20]魏江,郑小勇.关系嵌入强度对企业技术创新绩效的影响机制研究——基于组织学习能力的中介性调节效应分析[J].浙江大学学报(人文社会科学版)预印本,2010,09:68-80.
[21]张晶.高温高速自润滑辅助陶瓷球轴承设计与分析[D].哈尔滨工业大学,机械设计及理论,2013,硕士.
[22]张元铮.中国公益广告设计现状分析[D].沈阳师范大学,美术学,2013,硕士.
[23]杨晓辉.基于EMF框架的数据模型转换引擎的研究与实现[D].西安电子科技大学,计算机软件与理论,2011,硕士.
[24]郭争利.包钢巴润公司并段（高台阶）爆破陡帮开采方案研究[D].内蒙古科技大学,采矿工程,2013,硕士.
[25]林建.多源组播网络的安全网络编码研究[D].南京邮电大学,信号与信息处理（专业学位）,2013,硕士.
[26]薛晓鸣.小学低年级学生学习习惯研究[D].辽宁师范大学,教育管理（专业学位）,2012,硕士.
[27]禄果.李煜词中“香意象”的美学探究[D].西南大学,美学,2013,硕士.
[28]李燕.悬索桥设计阶段造价影响因素及相关性研究[D].重庆交通大学,管理科学与工程,2011,硕士.
[29]张洁.信号控制交叉口行人交通特性分析[D].长安大学,交通运输工程（专业学位）,2014,硕士.
[30]李兴伟.基于不同状态饱和函数的连续线性系统的稳定性分析[D].哈尔滨理工大学,应用数学,2012,硕士.
[31]孙婉竹.我国农村乡风文明建设研究[D].东北农业大学,马克思主义基本原理,2013,硕士.
[32]谢桂生,石玉梅.基于高阶谱的高分辨率处理[J].石油地球物理勘探,2000,06:695-702+820.
[33]王建程.水产品生产综合计划方法研究[D].广东工业大学,机械工程,2014,硕士.
[34]王丽凤.益生菌L.plantarum P-8对肉鸡肠道菌群、肠道免疫和生长性能影响的研究[D].内蒙古农业大学,农产品加工及贮藏工程,2014,博士.
[35]封巍.新疆特殊教育学校美术学科教育现状调查研究[D].新疆师范大学,美术学,2013,硕士.
[36]张月.琼脂石蜡双包埋切片及三种肿瘤标记物对胸腔积液性质的诊断价值[D].中国医科大学,内科学,2004,硕士.
[37]伍庆.基于FPGA的交流伺服系统电流环设计[D].华中科技大学,控制理论与控制工程,2013,硕士.
[38]段广仁,侯忠生,孙书利.序言[J].系统科学与数学,2014,10:1153.
[39]金晓楠.赵孟頫鞍马画艺术风格研究[D].渤海大学,美术学,2013,硕士.
[40]成守泽.长短桩组合围护结构工作机理研究[D].浙江大学,岩土工程,2013,硕士.
[41]石红霞.我国都市报社会新闻伦理问题研究[D].河北经贸大学,新闻学,2012,硕士.
[42]顾鹏尧,陈俊华,龚德伟,周明华.广义加权网络演化模型[J].数学的实践与认识,2013,22:253-259.
[43]张早娣,李慧,王泽松,付德君.团簇离子束纳米加工技术研究进展[J].中国表面工程,2014,06:28-43.
[44]叶春花.融资结构与治理结构的内在机制研究[D].江西财经大学,金融学,2004,硕士.
[45]方勇.露天矿区居民点安置方式探索[D].中国地质大学（北京）,地质工程,2013,硕士.
[46]严珏烨.高星级酒店顾客满意度影响因素分析[D].浙江工业大学,2009.
[47]李小勇.基于嵌入式Linux的工业无线传感器网络协调器的设计与实现[D].北京交通大学,交通信息工程及控制,2013,硕士.
[48]张旭.以读促写在英语专业写作教学中的实证研究[D].沈阳师范大学,外国语言学及应用语言学,2013,硕士.
[49]周鹤.冠心病患者外周血单核细胞表面晚期糖基化终末产物受体水平的表达[D].大连医科大学,内科学,2012,硕士.
[50]张晓宇.MCAI在中学化学中的运用[D].江西师范大学,教育,2003,硕士.