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

Backtracking algorithm for kind of job allocation problem

作　　者：刘亮[1] 王相海[2] 

机构地区：[1]辽宁师范大学计算机与信息技术学院,辽宁大连116029 [2]南京大学计算机软件新技术国家重点实验室,江苏南京210093

出　　处：《计算机工程与设计》2006年第18期3338-3339,3343,共3页Computer Engineering and Design

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

摘　　要：回溯法是解决组合搜索问题的重要方法,该方法的搜索通过一个多阶段的确定过程来实现,在每一阶段都需要从一些选择中选择一个分支,一旦发现前面的选择不可能获得一个解,则算法进行回溯,即重新回到刚搜索过的选择点,并选择该结点另一个没有被试过的分支,如果该点处所有的分支都已试过,则算法回溯到该结点之前被选择的点。首先对一类分配调度问题进行了分析,然后提出一种基于回溯法的解决方案,并给出了算法的具体实现过程,最后对所提出算法的复杂度进行了分析。实验结果验证了方法的有效性。Backtrack programming is a well-known technique for solving combinatorial search problems. The search is organized as a multi-stage decision where, at each stage, a choice among a number of alternatives is made. Whenever it is found that the previous choices cannot possibly lead to a solution, the algorithm backtracks, that is to say, re-establishes its state exactly as it was at the most recent choice point and chooses the next untried alternative at this point. If all alternatives are tried, the algorithm backtracks to the previous choice point. A kind of job allocation problem is brought up firstly. And then an efficient algorithm is presented based on backtracking algorithm. Finally, the complexity of the proposed algorithm is analyzed. Simulation results show it is effective.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]