检索结果-内蒙古大学图书馆

计算机应用 2007年第4期27卷 991-993页

作者：周康同小军刘文斌武汉工业学院数理科学系湖北武汉430023 华中科技大学控制科学与工程系湖北武汉430074

排课表问题是NP-完全问题。基于闭环DNA计算模型引入多种生化实验得出求解排课表问题的DNA算法。本算法采用两部编码方式产生初始数据池,引入批删除实验解决了教师和班级的冲突问题和同班课问题;引入批分离实验解决了正常合班课问题和... 详细信息

排课表问题是NP-完全问题。基于闭环DNA计算模型引入多种生化实验得出求解排课表问题的DNA算法。本算法采用两部编码方式产生初始数据池,引入批删除实验解决了教师和班级的冲突问题和同班课问题;引入批分离实验解决了正常合班课问题和教师时间要求问题;引入电泳实验解决了排课的均衡分配问题;引入标记实验得到了排课表问题的全局最优解集,并给出了算法的生化实现过程。最后,对算法的正确性进行了证明,并讨论了算法的复杂性。

关键词：闭环DNA计算模型排课表问题批删除实验批分离实验

来源：评论

学校读者我要写书评

暂无评论

排课表问题的一种矩阵解法

引用

电子科技大学学报 2000年第5期29卷 560-563页

作者：曾清海电子科技大学宽带光纤传输与通信系统技术国家重点实验室成都610054

对排课表问题进行了探讨，为排课表问题的软件实现提供了详细步骤。将排课表问题的求解转化为矩阵运算，阐述了矩阵运算的相关算法。该方法算法简单，易于软件实现。并对其正确性和可操作性进行了验证。

关键词：排课表问题矩阵二叉树搜索算法

来源：评论

学校读者我要写书评

暂无评论

0-1规划和排课表问题的DNA计算模型研究

0-1规划和排课表问题的DNA计算模型研究

引用

作者：张凤月华中科技大学

学位级别：博士

Adleman1994 年在Science 上发表的文章“Molecular Computation of Solutions to Combinatorial Problems”,成功地用DNA 计算方法求解有向图的Hamilton有向路问题,标志着一个全新的研究领域——DNA计算的随之产生。由于DNA计算机具有... 详细信息

Adleman1994 年在Science 上发表的文章“Molecular Computation of Solutions to Combinatorial Problems”,成功地用DNA 计算方法求解有向图的Hamilton有向路问题,标志着一个全新的研究领域——DNA计算的随之产生。由于DNA计算机具有的巨并行性、海量存储以及低能耗等特点,该领域的研究引起了众多学者的关注。本文结合生物学的研究方法和实验技术,对DNA 计算及其模型生物实现过程中的编码问题做了初步地探讨,并就DNA计算中的简单0-1 规划问题和排课表问题进行了初步研究。在DNA 计算中,信息是以DNA 序列为载体并通过DNA 分子间的特异性杂交来完成信息的处理的,因此,DNA 计算首要的问题就是DNA编码问题。由于DNA计算编码问题实质上属于NP 问题,目前的编码方法还无法很好地满足特定DNA计算模型的实际要求。本文在对DNA 计算中编码问题的产生背景和主要研究进展做了简单介绍,并进一步综合分子生物学实验涉及到DNA 设计基本原则的基础上,提出利用计算机辅助生物软件来对DNA编码链进行验证。结合对一DNA计算模型的DNA编码链的理论及实验结果验证,表明该方法对DNA编码验证是可行的。 DNA 计算离不开生物反应,并且在很大程度上依赖于生物技术的发展,而代表生物技术前沿技术的生物芯片技术,其在对信息的处理和DNA 计算上有诸多相似之处。本文用DNA计算解决规划问题的研究中,对0-1 规划问题分别给出了基于溶液计算、表面计算和溶液表面结合计算的三类DNA 计算模型,分别强调了溶液计算的高度并行和高存储性,表面计算的高自动化程度等优点,并进一步利用溶液与表面计算相结合的方法来避免各自的缺点,突出其优点,生物实验对溶液与表面计算相结合的模型进行了验证。另外,我们指出生物芯片技术可以被用于构建DNA计算的芯片,而可能解决更复杂的规划问题的DNA 计算模型,将是溶液与表面计算、常规和先进生物技术结合的产物。对于DNA计算而言,其关注的焦点在于能否解决现实中的难计算问题。目前研究者逐渐意识到,除非可以获得极大的反应规模,否则理论上仅仅通过增加反应规模来增强计算能力并无助于DNA 计算的进一步发展。基于此原因,我们利用两项生物技术:AcryditeTM 凝胶技术和缩微实验室技术（Lab-on-chip）,首次在理论上构建了解决简单排课表问题的DNA 计算模型,尽管其在运算规模上还无法达到大容积溶液计算的高并行性和高存储量,但两类模型都具有自动化,微型和高通量分析的特征。我们认为通过将前沿的生物技术和计算的新形式的相互结合,在一定程度上对并行性和可行性进行取舍,探索构建杂交型的微型DNA计算机将有助于DNA

