2013
12-27

回溯法（2）

/* 主题：批处理作业调度算法
* 作者：chinazhangjie
* 邮箱：[email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
* 开发语言：C++
* 开发环境：Mircosoft Virsual Studio 2008
* 时间: 2010.10.24
*/

#include <iostream>
#include <vector>
using namespace std;

class flowshop
{
public:
flowshop(vector<vector<int> >& rhs) {
each_t = rhs ;
machine1_t = 0 ;
total_t = 0 ;
best_total_t = 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 (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 :
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 ;
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 () ;
}

1)不同列：xi != xj

2)不处于同一正、反对角线：|i-j| != |x(i)-x(j)|

/* 主题：n后问题
* 作者：chinazhangjie
* 邮箱：[email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
* 开发语言：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;
}

1. bottes vernies blanches

I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!