【摘 要】
：
骨架分析是近年来NP-难解问题研究的热点,对于衡量问题的相变、难度及算法设计具有重要意义.骨架的理论分析及在算法设计方面的应用还处于起步阶段.从QAP问题入手,对QAP骨架进行了理论分析,证明寻找QAP问题的骨架属于NP-难解问题,不存在多项式时间的算法可以保证得到QAP问题的骨架,为局部最优解交叉来获得近似骨架提供了合理性解释.在此基础上,利用偏移实例构造方法,提出了基于偏移实例的近似骨架算法.
论文部分内容阅读
骨架分析是近年来NP-难解问题研究的热点,对于衡量问题的相变、难度及算法设计具有重要意义.骨架的理论分析及在算法设计方面的应用还处于起步阶段.从QAP问题入手,对QAP骨架进行了理论分析,证明寻找QAP问题的骨架属于NP-难解问题,不存在多项式时间的算法可以保证得到QAP问题的骨架,为局部最优解交叉来获得近似骨架提供了合理性解释.在此基础上,利用偏移实例构造方法,提出了基于偏移实例的近似骨架算法.其基本思想是:首先为QAP实例构造偏移实例,其最优解恰是原QAP实例的一个全局最优解;然后利用现有算法求
其他文献
神经退行性疾病是一类以神经元退行性病变或凋亡,从而导致个体行为异常乃至死亡为主要特征的疾病.随着社会逐渐步入老龄化,神经退行性疾病的发病率不断攀升,而大多这类疾病诊断困难,目前尚无有效的治疗措施.干细胞研究的迅速发展,为这类疾病的治疗提供了新的途径和可能.目前多种干细胞在神经退行性疾病动物模型上的尝试已取得进展.本文综述了胚胎干细胞、间充质干细胞、神经干细胞等在神经退行性疾病如帕金森氏病、阿尔茨海
采用Discovery Studio2.0中的药效团模型生成方法,产生了基于化学特征的ACE抑制肽的药效团模型.所选择的认为最好的药效团模型(Hypo1)含有5个化学特征(1个阴离子中心、1个氢键受体、1个氢键给体、2个疏水中心).我们先前采用实验的方法,从蚕蛹蛋白中获得具有ACE抑制活性的六肽分子,本文结合产生的ACE抑制肽药效团模型和分子对接研究,对该六肽分子进行结构优化,以识别六肽中对ACE
利用固相萃取分离和核磁共振技术(nuclear magnetic resonance,NMR)对人体尿液中的代谢物进行了较为系统的研究.通过对人体尿液样品固相萃取后分离得到的五个组分1HNMR,同核二维氢谱(correlation spectroscopy,COSY)和全相关谱(total correlation spectroscopy,TOCSY),异核相关光谱(heteronuclear s
提出了基于p进数域上的椭圆曲线的有理点群的商群的密码系统.这种密码与基于有限域上的椭圆曲线密码相比,增加了新的加密参数,在倍乘运算等方面具有优越性,且有相同的安全强度.给出了密码群的生成元的选取方法,通过建立这种商群的元素与其坐标近似值的一一对映应关系,解决了p进数域的椭圆曲线商群元素有限表示问题,并且给出了在此近似表示下商群的运算方法.
可重构计算兼顾定制计算的高效性与通用计算的灵活性,是人们正在探索的一类新型计算机体系结构.文中介绍一种粗粒度可重构多核协处理器体系结构,用于加速计算密集或数据密集类算法.在该结构中采用具有猜测执行机制的循环自动流水线技术,将流水线并行执行和数据驱动执行紧密结合.采用以循环程序为单位的固定指令多数据流执行模式,在循环执行期间,每个单元固定执行一种指令,配置信息量减少,支持快速动态重构.设计了多种特殊
对视野中的物体及运动方向进行感知是视觉感知的基本问题之一,较高级视皮层从V1区的简单细胞开始分为两个通路:"What通路"和"Where通路".前者对物体的形状、颜色、纹理等内容感知,后者对空间运动速度和方向等感知.本文利用仿脑视觉信息处理计算结构,研究视觉内容和运动方向上的感知计算模型、计算机理和学习算法.该计算模型是一个三层的神经网络,第一层是视觉信号输入层,用于接收外界图像刺激.第二层是神经
提出一种可用于高速片上系统异步IP模块互连的低摆幅差分接口电路.此接口电路驱动器通过驱动阵列(driver array)算法进行以降低功耗为目标的优化,接收器采用差分电平触发锁存器(differential level-triggered latch,DLTL)结构,能够正确恢复经过互连线传输的极低摆幅数字信号.与同类接口电路比较,在500MHz的信号频率下,提出的接口电路结构可以恢复50mV摆幅
特征捆绑问题一直是认知科学和神经科学中的一个重要问题.本文通过将噪声神经元模型的思想、贝叶斯方法和脉冲神经网络模型相结合,并引入竞争机制,提出了一个特征捆绑的计算模型-BayesianL inking Field模型,对视感知中的特征捆绑问题进行研究.实验证明本研究的模型很好地完成了视觉感知中特征捆绑的任务,并给感知研究带来了新的思路.
针对四川盆地东部的2006年特大干旱,分析MODIS遥感观测资料对旱情的响应,以探求区域干旱遥感监测的可操作性方案.首先,依据地面气象和水文观测初步估算了旱情的发展过程和空间分布范围,利用MODIS产品计算了2001~2006年夏季每8天的地表水分遥感指数;然后,构造并计算了地表水分距平遥感指数,用之检验了四川盆地东部特大干旱的遥感响应;最后,基于地表水分距平遥感指数分析了不同植被覆盖类型对干旱的
针对目前程序切片方法较单一,且其模块性和程序语言适应性较差,提出一种新型的形式化程序切片方法—基于模块单子语义的切片方法.通过设计切片单子转换器,切片这一类计算被抽象成独立于具体语言的切片单子转换器,它可模块化地加载到实际程序中,得到相应的模块单子切片算法.这种模块化的抽象机制使得单子切片算法具有较强的模块性和语言适应性.还给出切片单子转换器的若干性质,并证明模块单子切片算法的正确性和终止性,同时