Thread: iterated greedy!!

  1. #61
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    for example, the function rmv_columns if it was sth like this:
    Code:
    void Solution::rmv_column(int i) {
    
    
    	selected_columns.erase(i)
        obj_value = obj_value - (instance->cost)[i];
    	is_added[i] = false;
        for (int j = 0; j < (instance->covers)[i].size(); j++) {
            int aRow = (instance->covers)[i][j];
              is_covered[aRow] = false;
    	}
    }
    the part selected_columns.erase(i) is not correct.Just to show.I want to erase that concret column

    and then use it in the code like this:
    Code:
    for ( int i = 0; i < aSol->selected_columns.size()/2; i++){
            aSol-> rmv_column(i);
    }
    u think it would work??

  2. #62
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Your idea to use selected_columns.erase(i) seems like a good idea to me. How is it working?

    One possible problem is that you are erasing from the selected_columns vector at the same time as you are looping through it. This might make your loop code skip over some objects and not remove half of the columns.

    Another possible problem, which I think might be worse, is that random_shuffle is shuffling the columns inside selected_columns, but not inside instance->cost, instance->covers, and your other variables. So after calling random_shuffle the columns inside selected_columns don't match the ones in the other variables. I don't know if this is a problem or not, but it might cause you weird output.

  3. #63
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    Ok. i will explain. You have seen my final code.
    Code:
    start:
     
      int not_covered;
      for (int n=1; n <= num_trials; n++){
    
    	while (!aSol -> is_complete()) {
    	  for (int i = 0; i < instance -> n_cols ; i++) {
    			  if(aSol -> is_added[i]){
    				  k[i] = -1;}
    			  
    			  else{
    				  not_covered = 0;
    				  for (int j = 0; j < (instance->covers)[i].size(); j++) {
                           int aRow = (instance->covers)[i][j];
                              if (!aSol -> is_covered[aRow]) {
    							 // cout<<"not covered "<<endl;
    							  not_covered++;
    						  }
    						  
    				  }
    				  k[i] = (double) (not_covered)*1000.0/(double) (instance -> cost[i]);
    			  }  
    	  }
              aSol -> add_column(GetMax(k,instance->n_cols));
              
    	}
               
              //cout << " value " << aSol->value() <<" trial " << num_trials << "\ttime " << timer.elapsed_time(Timer::VIRTUAL) << endl;
    }
       cout << " value " << aSol->value() << endl;  
       random_shuffle (aSol -> selected_columns.begin(), aSol -> selected_columns.end() );
       
      aSol -> selected_columns.erase ( aSol -> selected_columns.begin(),aSol -> selected_columns.begin() + aSol -> selected_columns.size()/2  );
      cout << " value " << aSol->value() << endl;
      if (!aSol-> is_complete())
      goto start;
    What i want to do, is when find a solution does the shuffle( maybe it is not right), erase the half of the columns and repeat until it finds a new solution. Just to check i put these two cout and i see that gives me the same value( as you said also ).So that erase or shuffle or both DO not do anything.

    Any suggestion for these??
    First: should i skip totally el shuffle?
    The first you said i don't understand really well. How it should be?

    Ok..If i also comment shuffle it stils give me the same output.That means for some weird reason no erase columns.The selected_columns is defines into void Solution::add_column()
    Last edited by joan; 12-11-2006 at 12:26 PM.

  4. #64
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    I thought you were using rmv_column? I think the rmv_column idea was a better idea. Did you try that?

  5. #65
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    Yes, but i don't know how to write it.As you see above. I don't know how to express the selected_columns.???? part. if i do for example selected_columns.pop_back() it just gives me smaller values ( subtracting the last column of the set and nothing else ). I think it would work but as i said i don't know how to write it -> when i erase a column from the set (selected_columns ) this to have effect in all my variables. You understand me?
    This is why not working erase?? You see anything wrong in the code?? the goto part u think it's good?
    i really thought that i had it done.. :-(
    Last edited by joan; 12-11-2006 at 12:39 PM.

  6. #66
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    I thought this code looked good:
    Code:
    void Solution::rmv_column(int i) {
    
    
    	selected_columns.erase(i);
        obj_value = obj_value - (instance->cost)[i];
    	is_added[i] = false;
        for (int j = 0; j < (instance->covers)[i].size(); j++) {
            int aRow = (instance->covers)[i][j];
              is_covered[aRow] = false;
    	}
    }
    You need a semi-colon, but otherwise I don't see why it wouldn't work. Did you try it?

    >> the goto part u think it's good?
    No, I think goto is not a good idea, but if it works, now is not the time to change it. Leave the goto there and focus on the stuff that is not working.

  7. #67
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    I don't know if that expression >>selected_columns.erase(i); is correct. Because i look at the definition of erase and it is not quite like this.Also when i compile it like this i get an error for this: no matching function for call to 'std::vector<int, std::allocator<int> >::erase(int&)'

    I tried instead of that this one:
    Code:
    selected_columns.erase(selected_columns.begin()+ (i-1),selected_columns.begin()+ i);
    to erase the column of the position i. I'm not sure if is the same thing.Erase the column from the position i and erase the column i. i compileit and it is correct. But the problem that i told you before remains.Just calculates values which are decreasing..I don't know if is a problem of the loops..
    Last edited by joan; 12-11-2006 at 01:27 PM.

  8. #68
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    You're right. Use this:
    Code:
    selected_columns.erase(selected_columns.begin()+ i);

  9. #69
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    I really don't know if it works or not. In the first iteration i get a value that it is close to the optimal solution.In the other steps i get smaller and smaller values until one that is the smallest and after this one are repeated.Is this a solution?? i don't know if it's normal or it is because of the algorithm. Wouldn't it be supposed to get better solutions after each step or not? I'm just asking because i don't know really much about algorithms.With this line that you send me it works, but as i just described you.But looking at the void::rmv_column, erasing that column has effect in all the other variables,no? So, typically is correct. Is it a fault of the code(loops or sth)? I would like to know your opinion
    And by the way the final code
    Code:
    int not_covered;
      for (int n=1; n <= num_trials; n++){
    
    	  while (!aSol -> is_complete()) {
    	  for (int i = 0; i < instance -> n_cols ; i++) {
    			  if(aSol -> is_added[i]){
    				  k[i] = -1;}
    			  
    			  else{
    				  not_covered = 0;
    				  for (int j = 0; j < (instance->covers)[i].size(); j++) {
                           int aRow = (instance->covers)[i][j];
                              if (!aSol -> is_covered[aRow]) {
    							 // cout<<"not covered "<<endl;
    							  not_covered++;
    						  }
    						  
    				  }
    				  k[i] = (double) (not_covered)*1000.0/(double) (instance -> cost[i]);
    			  }  
    	  }
              aSol -> add_column(GetMax(k,instance->n_cols));
              
    	}
               
           cout << " value " << aSol->value() <<" trial " << num_trials << "\ttime " << timer.elapsed_time(Timer::VIRTUAL) << endl;
    
      
       //random_shuffle (aSol -> selected_columns.begin(), aSol -> selected_columns.end() );
       
       //aSol -> selected_columns.erase ( aSol -> selected_columns.begin(),aSol -> selected_columns.begin() + aSol -> selected_columns.size()/2  );
       for ( int i = 0; i< aSol->selected_columns.size()/2; i++){
    	   aSol-> rmv_column(i);
       }
      }

  10. #70
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    also, if you have time to look it.. the algorithm has as inputs -i ( the instances) -t time and -n the number of trials. i have defined all these as:
    Code:
    void read_parameters(int argc, char **argv)
    {
      int iarg=1;
    
      while (iarg < argc) {
        if (strcmp(argv[iarg],"-i")==0) {
          inputFile = argv[++iarg];
        }
        if (strcmp(argv[iarg],"-t")==0) {
          tmax = atoi(argv[++iarg]);
        }
        if (strcmp(argv[iarg],"-n")==0) {
          num_trials = atoi(argv[++iarg]);
    	}
        iarg++;
      }
    }
    But i dont know how to write, make a loop maybe so that in every trial it gives me the value, #of this trial and the time to compute this value. Because if i write to run for example:

    ./ig.exe -i instances/scp51.txt -t ( this must me the maximum time i want to put for the iteration) -n 5 it gives me sth like this:
    Code:
    value 289       trial 5           time  0.157 
    value 256       trial 5           time  0.157 
    value 239       trial 5           time  0.157 
    value 228       trial 5           time  0.157 
    value 220       trial 5           time  0.157

  11. #71
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> I would like to know your opinion
    I honestly don't know. I don't understand the part of the algorithm that calls for removing half of the columns at random and starting over. Unfortunately I don't have much time right now to look at it, so I'll just have to wish you luck. Good Luck.

  12. #72
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    Ok..if sometime you could look at look at it..

    anyway thanx for all again

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Finding the iterated type
    By QuestionC in forum C++ Programming
    Replies: 1
    Last Post: 04-27-2007, 10:51 AM
  2. ITERATED GREEDY ALGORITHM. Help!!
    By joan in forum C++ Programming
    Replies: 0
    Last Post: 12-05-2006, 12:45 PM
  3. Is Kazaa being greedy?
    By minesweeper in forum A Brief History of Cprogramming.com
    Replies: 29
    Last Post: 11-05-2002, 04:39 PM