回溯法
时间：2010-10-24 来源：chinazhangjie
问题表述：给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。
批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。
显然，1,3,2是最佳调度方案。
解空间：排列树（将作业顺序进行全排列，分别算出各种情况的完成时间和，取最佳调度方案）
实现：
/* 主题：批处理作业调度算法 * 作者：chinazhangjie * 邮箱：[email protected] * 开发语言：C++ * 开发环境：Mircosoft Virsual Studio 2008 * 时间: 2010.10.24 */ #include <iostream> #include <vector> using namespace std; class flowshop { public: flowshop(vector<vector<int> >& rhs) { task_count = rhs.size() ; each_t = rhs ; best_t.resize (task_count) ; machine2_t.resize (task_count,0) ; machine1_t = 0 ; total_t = 0 ; best_total_t = 0 ; current_t.resize (task_count,0) ; for (int i = 0 ;i < task_count; ++ i) { current_t[i] = i; // 为了实现全排列 } } void backtrack () { __backtrack (0); // 显示最佳调度方案和最优完成时间和 cout << "the best flowshop scheme is : "; copy (best_t.begin(),best_t.end(),ostream_iterator<int> (cout, " ")); cout << endl; cout << "the best total time is : " << best_total_t << endl; } private: void __backtrack (int i) { if (i >= task_count) { if (total_t < best_total_t || best_total_t == 0) { // 存储当前最优调度方式 copy (current_t.begin(),current_t.end(),best_t.begin()) ; best_total_t = total_t; } return ; } for (int j = i; j < task_count; ++ j) { // 机器1上结束的时间 machine1_t += each_t[current_t[j]][0] ; if (i == 0) { machine2_t[i] = machine1_t + each_t[current_t[j]][1] ; } else { // 机器2上结束的时间 machine2_t[i] = ((machine2_t[i - 1] > machine1_t) ? machine2_t[i - 1] : machine1_t) + each_t[current_t[j]][1] ; } total_t += machine2_t[i]; // 剪枝 if (total_t < best_total_t || best_total_t == 0) { // 全排列 swap (current_t[i],current_t[j]) ; __backtrack (i + 1) ; swap (current_t[i],current_t[j]) ; } machine1_t -= each_t[current_t[j]][0] ; total_t -= machine2_t[i] ; } } public : int task_count ; // 作业数 vector<vector<int> > each_t ; // 各作业所需的处理时间 vector<int> current_t ; // 当前作业调度 vector<int> best_t ; // 当前最优时间调度 vector<int> machine2_t ; // 机器2完成处理的时间 int machine1_t ; // 机器1完成处理的时间 int total_t ; // 完成时间和 int best_total_t ; // 当前最优完成时间和 }; int main() { // const int task_count = 4; const int task_count = 3 ; vector<vector<int> > each_t(task_count) ; for (int i = 0;i < task_count; ++ i) { each_t[i].resize (2) ; } each_t[0][0] = 2 ; each_t[0][1] = 1 ; each_t[1][0] = 3 ; each_t[1][1] = 1 ; each_t[2][0] = 2 ; each_t[2][1] = 3 ; // each_t[3][0] = 1 ; // each_t[3][1] = 1 ; flowshop fs(each_t) ; fs.backtrack () ; }
三、n后问题
问题表述：在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。求不同的解的个数。
解向量：(x1, x2, … , xn)
显约束：xi = 1,2, … ,n
隐约束：
1)不同列：xi != xj
2)不处于同一正、反对角线：|i-j| != |x(i)-x(j)|
解空间：满N叉树
实现：
/* 主题：n后问题 * 作者：chinazhangjie * 邮箱：[email protected] * 开发语言：C++ * 开发环境：Mircosoft Virsual Studio 2008 * 时间: 2010.10.24 */ #include <iostream> #include <vector> using namespace std; class queen { // 皇后在棋盘上的位置 struct q_place { int x; int y; q_place () : x(0),y(0) {} }; public: queen(int qc) : q_count (qc), sum_solution (0) { curr_solution.resize (q_count); } void backtrack () { __backtrack (0); } private: void __backtrack (int t) { if (t >= q_count) { // 找到一个解决方案 ++ sum_solution ; for (size_t i = 0;i < curr_solution.size(); ++ i) { cout << "x = " << curr_solution[i].x << " y = " << curr_solution[i].y << endl; } cout << "sum_solution = " << sum_solution << endl; } else { for (int i = 0;i < q_count; ++ i) { curr_solution[t].x = i; curr_solution[t].y = t; if (__place(t)) { __backtrack (t + 1); } } } } // 判断第k个皇后的位置是否与前面的皇后相冲突 bool __place (int k) { for (int i = 0; i < k; ++ i) { if ((abs(curr_solution[i].x - curr_solution[k].x) == abs(curr_solution[i].y - curr_solution[k].y)) || curr_solution[i].x == curr_solution[k].x) { return false; } } return true; } private: vector<q_place> curr_solution; // 当前解决方案 const int q_count; // 皇后个数 int sum_solution; // 当前找到的解决方案的个数 }; int main() { queen q(5); q.backtrack (); return 0; }
参考资料 《算法设计与分析》王晓东编著
授课教师 张阳教授
相关阅读 更多 +
