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

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

Backtracking algorithm for kind of job allocation problem

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.