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

摘要：

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

关键词：回溯、算法、工作调度、限界、复杂度

所属期刊栏目：27

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金60372071;山东省自然科学基金20032125;辽宁省高等学校优秀人才基金RC-04-11

在线出版日期：2006-10-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：3338-3339,3343