【摘 要】
：
目前各种分子计算模型多基于生物技术,求解一个问题的分子计算机算法很难不作修改地应用于其他类似的问题,尚不似传统计算机般通用。为此,提出一种基于图灵机的广义分子计算模型,其由一台单带图灵机、一条单向只写带和一条工作带组成,通过只写带与工作带之间特殊的映射函数实现并行的同时读、写操作。实验说明了该模型能够在多项式时间求解NP完全的满足性问题(SAT),比现有分子计算模型在计算准确性和通用性上存在明显优
【机 构】
：
北京理工大学机电学院爆炸科学与技术国家重点实验室,北京邮电大学计算机学院智能通信软件多媒体北京市重点实验室
【基金项目】
：
国家自然科学基金资助项目（11272066）
论文部分内容阅读
目前各种分子计算模型多基于生物技术,求解一个问题的分子计算机算法很难不作修改地应用于其他类似的问题,尚不似传统计算机般通用。为此,提出一种基于图灵机的广义分子计算模型,其由一台单带图灵机、一条单向只写带和一条工作带组成,通过只写带与工作带之间特殊的映射函数实现并行的同时读、写操作。实验说明了该模型能够在多项式时间求解NP完全的满足性问题(SAT),比现有分子计算模型在计算准确性和通用性上存在明显优势。
其他文献
应急条件(地震、泥石流、洪水等)下的路况不稳定,随时会发生意外的问题。为了解决应急条件下的物资分配,在研究蚁群算法解决传统VRP(vehicle routing problem)的基础上,通过加入动态路况子对VRP数学模型进行改进,提出蚁群算法对改进后的车辆路路径问题的数学模型,并利用陕西省21个城市的实际经纬度作为应急情况下的模拟货物需求地点和仓库进行系统仿真,对影响改进算法收敛性的参数进行分析
针对交通场景中车辆距离过近和相互遮挡的问题,提出了利用车辆边缘的遮挡车辆曲线分割算法。首先在图像分块的基础上检测出车辆区域,根据车辆区域的长宽比和占空比进行多车判断;然后对车辆区域进行HSI空间亮度均衡化和平滑处理,并利用一维最大熵法分割图像;最后确定车辆区域的中心线,并提取车辆的边缘轮廓,曲线分割遮挡车辆。实验结果表明,算法能够按照车辆的边缘轮廓准确分割遮挡车辆,与其他算法相比,在满足实时性的前
前向安全公钥加密方案是指当前时段的私钥泄露不会造成敌手得到解密过去时段的密文的能力。已有的前向安全加密方案一般存在密文长度与时间段总数成线性关系的问题,并且加解密效率也较低。针对这一系列问题,提出了一个新的前向安全公钥加密方案,所有参数关于时间段总数的复杂性均不超过对数的平方,且在标准模型下证明了它的安全性。该方案具有定长密文、固定加/解密开销的特点。
在能量有限的无线网络中,网络生存时间往往需要尽量延长。针对网络生存时间优化问题,综合考虑了随机拓扑环境中的无网络编码场景、双向网络编码场景和侦听网络编码场景,结合功率控制模型、数据流个数、业务需求分布和每个节点的初始能量,使用内点方法对这些场景下的网络生存时间进行评估和优化。仿真结果说明了在弱功控情况下,网络编码可提高生存时间增益,该增益和计算开销都随数据流个数的增加而增加,而业务需求分布和节点初
提出一种基于区分服务的拥塞控制机制(DiffServ congestion control,DSCC)用于解决Mesh网拥塞问题。该机制首先对到达节点的实时业务、非实时业务到达率进行周期性的统计,依据统计值对节点下一时段到达的主流业务类型进行预测,同时动态地调整缓存队列长度的阈值以监测拥塞。最后DSCC根据未来到达的主流业务类型,自适应地为节点设定传输避让指数,公平有效地缓解了网络拥塞。实验结果表
Ad hoc网络的无线、自组织特点使其很容易受到DoS攻击。在已有研究成果DSR-BCA协议的基础上,增加一个应对DoS攻击的机制,参与网络路由的节点都执行路由参与验证算法,当网络数据传输的丢包率超过预设阈值时,用隔离算法找出被DoS攻击的节点并隔离它,使网络节点的有效性最大化。仿真实验表明,该方法在Ad hoc网络受到DoS攻击时的效果明显,在平均传输时延和分组投递率两方面的性能都有提高,对于D
针对传统社团检测算法无法判断网络中特殊节点和SCAN算法对于参数依赖性太大的缺点,提出了一种基于自然最近邻居概念的社团检测算法CD3N。算法利用自然最近邻居无参的特性,首先以结构相似度为基准,计算出网络节点的自然最近邻居,并依此构造小值最近邻域图;然后取邻域图中邻居数最多的节点为核心节点,根据可达关系,构造关于核心节点的社团;重复选取核心节点并构造社团的过程,直到没有可归入社团的节点。将算法应用到
引入本体论思想研究空间关系描述与推理,目的是为了实现地理空间信息的共享和互操作。从地理本体的概念出发,建立了符合常识空间认知的空间关系描述模型。以河南省行政区划、交通、旅游景点为基础数据,构建了空间关系本体实例库;自定义了空间关系推理规则,并实现了规则的SWRL表达;设计了基于本体的定性空间关系推理总体框架,并结合应用实例进行了推理实验,有效地验证了空间关系本体推理机制的可行性。
为了实现移动机器人在障碍环境中的路径规划,提出一种改进的混合蛙跳算法(SFLA)。改进算法在原算法基础上引入交叉操作,并在青蛙更新策略中充分利用学习机制;此外提出了一种带控制参数的产生新个体的方法代替原本的随机更新操作。把路径规划问题转换为最小化问题,基于环境中目标和障碍物的位置定义青蛙的适应度,机器人依次到达每次迭代中最好蛙的位置,从而实现最优路径规划。移动机器人仿真实验中,与基本蛙跳算法和其他
采用基于字的随机故障模型对SHACAL-2*算法进行差分故障攻击,理论结果和实验数据都表明以超过60%的成功概率恢复512 bit的种子密钥需要160个随机故障,以超过97%的成功概率恢复512 bit的种子密钥需要204个随机故障。SHACAL-2*算法可以找到两个有效的差分故障位置,而SHACAL-2算法只有一个有效的差分故障位置。因此,从实施差分故障攻击的难易程度看,SHACAL-2*算法抵