关键词： DNA计算 DNA编码的验证 0-1 规划问题排课表问题生物芯片 Acrydite TM 凝胶技术缩微实验室技术(Lab-on-chip)

来源：评论

学校读者我要写书评

暂无评论

求解排课表问题的酶切DNA计算模型研究

求解排课表问题的酶切DNA计算模型研究

引用

作者：桑晓彤大连理工大学

学位级别：硕士

DNA计算作为一种新兴的智能计算手段,在近些年成为国内外学者广泛关注和研究的对象。1994年Adleman创新地采用DNA计算的方法解决七个城市之间的哈密顿路径问题,这标志着DNA计算正式成为解决NP-完全问题的一种有效手段。利用DNA计算解决... 详细信息

DNA计算作为一种新兴的智能计算手段,在近些年成为国内外学者广泛关注和研究的对象。1994年Adleman创新地采用DNA计算的方法解决七个城市之间的哈密顿路径问题,这标志着DNA计算正式成为解决NP-完全问题的一种有效手段。利用DNA计算解决问题的基本思路是:基于DNA分子独特的分子结构和自我复制能力,把现实问题进行DNA编码并生成特定的DNA分子。在生物酶的催化作用下,生成需要的初始解空间。在进行一系列生物反应后删除非解,最后利用PCR技术、凝胶电泳技术等生物方法对结果进行检测并映射成实际问题的最终解。DNA计算由于其并行性高、储存量大等特点,有望在解决NP-完全问题的研究方面有所突破。排课表问题作为一种典型的NP-完全问题,是一个有约束的,多目标优化问题,具有很强的实际实用价值。本文旨在研究面向求解排课表问题的DNA计算模型。在对DNA计算和相关计算模型的研究基础上,本文提出了两种改进的求解排课表问题的酶切DNA计算模型:1.基于AcryditeTM凝胶分离的DNA计算模型。在构建凝胶柱的基础上,通过酶切反应和电泳技术将DNA凝胶柱重新排列,此过程中的最小循环数就是排课表问题中的最少课时数。此模型中限制性内切酶的使用改进了以往计算模型反应时间长、反应条件复杂、容易产生发卡结构等缺点,提高了模型的使用效率。2.上述基于AcryditeTM凝胶分离的计算模型由于其生物技术的限制,难以应用于大规模的排课表问题中。为此,本文通过将荧光技术与酶切技术相结合,提出了可用于求解较大规模排课表问题的表面DNA计算模型。由于模型中的DNA分子以点阵列的形式储存,在并行性和存储量方面都有优势,因而适用于较大规模的排课问题。该计算模型相比之前的计算模型具有反应灵敏度更高、实验操作更简单、反应时间缩短的优点。本文关于DNA计算模型的研究不仅为诸如排课表问题的NP-完全问题提供了更多的求解途径和研究思路,也为DNA计算、生物计算的研究带来了更多可能性,具有一定的理论研究意义和实际应用价值。

关键词： DNA计算模型排课表问题酶切技术 AcryditeTM凝胶技术表面DNA计算

来源：评论

学校读者我要写书评

暂无评论

基于立方体染色解决排课表问题

引用

通信市场 2009年第9期 106-111页

作者：李敬文于自强兰州交通大学电信学院兰州730070

排课表问题是一个NP完伞类问题,本文将排课表问题的要素映射到立方体模型上,根据立方体染色的思想,数学化约束条件,设计出合理高效的算法解决排课表问题.

关键词：排课表问题立方体模型立方体染色

来源：评论

学校读者我要写书评

暂无评论

基于表面的DNA计算模型解决排课表问题

引用

安徽理工大学学报（自然科学版） 2014年第1期34卷 11-14页

作者：单静怡殷志祥安徽理工大学理学院安徽淮南232001

考虑到教师、班级以及课时等的不同要求,复杂的排课表问题就属于NP问题。为了使排课表问题更加简捷,方便,提出了基于微量点样技术的表面DNA计算模型。在实验中,通过对每次结果进行记录和比较,得到了满足问题要求的可行解。不需要改变问... 详细信息

考虑到教师、班级以及课时等的不同要求,复杂的排课表问题就属于NP问题。为了使排课表问题更加简捷,方便,提出了基于微量点样技术的表面DNA计算模型。在实验中,通过对每次结果进行记录和比较,得到了满足问题要求的可行解。不需要改变问题的初始点列,适于研究规模较大的问题。

关键词： DNA表面模型排课表问题 0-1规划问题

来源：评论

学校读者我要写书评

暂无评论

求解排课表问题的一个启发式数值算法

引用

运筹与管理 2005年第5期14卷 36-40页

作者：谢凡荣南昌大学数学系江西南昌330047

