正则图控制数及其相关问题的研究

结题报告

项目介绍

AI项目解读

基本信息

批准号：
61063004
项目类别：
地区科学基金项目
资助金额：
22.0万
负责人：
付学良
依托单位：
内蒙古农业大学
学科分类：
F0201.计算机科学的基础理论
结题年份：
2013
批准年份：
2010
项目状态：
已结题
起止时间：
2011-01-01 至2013-12-31

项目参与者：
李美安；李宏慧；董改芳；扈华；王艳芬；左东石；宋平平；马俊清；
关键词：
彩虹控制数控制数罗马控制数符号边控制数算法

项目摘要

本项目研究图的控制数及其相关问题的精确解，特别是图的控制数、图的罗马控制数、图的彩虹控制数以及图的符号边控制数；同时，研制较好的计算图的控制数及其相关问题算法, 进而研究给定控制条件下的正则图的特征，从中探讨出图的控制数及其相关问题中一些基本性质，并为这些图的实际应用提供更坚实的理论基础。.图的控制数及其相关问题具有许多实际应用背景，图的控制数问题最初是在网络设计与分析的实际应用领域中提出来的。对图的控制问题及其相关性质的深入研究，在线性代数、最优化理论、通信网络的设计和分析、计算复杂性、算法设计与分析等领域都有广泛的应用。本课题属于NP困难问题，研究它对解决一般NP困难问题也很有意义。.在图的控制数及其相关问题精确解的研究领域，申请者已取得了部分国际领先成果，本项目的研究，将有助于我们在该领域继续保持国际领先水平。

结项摘要

本项目以图的控制数及其相关问题为理论研究基础，以正则图控制数及其相关问题的精确解为着眼点，以正则图控制数算法研究为突破口，研究的重点和问题解决的核心是图的控制数算法设计、分析、优化和应用。项目取得的成果如下：（1）本课题研究的是正则图控制数精确解，该问题是NP困难问题，研究的关键是设计一个好的计算算法。传统对图的控制数计算采用图的DSF或BSF搜索算法计算图的控制数近似解，本项目在研究的过程中探讨了将遗传算法、人工免疫算法、分支限界算法、蚁群算法以及混沌理论等有机融合到图的控制数精确解的计算算法当中，并取得了较好的结果。同时对传统的计算图的控制数的串行算法结合图的控制数算法计算的内在特性成功移植到云平台（Cloudsim平台）上，完成了串行算法到并行算法的转换，并完成了计算过程的可视化软件开发，使得运行效率显著提高，该成果已成功申请到国家软件著作权专利。在有效提升算法效率的同时，将计算机证明和数学证明相结合，成功的解决了广义帕特森图以及循环图等正则图的控制数的精确解。（2）在国内外首次系统的将图的控制数串行算法并行化与可视化，并获得了国家软件著作权专利，目前有大连理工大学、山东科技大学、太原理工大学以及中国计量大学等高校研究图的控制数的专家、学者给予好评，并对软件运行稳定性和效果给予肯定。该成果不仅对图的控制数计算上很有帮助，对目前的研究热点领域物联网任务调度及云计算任务调度算法也很有借鉴作用。（3）在本项目资助下，在国内外核心期刊上发表论文23篇，其中被SCI检索文章3篇，被EI检索文章5篇，ISTP检索文章2篇，另有4篇文章被EI刊源接收，4篇处于SCI刊源审稿之中。（4）在本项目资助下，成功培养了硕士生毕业8名，现在在读的三年级研究生5名，二年级研究生6名，在读博士研究生1名，资助青年教师5名；成功培育了一支内蒙古农业大学校级教学与科研团队。