目标序列部分确定的翻转距离星树问题

来源 :软件学报 | 被引量 : 0次 | 上传用户：neu20063043

【摘要】

：

讨论翻转距离星树问题,将3SAT问题归约到目标序列部分固定的翻转距离星树问题,证明实例中当有向符号序列个数为3时,若目标序列符号顺序固定,且有部分符号方向给定,则只确定其

【作者】

：

栾峻峰朱大铭马绍汉

【机构】

：

山东大学

【出处】

：

软件学报

【发表日期】

：

2003年2期

【关键词】

：

目标序列翻转距离星树问题 NP问题算法计算复杂性进化树基因组 algorithm computational complexity evoluti

【基金项目】

：

国家自然科学基金

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

讨论翻转距离星树问题,将3SAT问题归约到目标序列部分固定的翻转距离星树问题,证明实例中当有向符号序列个数为3时,若目标序列符号顺序固定,且有部分符号方向给定,则只确定其余符号方向以使得目标序列与已知3条给定序列翻转距离之和最小所对应的翻转距离星树问题也是NP-难解问题.同时,还给出了该问题的多项式时间近似算法.

其他文献

特效查杀木马的金山毒霸6增强版

网络是一个多元化的世界,在这个虚拟与现实交织的地方,只要您的计算机是连入网络的,您就随时都面临被攻击的危险。肆虐的病毒,泛滥的垃圾邮件,不断攻击的黑客,尤其是特洛伊木

期刊

金山毒霸查杀增强版木马病毒病毒库日志文件密码安全病毒防火墙闪盘功能点

集合索引结构及其联接操作

集合类型是面向对象数据库和对象-关系数据库中的一种重要的数据类型.提出了集合类型数据的一种索引结构Set_struc,并提出了基于Set_struc的集合联接算法.Set_struc通过合并

期刊

集合索引Set_struc联接操作Indexing (of information)Set theory

第2届全国智能科学与技术教育学术研讨会（第l轮）征文通知

期刊

解剖黑暗——浅谈寂静岭

寂静岭,一个大雾弥漫,谜一样的小镇;《寂静岭》,一个有着庞大世界观和厚重文化底蕴的游戏。是的,现在的《寂静岭》(以下简称sh)系列已经无可厚非地确定了其AVG游戏世界的王者

期刊

游戏世界王者地位生化危机罪与罚文化底蕴男主角报纸报道预告片美国中部告诉我

从元青花四爱图梅瓶谈艺术的目的

摘要：任何人类活动都是有目的的，自觉的目的性是人类区分于动物的重要标志。艺术作为一种感性物质生活需要之外的人类活动，它当然也有其目的。从总体上看，艺术的目的，就是激活人的非功利心态，实现对现实世界的超越，实现人的自我确证，构建虚拟的自我中心世界。　　關键词：元青花四爱图梅瓶艺术　　[本文系安徽省高等学校省级质量工程《美术教育专业综合改革试点》课题（批号2012zy085）阶段性成果。]　　在

期刊

元青花四爱图梅瓶艺术

肺癌误诊为肺脓肿18例临床分析

目的：探讨肺癌误诊为肺脓肿原因。方法分析温州医科大学附属第一医院1999.2-2013.4月间收治的18例支气管肺癌误诊为肺脓肿患者的临床表现、影像学特点。结果部分肺癌的临床表

期刊

支气管肺癌延误诊治肺脓肿临床分析影像学特点附属第一医院临床表现经皮肺穿刺

“文检课”新理念与大学生素质教育

期刊

高校文献检查课大学生素质教育

药物过敏致双目失明1例分析

本文通过对1例药物过敏所致双目失明案例的分析,讨论了对《审视瑶函》中提出的＂内障＂一病的治疗经验。1病案举例王某,女,11岁。初诊日期2009年3月3日。主诉：双目干痛9个月,视力

期刊

《审视瑶函》内障羞明药物过敏医案

淳安县农村卫生院改革的做法与体会

<正> 淳安是一个集库区、山区、边区、老区于一身的经济欠发达县,人口45万,其中农业人口占全县总人口的89％以上。全县原有66个乡镇卫生院,1993年撤扩并为37个乡镇卫生院、29个

期刊

农村卫生院改革浙江淳安县

金华县乡镇卫生防保体制模式探讨

<正> 为研究农村卫生防保体制如何适应中国特色卫生防病工作的需求,近年来,我们在理顺关系、完善体制、扩大功能、强化队伍建设等方面进行了乡镇卫生防保体制的改革,通过5年

期刊

乡镇卫生卫生防保体制服务模式

目标序列部分确定的翻转距离星树问题

与本文相关的学术论文