【摘 要】
:
在包含一组相互分离凸多面体的三维空间中为任意两点寻找最短路的问题是NP问题.当凸多面体的个数k 任意时,它为指数时间复杂度;而当k= 1时,为O(n2)(n 为凸多面体的顶点数).文章主要研究了k= 2情形下
【基金项目】
:
国家自然科学基金;国家863高科技项目基金;中国科学院院长特别基金
论文部分内容阅读
在包含一组相互分离凸多面体的三维空间中为任意两点寻找最短路的问题是NP问题.当凸多面体的个数k 任意时,它为指数时间复杂度;而当k= 1时,为O(n2)(n 为凸多面体的顶点数).文章主要研究了k= 2情形下的最短路问题,提出一个在O(n2)时间内解决该问题的算法.所得结果大大优于此情形下迄今为止最好的结果——O(n3logn).另外,将此结果应用到k> 2的情形后,获得的结果为O(12i- 1n2i).
其他文献
随着电子商务的快速发展,电商供应链中企业之间的供需关系变化加大,使得供应链上中小企业融资难问题更加突出,基于电子商务的供应链金融服务创新成为供应链管理中一个新的研
目的探析亚临床甲状腺功能减退(SCH)与多囊卵巢综合征(PCOS)者间的相关作用及关系。方法选取2017年3月-2018年2月在湖北省江陵县人民医院接受诊断治疗的52例SCH伴PCOS者和55
目的本文就静脉治疗护理小组在静脉化疗中的作用效果进研究。方法选取2016年1月至12月在我科接受静脉化疗的96例患者,采用随机数字表法分为实验组与参照组,各48例。参照组患
浅层地热能资源作为一种可再生、环保、清洁、储量巨大的新型能源资源,逐渐被人们认识、接受和重视。随着地源热泵技术的日益进步,我国城市地区浅层地热能利用正快速发展,为
对城域传送网PTN独立组网及OTN+PTN联合组网模式的网络结构及演进进行了深入探讨,并提出了组网时应注意的有关问题。文中有关数据主要借鉴烽火通信相关设备(OTN设备型号为FON
随着影像时代的到来和多媒体技术在教学中的广泛运用,英美文学课程教学应坚持其教学目标和本质为主,重视经典英美文学作品阅读;教师可采取课堂内与课堂外、传统阅读与数字阅
<正>设计一【教学设想】如果教学还停留在"把每一个字词圈起来,多写几遍、背课文注释、考文言翻译……"的思维时,将无法轻松驾驭一堂会让孩子感动生命或印象深刻的语文课!我
复句与句群转换例析河南濮阳县教师进修学校李家林《中学教学语法系统提要(试用)》指出:“有些句群可能改造成一个复句或者多重复句。有些复句、多重复句也可能改造成句群,视表达
基于齿轮加工工艺的需求,以YK2050数控螺旋锥齿轮磨齿机和No.116机械铣齿机为例,推导了将"T类"机械式铣齿机加工调整参数转化成数控螺旋锥齿轮磨齿机调整参数的原理及公式。
基于齿轮加工工艺的需求,以YK2050数控螺旋锥齿轮磨齿机和Y2280机械铣齿机为例,推导了将“M类”机械式铣齿机加工调整参数转化成数控螺旋锥齿轮磨齿机调整参数的原理及公式。