为了便于建立与排课表问题有关的决策支持系统,本文给出一个求解排课表问题的启发式数值算法,证明了算法的正确性,并举例说明算法的应用。该算法具有易于编程实现、收敛性好等优点,大量数值实值表明该算法能求得问题的最优解。

关键词：运筹学决策支持系统数值实验排课表问题典则型运输网络最小费用最大流

来源：评论

学校读者我要写书评

暂无评论

遗传算法的一些技术分析及在排课问题中的应用

遗传算法的一些技术分析及在排课问题中的应用

引用

作者：吕晓兰州大学

学位级别：硕士

在排课问题中,主要的考虑因素是时间、教师、教室、班级以及课程。一名教师可能同时担任几门课程的教学,同一门课程有时也由几名教师同时讲授。编排课表时要尽可能做到教师与课程之间的合理搭配,同时必须避免时间和地点(教室)的冲突。... 详细信息

在排课问题中,主要的考虑因素是时间、教师、教室、班级以及课程。一名教师可能同时担任几门课程的教学,同一门课程有时也由几名教师同时讲授。编排课表时要尽可能做到教师与课程之间的合理搭配,同时必须避免时间和地点(教室)的冲突。在满足以上要求后,还可以进一步优化课表结构,使得班级听课次数和教师讲课次数在时间和地点(教室)上合理分布,避免过于集中或过于分散。因而,排课问题是一个多目标的优化问题。求解此类优化问题已有遗传算法、蚁群算法、模拟退火算法、人工神经网络算法等,而遗传算法由于对所求问题的条件转化步骤较少,对目标函数也无特殊要求,求解过程相对于其它优化算法直观性强,对问题的依赖条件少。本文介绍了遗传算法的基本求解过程,分析了与位爬山法相结合的混合遗传的结构、收敛性及欺骗性问题,将该方法作为求解排课问题的算法。对排课问题的各种约束条件和求解目标做了详细分析,选取了较主要的目标作为求解对象,用线性加权法处理个目标之间的关系,将加权后的结果作为方案的最终目标。

关键词：遗传算法多目标规划混合遗传算法位爬山法线性加权和法排课表问题

来源：评论

学校读者我要写书评

暂无评论

基于DNA计算模型的图顶点着色问题及其应用

基于DNA计算模型的图顶点着色问题及其应用

引用

作者：陈敏安徽理工大学

学位级别：硕士

DNA计算是一门新兴学科,是生物计算中最受关注的一种智能计算,自1994年,图论中的哈密顿路径问题被Adleman利用DNA计算成功解决并进行了实验,DNA计算就成为国内外专家学者关注的重要领域。DNA计算的基本思想是：利用DNA分子特殊的自我复... 详细信息

DNA计算是一门新兴学科,是生物计算中最受关注的一种智能计算,自1994年,图论中的哈密顿路径问题被Adleman利用DNA计算成功解决并进行了实验,DNA计算就成为国内外专家学者关注的重要领域。DNA计算的基本思想是：利用DNA分子特殊的自我复制等性能,产生相应的编程,然后生成DNA分子链,在各种生物酶的催化下,生成所需的数据池(data pool),然后进行生物反应。最后,利用PCR、分子纯化、凝胶电泳、磁珠分离等生物技术,对产生的结果进行检测。首先,本文介绍了DNA计算的产生背景,研究状况,生物学操作。指出DNA计算机的优点与缺点、实际应用与存在的问题。其次通过对DNA计算的几种模型的研究,试图找到DNA计算模型来解决图顶点着色问题,并对几种模型进行比较。最后,利用图顶点着色的DNA计算模型,解决了课表安排问题及机场停机位问题。排课表是一个典型的NP-完全问题。本文利用AcryditeTM凝胶技术,把课时作为图顶点着色信息映射成DNA分子链,构建凝胶柱,通过生物反应将DNA链重新排列,排列所需要的最少循环数即为排课表所需要的最少课时数。AcryditeTM凝胶技术作为较新的一种核酸分离技术,在DNA计算中得到了成功应用。停机位分配(ASA)是一种关于优化组合的问题,分配的合理性对机场的生产调度非常关键。本文通过对ASA问题的分析,把ASA问题转化为基于DNA计算的图顶点着色模型并设计了一种生物算法。经过多次实验证明：这种算法非常的简单,在实验室中很容易操作,与遗传算法,贪婪算法相比,更具有优势。

关键词： DNA计算图顶点着色问题排课表问题 AcryditeTM凝胶技术停机位分配

来源：评论

学校读者我要写书评

暂无评论

一个NP问题的近似算法

引用

东北电力学院学报 2002年第1期22卷 39-43页

作者：于标扬州职业大学江苏扬州225002

对程序排课问题的近似算法进行了探讨 ,提出了一种实用的近似算法 ,可使程序排课问题得到相当程度的解决。

关键词： NP问题近似算法边着色排课表问题

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：