一类工作调度问题的回溯解法

作     者：刘亮 王相海 LIU Liang;WANG Xiang-hai

作者机构：辽宁师范大学计算机与信息技术学院辽宁大连116029 南京大学计算机软件新技术国家重点实验室江苏南京210093 

基　　金：国家自然科学基金项目(60372071) 辽宁省自然基金项目(20032125) 辽宁省高等学校优秀人才支持计划基金项目(RC-04-11) 

出 版 物：《计算机工程与设计》 (Computer Engineering and Design)

年 卷 期：2006年第27卷第18期

页      码：3338-3339,3343页

摘      要：回溯法是解决组合搜索问题的重要方法,该方法的搜索通过一个多阶段的确定过程来实现,在每一阶段都需要从一些选择中选择一个分支,一旦发现前面的选择不可能获得一个解,则算法进行回溯,即重新回到刚搜索过的选择点,并选择该结点另一个没有被试过的分支,如果该点处所有的分支都已试过,则算法回溯到该结点之前被选择的点。首先对一类分配调度问题进行了分析,然后提出一种基于回溯法的解决方案,并给出了算法的具体实现过程,最后对所提出算法的复杂度进行了分析。实验结果验证了方法的有效性。

主 题 词：回溯 算法 工作调度 限界 复杂度 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.3969/j.issn.1000-7024.2006.18.009

馆 藏 号：203747599...