#pragma warning(disable:4996)
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<fstream>
#define inf 100000000
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define Tabu_prob 1 // rejects tabu listed substrings with "tabu_prob" probability
#define Distinct_Substr 300005 // Maximum no. of distinct substrings
#define NO_UPDATE 70 // No update for NO_UPDATE iterations -> terminate
#define MAX_RUN 4
#define POPULATION_SIZE (n*2) // No. of ants = some multiple of no. of target strings in the input
#define T 305 // Maximum Cardinality of the set of target string
#define M 305 // Maximum length of target string
#define child 130 // no. of children of a node in TRIE
/* constants for a random number generator, for details see numerical recipes in C */
#define IA 16807
#define IM 2147483647
#define AM (1.0/IM)
#define IQ 127773
#define IR 2836
#define MASK 123459876
/* constants for a random number generator, for details see numerical recipes in C */
using namespace std;
// seed for ran01
int seed = (int) time(NULL);
//is tabu on ? 1 : on, 0:Off
int tabu_done;
char str_folder[100];
double ran01( int *idum )
/*
FUNCTION: generate a random number that is uniformly distributed in [0,1]
INPUT: pointer to variable with the current seed
OUTPUT: random number uniformly distributed in [0,1]
(SIDE)EFFECTS: random number seed is modified (important, this has to be done!)
ORIGIN: numerical recipes in C
*/
{
long k;
double ans;
k =(*idum)/IQ;
*idum = IA * (*idum - k * IQ) - IR * k;
if (*idum < 0 ) *idum += IM;
ans = AM * (*idum);
return ans;
}
// v is target string idx, returns pair<> to access istarget
pair<int,int> calc_target_idx(int v)
{
return make_pair(v/30,v%30);
}
struct trie
{
// int freq_target; // freq. of target strings
// int istarget[10]; // which target string contains this substring -> bitwise access
int val; // contains the unique idx of root to this position
// int freq; // total frequency of this substring
trie *next[child];
trie()
{
int i;
val=-1;
// memset(istarget,0,sizeof(istarget));
for(i=0;i<child;i++)
next[i]=NULL;
}
~trie()
{
int i;
for(i=0;i<child;i++)
delete next[i];
}
};
//if q<=q0 then in ACS the best solution is selected
const double q0 = 0.25;
//prob of best
const double p_best = 0.09;
double t_max, t_min; //Max, Min limit of pheromone value
//this is not used -> will not work for MMAS
const double minus_pheromone = 0.0; //total amount of evaporation in a run
//so it is made const. zero, so don't need to change anything in select_jump
/********************************/
double alpha, beta, evaporation_rate;
double allowed_time; //may need to read from input
int sub_freq[Distinct_Substr]; //total freq. of substring w.r.t. it's id
int sub_freq_target[Distinct_Substr]; //freq. of target strings who contain id-th substr
int sub_is_target[Distinct_Substr][22]; //bitmap -> 1 -> which targets contain this id
pair<int,int> sub_start[Distinct_Substr];
pair<int,int> sub_end[Distinct_Substr];
int sub_tabu[Distinct_Substr]; //substring -> tabu or not
int tabu_active; //marker of active tabu
trie *root;
int L; //L of L-cover
int id; //gives id to a substring
int n; //number of target strings
int m; //maximum length of a string
int max_len_in_all; //maximum length of a substring which is a substring of every target string
int max_allowed_substr_length; //in solution set
int min_allowed_substr_length; //in solution set
char toBeCovered[T][M]; //target strings
int target_length[T];
double sqrt_m;
ofstream output,output_best;
struct node
{
// int length;
double cost;
int substr_idx;
double pheromone, eta, probability, cum_prob;
double eta1, eta2;
void init(int length)
{
pheromone = 10.0;
//cost = 1.0;
if(length > max_allowed_substr_length)
cost = inf;
//else if(length > m/4)
// cost = 1.2;
else if(length < min_allowed_substr_length)
cost = inf;
// else if(length==2)
// cost = 1.5;
else
cost = 1.0;
eta = (0.001 * eta1 + 0.999 * eta2 * sqrt(length / sqrt_m) ) / cost;
//eta = (0.0995 * eta1 + 0.9 * (eta2) + 0.0005* (length)/(sqrt_m) ) / cost;
//eta = (0.001 * eta1 + 0.999 * (eta2) ) / cost; //instances_100_a4_s20-30_l3-10_L50-100
// eta = sub_freq[substr_idx]/(id + 0.0); // needs change
}
};
//targetidx pos
vector<node> adj[T][M]; //vector of edges from [T][M]
node all_node[1000005]; //just a list of all nodes according to id
struct solution
{
double cost; //cost or fitness of this solution
set<int> substr_list; //set of ids of the substrings
vector< pair<int,int> > jumps; //represents the jumps -> <target_string_idx, pos>
void init()
{
substr_list.clear();
jumps.clear();
}
void calc_cost()
{
int i;
cost = 0.0;
vector<int> now_here(substr_list.begin(),substr_list.end());
for(i=0;i<now_here.size();i++)
cost += all_node[now_here[i]].cost;
// printf("calc cost ok \n");
}
}global_best, local_best, current;
void addtoTrie(trie *now,int i,int j,int pos)
{
// if(pos-j+1>13)
// return;
if(!toBeCovered[i][pos])
return;
pair<int,int> access_target = calc_target_idx(i);
int temp_idx;
int v = toBeCovered[i][pos];
if(!now->next[v])
{
now->next[v] = new trie();
now->next[v]->val = id++;
// node temp;
// temp.substr_idx = now->next[v]->val;
// temp.init();
// all_node[temp.substr_idx] = temp;
// now->next[v]->freq = 1;
temp_idx = now->next[v]->val;
sub_freq[temp_idx] = 0;
sub_freq_target[temp_idx] = 0;
memset(sub_is_target[temp_idx],0,sizeof(sub_is_target[temp_idx]));
}
temp_idx = now->next[v]->val;
sub_freq[temp_idx]++;
sub_start[temp_idx] = make_pair(i,j);
sub_end [temp_idx] = make_pair(i,pos);
if( !(sub_is_target[temp_idx][access_target.first] & (1<<access_target.second)) )
sub_is_target[temp_idx][access_target.first] |= (1<<access_target.second),
sub_freq_target[temp_idx]++;
/*
if( !(now->next[v]->istarget[ access_target.first ] & (1<<access_target.second)))
now->next[v]->istarget[ access_target.first ] |= (1<<access_target.second),
now->next[v]->freq_target++;
*/
//sub_freq[now->next[v]->val] = now->next[v]->freq;
node temp;
temp.substr_idx = now->next[v]->val;
adj[i][j].push_back(temp);
addtoTrie(now->next[v],i,j,pos+1);
}
void buildGraph()
{
// all_node.clear();
root = new trie();
root->val = id++;
int i,j;
id = 0;
for(i=0;i<n;i++)
for(j=0;toBeCovered[i][j];j++)
{
adj[i][j].clear();
addtoTrie(root,i,j,j);
}
// printf("build graph ok \n");
}
void initialize_pheromone()
{
int i,j,k;
for(i=0;i<n;i++)
for(j=0;toBeCovered[i][j];j++)
{
for(k=0;k<adj[i][j].size();k++)
{
adj[i][j][k].init(k+1);
all_node[adj[i][j][k].substr_idx] = adj[i][j][k];
}
}
// printf("initialze pheromone ok \n");
}
/**********************************************/
// may be useful for L-cover
int mark_now;
int target_is_cover; // idx of target string for is_cover
// target_idx from to
char dp_is_cover[T][M][M]; // is it possible to cover [from, to] within a finite cost?
int is_cover(int from, int to)
{
if(to-from+1 < min_allowed_substr_length)
{
dp_is_cover[target_is_cover][from][to] = mark_now - 1;
return dp_is_cover[target_is_cover][from][to];
}
if(to-from+1 <= max_allowed_substr_length)
{
dp_is_cover[target_is_cover][from][to] = mark_now;
return dp_is_cover[target_is_cover][from][to];
}
if(dp_is_cover[target_is_cover][from][to] >= mark_now - 1)
return dp_is_cover[target_is_cover][from][to];
int i, vv;
dp_is_cover[target_is_cover][from][to] = mark_now - 1;
for(i = from + min_allowed_substr_length - 1; i < to; i++)
{
if( i - from + 1 > max_allowed_substr_length)
continue;
vv = is_cover(i+1,to);
if( vv == mark_now)
{
dp_is_cover[target_is_cover][from][to] = mark_now;
break;
}
}
return dp_is_cover[target_is_cover][from][to];
}
void calc_is_cover(void)
{
mark_now += 2;
int i,j,k,ffff;
for(i = 0; i < n; i++)
{
target_is_cover = i;
for(j = 0; toBeCovered[i][j]; j++)
for(k = j; toBeCovered[i][k];k++)
{
// dp_is_cover[i][j][k] = -1;
ffff = is_cover(j,k);
}
}
}
/******************************************/
void visitTrie(trie *now,int i,int j,int pos)
{
// if(pos-j+1>13)
// return;
if(!toBeCovered[i][pos])
return;
int v = toBeCovered[i][pos];
adj[i][j][pos-j].eta1 = sub_freq[now->next[v]->val]/(double)(id+0.0);
adj[i][j][pos-j].eta2 = sub_freq_target[now->next[v]->val]/(double)(n+0.0);
if(sub_freq_target[now->next[v]->val] == n)
max_len_in_all = MAX(max_len_in_all,pos-j+1);
visitTrie(now->next[v],i,j,pos+1);
}
void calc_eta()
{
max_len_in_all = 0;
int i, j;
for(i=0;i<n;i++)
for(j=0;toBeCovered[i][j];j++)
visitTrie(root,i,j,j);
}
int run, ant;
int select_jump(int target_idx,int pos,int flag,int interval_count)
{
// printf("select jump enter \n");
if(interval_count == (L-1))
return (target_length[target_idx] - 1);
if(target_length[target_idx] - pos <= 2*min_allowed_substr_length)
return (target_length[target_idx] - 1);
int i, ret_idx;
double sum_heu = 0, max_prob = -1;
for(i = 0; i < adj[target_idx][pos].size(); i++)
{
if(fabs(adj[target_idx][pos][i].cost - inf) < 1e-5)
continue;
if(toBeCovered[target_idx][pos+i+1] && dp_is_cover[target_idx][pos+i+1][target_length[target_idx]-1]==(mark_now - 1))
continue;
double now_pheromone = adj[target_idx][pos][i].pheromone - minus_pheromone;
double tabu_factor = 1.0 - Tabu_prob * (sub_tabu[ adj[target_idx][pos][i].substr_idx ] == tabu_active);
/* if(flag)
{
now_pheromone = MAX(t_min,now_pheromone);
now_pheromone = MIN(t_max,now_pheromone);
} */
sum_heu += ( pow(now_pheromone, alpha) * pow(adj[target_idx][pos][i].eta, beta) * tabu_factor);
}
for(i = min_allowed_substr_length - 1; i < adj[target_idx][pos].size(); i++)
{
if(fabs(adj[target_idx][pos][i].cost - inf) < 1e-5)
{
adj[target_idx][pos][i].cum_prob = adj[target_idx][pos][i-1].cum_prob;
continue;
}
if(toBeCovered[target_idx][pos+i+1] && dp_is_cover[target_idx][pos+i+1][target_length[target_idx]-1]==(mark_now - 1))
{
adj[target_idx][pos][i].cum_prob = adj[target_idx][pos][i-1].cum_prob;
continue;
}
double now_pheromone = adj[target_idx][pos][i].pheromone - minus_pheromone;
double tabu_factor = 1.0 - Tabu_prob * (sub_tabu[ adj[target_idx][pos][i].substr_idx ] == tabu_active);
/* if(flag)
{
now_pheromone = MAX(t_min,now_pheromone);
now_pheromone = MIN(t_max,now_pheromone);
}*/
double neumerator = pow(now_pheromone, alpha) * pow(adj[target_idx][pos][i].eta, beta) * tabu_factor;
adj[target_idx][pos][i].probability = neumerator / sum_heu;
if(adj[target_idx][pos][i].probability > max_prob)
max_prob = adj[target_idx][pos][i].probability,
ret_idx = i + pos;
if(i == min_allowed_substr_length - 1)
adj[target_idx][pos][i].cum_prob = adj[target_idx][pos][i].probability;
else
adj[target_idx][pos][i].cum_prob = adj[target_idx][pos][i].probability + adj[target_idx][pos][i-1].cum_prob;
}
//int seed;
//seed = (long int) time(NULL);
if(flag%2 == 0)
{
double q = ran01(&seed);
if(q < q0)
return ret_idx;
}
double random_select = ran01(&seed);
for(i=0;i<adj[target_idx][pos].size();i++)
{
if(fabs(adj[target_idx][pos][i].cost - inf) < 1e-5)
continue;
if(toBeCovered[target_idx][pos+i+1] && dp_is_cover[target_idx][pos+i+1][target_length[target_idx]-1]==(mark_now - 1))
continue;
if(adj[target_idx][pos][i].cum_prob >= (random_select - 1e-12) )
return i+pos;
}
}
int select_backjump(int target_idx,int pos,int flag,int interval_count)
{
if(interval_count == (L-1))
return 0;
if(pos + 1 <= 2*min_allowed_substr_length)
return 0;
int i, ret_idx;
double sum_heu = 0, max_prob = -1;
for(i = pos; i >= 0 ; i--)
{
if(fabs(adj[target_idx][i][pos - i].cost - inf) < 1e-5)
continue;
if(i && dp_is_cover[target_idx][0][i-1]==(mark_now - 1))
continue;
double now_pheromone = adj[target_idx][i][pos - i].pheromone - minus_pheromone;
double tabu_factor = 1.0 - Tabu_prob * (sub_tabu[ adj[target_idx][i][pos - i].substr_idx ] == tabu_active);
sum_heu += ( pow(now_pheromone, alpha) * pow(adj[target_idx][i][pos - i].eta, beta) * tabu_factor);
}
for(i = pos; i >= 0 ; i--)
{
if(fabs(adj[target_idx][i][pos - i].cost - inf) < 1e-5)
continue;
if(i && dp_is_cover[target_idx][0][i-1]==(mark_now - 1))
continue;
double now_pheromone = adj[target_idx][i][pos - i].pheromone - minus_pheromone;
double tabu_factor = 1.0 - Tabu_prob * (sub_tabu[ adj[target_idx][i][pos - i].substr_idx ] == tabu_active);
double numerator = ( pow(now_pheromone, alpha) * pow(adj[target_idx][i][pos - i].eta, beta) * tabu_factor);
adj[target_idx][i][pos - i].probability = numerator/sum_heu;
if(adj[target_idx][i][pos - i].probability > max_prob)
{
max_prob = adj[target_idx][i][pos - i].probability;
ret_idx = i;
}
if(pos - i + 1 == min_allowed_substr_length)
adj[target_idx][i][pos - i].cum_prob = adj[target_idx][i][pos - i].probability;
else
adj[target_idx][i][pos - i].cum_prob = adj[target_idx][i+1][pos - i - 1].cum_prob + adj[target_idx][i][pos - i].probability;
}
if(flag%2 == 0)
{
double q = ran01(&seed);
if(q < q0)
return ret_idx;
}
double random_select = ran01(&seed);
for(i = pos; i >= 0 ; i--)
{
if(fabs(adj[target_idx][i][pos - i].cost - inf) < 1e-5)
continue;
if(i && dp_is_cover[target_idx][0][i-1]==(mark_now - 1))
continue;
if(adj[target_idx][i][pos - i].cum_prob >= random_select - 1e-12)
return i;
}
return ret_idx;
}
int construction_failure; //not used
void construction(int ant, int flag)
{
// printf("construction enter \n");
//int seed;
//seed = (int) time(NULL);
int start_target = (int)(ran01(&seed)*n);
start_target %= n;
int i, pos;
current.init();
for(i = start_target;;)
{
if(rand()%2)
{
current.jumps.push_back(make_pair(i,0));
pos = 0;
int interval_count = 0; //can not be greater than L for L-cover
while(toBeCovered[i][pos])
{
int k = select_jump(i,pos,flag,interval_count);
// printf("select jump ok \n");
current.substr_list.insert(adj[i][pos][k-pos].substr_idx);
current.jumps.push_back(make_pair(i,k+1));
pos = k+1;
interval_count++;
}
}
else
{
vector< pair<int,int> > tempv;
pos = target_length[i] - 1;
tempv.push_back(make_pair(i,pos+1));
int interval_count = 0; //can not be greater than L for L-cover
while(pos>=0)
{
int k = select_backjump(i,pos,flag,interval_count);
current.substr_list.insert(adj[i][k][pos-k].substr_idx);
tempv.push_back(make_pair(i,k));
pos = k-1;
interval_count++;
}
reverse(tempv.begin(),tempv.end());
for(int k = 0; k < tempv.size(); k++)
current.jumps.push_back(tempv[k]);
}
i = (i+1)%n;
if(i==start_target)
break;
}
current.calc_cost();
// printf("construntion ok \n");
}
void backward_construction(int ant, int flag)
{
}
void update_pheromone(int flag, solution got) //need to modify according to flag
{
// printf("update pheromone enter\n");
int i, j, k;
double k1;
// fixing t_max and t_min for the solution we got here
double tmax_d = evaporation_rate * got.cost;
t_max = 1.0/tmax_d;
k1 = m/2.0; // max length of string/2 -> average length jump
double p_dec = pow(p_best,(double) 1.0/(double)m);
double tmin_d = (k1-1)*p_dec;
t_min = t_max*(1-p_dec)/tmin_d;
// evaporate
for(i=0;i<n;i++)
for(j=0;toBeCovered[i][j];j++)
for(k = 0;k<adj[i][j].size();k++)
{
adj[i][j][k].pheromone *= (1 - evaporation_rate);
adj[i][j][k].pheromone = MAX(adj[i][j][k].pheromone, t_min);
adj[i][j][k].pheromone = MIN(adj[i][j][k].pheromone, t_max);
}
// increase pheromone
for(i=0;i<got.jumps.size();i++)
{
int uuu = got.jumps[i].first; //target string index
int vvv = got.jumps[i].second; //current position
if(!toBeCovered[ uuu ][ vvv ]) //reached end of this target string
continue;
if(i+1>=got.jumps.size())
continue;
j = got.jumps[i+1].second - 1;
//jump position from current position
//if(tabu_done)
//{
// adj[ uuu ][ vvv ][ j - vvv].pheromone -= evaporation_rate * (1.0/got.cost);
//}
//else
adj[ uuu ][ vvv ][ j - vvv].pheromone += evaporation_rate * (1.0/got.cost);
adj[ uuu ][ vvv ][ j - vvv].pheromone = MIN(adj[ uuu ][ vvv ][ j - vvv].pheromone, t_max);
adj[ uuu ][ vvv ][ j - vvv].pheromone = MAX(adj[ uuu ][ vvv ][ j - vvv].pheromone, t_min);
}
// printf("update pheromone ok \n");
}
void output_strings_best(int run)
{
output_best<<"Run "<<run<<endl;
int i;
/* for(i=0;i<global_best.jumps.size();i++)
{
int now_taget_idx = global_best.jumps[i].first;
if(i+1>=global_best.jumps.size() || global_best.jumps[i+1].first!=now_taget_idx)
{
output_best<<endl;
continue;
}
for(int j=global_best.jumps[i].second;j<global_best.jumps[i+1].second;j++)
output_best<<toBeCovered[now_taget_idx][j];
output_best<<" ";
}*/
output_best<<"Solution Set"<<endl;
vector<int> idx_list(global_best.substr_list.begin(),global_best.substr_list.end());
for(i=0;i<idx_list.size();i++)
{
int now_idx = idx_list[i];
int target_now = sub_start[now_idx].first;
for(int j = sub_start[now_idx].second; j<= sub_end[now_idx].second; j++)
output_best<<toBeCovered[target_now][j];
output_best<<endl;
}
}
solution local_search(solution got)
{
int tweak = n;
solution best_local;
best_local.cost = 1000000000;
while(tweak--)
{
solution temp = got;
int no_remove = 10;
while(no_remove--)
{
int target = (int)(ran01(&seed)*n);
target %= n;
int i = 0;
while(temp.jumps[i].first != target)
i++;
int no_partition = 0, j = i+1;
while(j < temp.jumps.size() && temp.jumps[j].first==target)
no_partition++,j++;
int remove_idx = (int)(ran01(&seed)*no_partition);
remove_idx %= no_partition;
if(remove_idx == 0 || remove_idx == no_partition)
{
no_remove++;
continue;
}
temp.jumps.erase(temp.jumps.begin()+i+remove_idx);
temp.substr_list.clear();
for(i=0;i<temp.jumps.size();i++)
{
if(i+1>=temp.jumps.size())
continue;
if(!toBeCovered[temp.jumps[i].first][temp.jumps[i].second])
continue;
j = temp.jumps[i+1].second - 1 - temp.jumps[i].second;
temp.substr_list.insert(adj[temp.jumps[i].first][temp.jumps[i].second][j].substr_idx);
}
temp.calc_cost();
if(temp.cost<best_local.cost)
best_local = temp;
}
}
return best_local;
}
/*
// for sorting strings according to size, then alphabetical order
bool comp(string founda,string foundb)
{
if(founda.size() == foundb.size())
return founda < foundb;
return founda.size() < foundb.size();
}
*/
// for sorting idx_list according to eta
bool comp_substring_eta(int id1, int id2)
{
return all_node[id1].eta < all_node[id2].eta;
}
void mark_tabu2(void)
{
vector<int> idx_list(global_best.substr_list.begin(),global_best.substr_list.end());
sort(idx_list.begin(), idx_list.end(), comp_substring_eta);
int to_be_tabu = idx_list.size()/3, i;
for(i = 0; i < to_be_tabu; i++)
sub_tabu[ idx_list[i] ] = tabu_active;
}
bool comp_substring_pheromone(int id1, int id2)
{
return all_node[id1].pheromone > all_node[id2].pheromone;
}
void mark_tabu3(void)
{
vector<int> idx_list(global_best.substr_list.begin(),global_best.substr_list.end());
sort(idx_list.begin(), idx_list.end(), comp_substring_pheromone);
int to_be_tabu = idx_list.size(), i;
for(i = 0; i < to_be_tabu; i++)
sub_tabu[ idx_list[i] ] = tabu_active;
}
void mark_tabu(void)
{
vector<int> idx_list(global_best.substr_list.begin(),global_best.substr_list.end());
vector<string> string_list;
int i,j;
for(i = 0; i < idx_list.size(); i++)
{
int temp_idx = idx_list[i];
int target_idx = sub_start[temp_idx].first;
char temp_s[1000];
for(j = sub_start[temp_idx].second; j <= sub_end[temp_idx].second; j++)
temp_s[ j - sub_start[temp_idx].second ] = toBeCovered[target_idx][j];
temp_s[ j - sub_start[temp_idx].second ] = 0;
string_list.push_back(temp_s);
}
// sort korle accordingly idx_list o update korte hobe.
// sort(string_list.begin(),string_list.end(),comp());
int cnt_tabu = 0;
for(i = 0; i < string_list.size(); i++)
for(j = 0; j < string_list.size(); j++)
{
if(j == i)
continue;
if(string_list[i].size() == 1)
continue;
int vvv = (int)string_list[j].find(string_list[i]);
if(vvv != -1) // found i in j
{
// if(rand()%2)
// continue;
if(rand()%5)
sub_tabu[ idx_list[i] ] = tabu_active; // tabu it
else
sub_tabu[ idx_list[j] ] = tabu_active;
cnt_tabu++;
}
}
if(cnt_tabu <= idx_list.size()/5)
mark_tabu2();
}
void ACO(int flag) // flag - 0 - ACS, 1 - MMAS, 2 - Hybrid
{
calc_eta();
initialize_pheromone();
calc_is_cover();
int iter,iter_best;
double best_time;
for(run = 1; run <= MAX_RUN; run++)
{
/* minus_pheromone = 0.0; -> not used */
tabu_done = 0;
global_best.cost = 100000000;
double st_time = time(NULL);
int idx_fgb = 0;
initialize_pheromone();
iter = 0;
int no_change = 0;
int last_tabu_on = 0;
int local_best_all = 100000000;
while(1)
{
local_best.cost = 100000000;
for(ant = 1; ant <= POPULATION_SIZE; ant++)
{
srand(iter*iter + rand()%100);
construction(ant, flag);
// solution from_local = local_search(current);
// if(from_local.cost < current.cost)
// current = from_local;
// printf("%lf\n",current.cost);
if(current.cost<local_best.cost)
local_best = current;
// if(flag == 0) // for ACS
// update_pheromone(flag);
}
if(local_best.cost == local_best_all)
no_change++;
else{
local_best_all = local_best.cost;
no_change = 0;
}
/*
if(rand()%7 == 0)
{
solution from_local = local_search(local_best);
if(from_local.cost < local_best.cost)
local_best = from_local;
}
*/
if(local_best.cost < global_best.cost)
{
//solution from_local = local_search(local_best);
//if(from_local.cost < local_best.cost)
// local_best = from_local;
global_best = local_best;
double nd_time = time(NULL);
double elapsed = (nd_time - st_time);
iter_best = iter;
best_time = elapsed;
//no_change = 0;
}
//else
// no_change++;
//schedule for tabu
if(tabu_done > 0)
tabu_done++;
/* if((no_change > NO_UPDATE/4) && (tabu_done==0) && ((iter - last_tabu_on) > NO_UPDATE/4))
{
printf("here tabu on iteration %d\n tabu_idx %d\n",iter,tabu_active);
tabu_done = 1;
if(rand()%2 == 0)
mark_tabu();
//else
{
if(rand()%3 == 0)
mark_tabu2();
//else
mark_tabu3();
}
}
if(tabu_done > NO_UPDATE/2)
{
printf("here tabu off %d iteration %d\n",tabu_done,iter);
tabu_done = 0;
tabu_active++;
}
if(tabu_done)
last_tabu_on = iter;*/
// FOR both ACS and MMAS
// Scheduling
int fgb[] = {7,6,5,4,3,2,1};
int iter_fgb[] = {25,50,100,200,300,400,10000000};
/* if(iter > 120 && iter%50 == 0)
{
beta -= alpha;
if(beta < alpha)
beta = alpha + 1;
}*/
if(iter > iter_fgb[idx_fgb])
idx_fgb++;
if(iter%fgb[idx_fgb]==0 && iter>150)
update_pheromone(flag, global_best);
else
update_pheromone(flag, local_best);
iter++;
printf("iteration %d global_best %lf %d local_best %lf\n",iter,global_best.cost,global_best.substr_list.size(),local_best.cost);
if(no_change > NO_UPDATE)
{
// record
break;
}
double nd_time = time(NULL);
double elapsed = (nd_time - st_time);
if(elapsed > allowed_time)
{
// record
break;
}
}
output<<"Run "<<run<<endl;
output<<iter_best<<" "<<best_time<<" "<<global_best.substr_list.size()<<endl;
output_strings_best(run);
}
}
int readInput(int fileidx)
{
/*if(scanf("%d",&n)!=1) // number of target strings
return 0;*/
int i;
m = 0;
n = 10; //all set length 100
for(i=0;i<n;i++)
{
scanf("%s",toBeCovered[i]);
int v = strlen(toBeCovered[i]);
m = MAX(v,m);
target_length[i] = v;
}
sqrt_m = sqrt((double)m);
max_allowed_substr_length = m/2;
min_allowed_substr_length = 3;
return 1;
}
void parameterRead(int fileidx)
{
char str[55];
sprintf(str,"input\\param%.2d.txt",fileidx);
freopen(str,"r",stdin);
scanf("%lf%lf%lf",&alpha,&beta,&evaporation_rate);
scanf("%d",&L);
scanf("%lf",&allowed_time);
// fclose(fp);
}
void init_output_file(int fileidx)
{
char str[200];
sprintf(str,"output\\%s\\outputtest%.2d.txt",str_folder,fileidx);
output.open(str);
sprintf(str,"output\\%s\\outputbest%.2d.txt",str_folder,fileidx);
output_best.open(str);
}
int main()
{
int fileidx;
//scanf("%d",&fileidx);
char str_command[100];
strcpy(str_folder,"instances_10_a50_s2-10_l3-10_L50-100");
sprintf(str_command,"mkdir output\\%s",str_folder);
system(str_command);
for(fileidx = 2; fileidx <= 50; fileidx+=2)
{
//parameterRead(fileidx);
init_output_file(fileidx);
char str[200];
sprintf(str,"instances\\%s\\instance%.2d",str_folder,fileidx);
freopen(str,"r",stdin);
// while(readInput(fileidx))
{
readInput(fileidx);
buildGraph();
alpha = 5.0;
beta = 20.0;
evaporation_rate = 0.02;
L = 200;
allowed_time = 7200;
output<<"alpha "<<alpha<<" beta "<<beta<<" evaporation_rate "<<evaporation_rate<<" with tabu"<<endl;
output_best<<"alpha "<<alpha<<" beta "<<beta<<" evaporation_rate "<<evaporation_rate<<" with tabu"<<endl;
tabu_active++;
ACO(2);
/* beta += 0.5;
output<<"alpha "<<alpha<<"beta "<<beta<<"evaporation_rate "<<evaporation_rate<<endl;
output_best<<"alpha "<<alpha<<"beta "<<beta<<"evaporation_rate "<<evaporation_rate<<endl;
ACO(2);
evaporation_rate -= 0.005;
output<<"alpha "<<alpha<<"beta "<<beta<<"evaporation_rate "<<evaporation_rate<<endl;
output_best<<"alpha "<<alpha<<"beta "<<beta<<"evaporation_rate "<<evaporation_rate<<endl;
ACO(2);*/
}
output.close();
output_best.close();
}
return 0;
}