I think it is necessary to analyze the efficiency class before optimize it. It is difficult to estimate the efficiency class accurately because the each of recurrence running time is different. So I use a approximate method to estimate the number of nodes generated. The lower bound should be 1+n+n(n-3)+n(n-3)(n-6)+…+ n(n-3)(n-6)…(n-3i)…1 (i<n/3). The upper bound should be 1+n+n(n-2)+n(n-2)(n-4)+…+ n(n-2)(n-4)…(n-2i)…1(i<n/2). Apparently the number of nodes has been generated is between the lower bound and upper bound. Notice that there is no way to improving efficiency on the basis of two bounds unless the algorithm has a revolutionary remodification. Then I limit the optimization to local modification.
The disadvantage mainly is: Before move(), it is advised that check the feasibility of moving as possible in order to avoid the expansive recurrence rather than check it after recurrence. If the checking before move() is in charge, then duplicate_array never has value 2 in it. Note that it is impossible to making this check perfect or else algorithm can generate the permutation directly. The goal of this check function should be perfect as possible as we can. For the sake of confusion, it is wised to rename it by another name: legal_position(int j). There are two matter legal_position should care: 1) j can’t be the number already existed. That is, new chess can’t be the same column with chesses already moved. 2) j can’t be the i+1 or i-1 that i is last moved j. Condition 1) can be achieved by duplicate_array itself and 2) can be achieved by two integral variable.
In addition, the vector<pair<int,int> > does not contribute anything in computation, it is just a container of result. It is necessary to eliminating this redundant container and modifying the implementation of output_functor.
Codes that improved are listed below:
In the definition of class:
class chess_board
{
vector<int> array;
vector<int> duplicate_array;
int integral_check_1;
int integral_check_2;
public:
int n;
int cur_i;
int number_solution;
chess(int dim):integral_check_1(-30000),integral_check_2(-30000),n(dim),cur_i(0),number_solution(0)
{
array.resize(n,-30000);
duplicate_array.resize(n,0);
}
void move(int j)
{
array[cur_i]=j;
integral_check_1=j+1;
integral_check_2=j-1;
if(duplicate_array[j]==0)
duplicate_array[j]=1;
}
void un_move(int j)
{
array[cur_i]=-30000;
integral_check_1=-30000;
integral_check_2=-30000;
if(duplicate_array[j]==1)
duplicate_array[j]=0;
}
bool legal_pos(int j)
{
if(duplicate_array[j] == 0 && j != integral_check_1 && j != integral_check_2)
return true;
else
return false;
}
void write()
{
number_solution++;
for_each(array.begin(), array.end(), output_functor<int>());
cout<<endl;
}
////////////////////////////////////////////////////////////////////////////////////////////
In the definition of output_functor:
template<class T>
struct output_functor : public unary_function<T,void>
{
output_functor():n(0){}
void operator()(const T& p) //note that this operator() modifying n, so throw off const {
cout<<"("<<n<<","<<p<<")"<<" ";
n++;
}
int n;
};
In the BackTracking function:
for(int j=0; j<c.n; j++)
{
if(c.legal_pos(j) == false)
continue;
c.move(j);
c.cur_i += 1;
BackTracking(c);
c.un_move(j);
}
The efficiency improvement is concerned with n, the larger n is, the more improvement have. By the way, Dev 4.9.8.0 can generate the program faster than VC2003 by a large factor. For the situation n=10, program generated by Dev needs about 5 seconds to complete computation, VC2003 needs about 16 seconds. It is not so clear whether this optimization can be attained in layer of C++ or not.
