iterated greedy!!

This is a discussion on iterated greedy!! within the C++ Programming forums, part of the General Programming Boards category; >> what do u mean i changed the return value? You changed the return value of the GetMax function from ...

  1. #31
    Registered User
    Join Date
    Jan 2005
    Posts
    7,318
    >> what do u mean i changed the return value?
    You changed the return value of the GetMax function from int to double.

    >> the return value represents the corresponding index of the biggest element(column in this case) of the set with the columns we add
    Right, and what type is used for the index (column in this case)? int or double?

    >> the warning is:
    That warning will be fixed when you fix the return type of GetMax.


    >> i added the map is_added when we add a column.I also inculded it to the header file
    >> A little change.I didn't want to do, cause these are ready given.

    You don't have to add is_added to the header. You can just add it to the main program code. Instead of adding the column to this map inside of add_column, you can just add the column to the map in the main program after the code aSol->add_column(GetMax(k,instance->n_cols));.


    >> if (!aSol -> is_added[i]){
    Good. This will still work if you declare the is_added map next to the k array instead of in the header.


    So, for the steps a), b), c) and d) I had above, here is where you are from what I see:

    a) You have to fix the return type of GetMax as I mentioned above. This will fix the warning as well. I hope you are allowed to change the GetMax function from the assignment.

    b) You did good by using the is_added map. You have to remove that from the header since you are not supposed to change the header, and declare it inside the main program code.
    You are only half done, though. You also have to prevent the GetMax function from accidentally choosing a column that has already been added. I already gave one idea for how to do this: if is_added[i] is true, then set k[i] to -1. That way it will never be Max. This will only work if the numbers are always positive numbers.

    c) Still have to do.
    d) Still have to do.

  2. #32
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    You are right..i changed by accident the return value of GetMax. Now, it works fine, without warning. Yes, i'm allowed to change it..This is a function i wrote.
    There is no restriction(i hope its the right word) to change the headers.I didn't want to, in case i would have problems.

    OK!! now i have to work with c and d

  3. #33
    Registered User
    Join Date
    Jan 2005
    Posts
    7,318
    Great.

    Did you finish the second half of b)?

  4. #34
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    Yes..
    Here is the code by now
    Code:
    Solution* aSol = new Solution(instance);
      
      SC_instance* covers;
      Solution* selected_columns;
      double k[5000];
      while (!aSol -> is_complete()) {
    	  for (int i = 0; i < instance -> n_cols ; i++) {
    		  if (!aSol -> is_added[i]){
    			  if(aSol -> is_added[i] = true ){
    				  k[i] = -1;
    			  }
    			  else{
    
    		  
    		   k[i] = (instance->covers[i].size())/(instance -> cost[i]);
    	  }
    	}  
    
    	  
    		  aSol -> add_column(GetMax(k,instance->n_cols));
      }
      }
    
      
       random_shuffle (aSol -> selected_columns.begin(), aSol -> selected_columns.end() );
    I compile it without error or warning

  5. #35
    Registered User
    Join Date
    Jan 2005
    Posts
    7,318
    Ooops. Look at it again. Here it is with easier to read indentation
    Code:
    if (!aSol -> is_added[i]){
    	if(aSol -> is_added[i] = true ){
    		k[i] = -1;
    	}
    	else{	  
    		k[i] = (instance->covers[i].size())/(instance -> cost[i]);
    	}
    }
    Look at those first two lines.

  6. #36
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    Ok..I think that this is the right
    Code:
    Solution* aSol = new Solution(instance);
      
      SC_instance* covers;
      Solution* selected_columns;
      double k[5000];
      while (!aSol -> is_complete()) {
    	  for (int i = 0; i < instance -> n_cols ; i++) {
    			  if(aSol -> is_added[i] = true ){
    				  k[i] = -1;}
    			  
    			  else{
    
    		  
    		   k[i] = (instance->covers[i].size())/(instance -> cost[i]);
    	  
    			  }  
    
    	  
    		  aSol -> add_column(GetMax(k,instance->n_cols));
    	  }
      }
    
      
       random_shuffle (aSol -> selected_columns.begin(), aSol -> selected_columns.end() );

  7. #37
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    It is the first time i work with this..removing randomly elements from an array..I keep searching in internet but i haven't really found what i want ( not exactly, even more or less).

    My first attempt is this one
    Code:
    random_shuffle (aSol -> selected_columns.begin(), aSol -> selected_columns.end() );
    
       delete ( aSol -> selected_columns.size() / 2 );
    i get an error for the second line:
    type 'usigned int' argument given to 'delete', expected pointer..

    I dont'know if i'm at the right way.You suggest me to use another command of delete. If no, how would u suggest me to use it?

  8. #38
    Registered User
    Join Date
    Jan 2005
    Posts
    7,318
    >> Ok..I think that this is the right
    Almost. There is a typo (= should be ==). I would just remove the entire "= true" part and leave it as
    Code:
    if(aSol -> is_added[i]){
    And I just noticed that the call to add_column is inside the for loop. It should be after the for loop, because you only want to add a column after you calculate all the k values, and the k values are all calculated by the for loop.

    >> You suggest me to use another command of delete. If no, how would u suggest me to use it?
    You would use erase, not delete, but before you use that method you have to answer this question:

    Is it ok that random_shuffle changes the order of the data inside aSol->selected_columns?





    Anyway, here are my ideas to help you with part c).

    I would create a new function. This function would be called to calculate k for a given index i. This will make it a little less confusing to read and fix the code. So your code above would look like this:
    Code:
      double k[5000];
      while (!aSol -> is_complete()) {
    	  for (int i = 0; i < instance -> n_cols ; i++) {
    			  if(aSol -> is_added[i]){
    				  k[i] = -1;
    			  }
    			  else{
    				  k[i] = CalculateKValue(instance, i);
    			  }
    	  }
    	  aSol -> add_column(GetMax(k,instance->n_cols));
    }
    So in that function you have to calculate k. The value k is calculated as the number of rows that are covered by the current column, minus the number of rows that have already been covered by columns added to the solution, dividing all of that by the cost. So, I would loop through instance->covers[i], and check each row in that vector to see if it is in the is_covered map. If it is, then skip it, otherwise increment your count. Then divide all of that by the cost when you are done.

    See if you understand what I'm saying, and if you think that will work. Don't write any code yet (except maybe an empty function). Start by writing out in pseudo code how that CalculateKValue function would work. If you can do that, then it will be easy to translate it into code. When I say pseudo code, I mean like I did earlier like this:
    - While solution is not complete:
    - - For current_column = 0 to num columns:
    - - - If current column has not already been added to the solution:
    - - - - Calculate k for current column and assign it to k[current_col].
    - - - End If
    - - End For
    - - Find the column with the largest value in k, not counting columns already added to the solution.
    - - Add that column to the solution.
    - End while

  9. #39
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    I will try to understand it good and then see if it works..

    Only sth that is the key.When you say >> minus the number of rows that have already been covered by columns added to the solution.

    Not any rows in general..Rows that have been already covered by columns added to the solution AND at the same time are covered by the current column. I hope that u mean that, because u didn't write. If u don't then is different what u say..

    Thanx

  10. #40
    Registered User
    Join Date
    Jan 2005
    Posts
    7,318
    That is what I meant.

  11. #41
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    Ok.. I think i have understand what u are trying to say.

    But really, i don't know how to make the function( what parameters to use, etc..).It is quite complicated.

    One question: the >> rows that have already been covered by columns added to the solution would be this count increments every time the row is not in the is_covered map??

    and second, i would use the same index i ?? i will try to make an inner loop
    Last edited by joan; 12-08-2006 at 04:08 AM.

  12. #42
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    i have write this code, but i have many errors. I will try to figuer out what's goin on. If any time you are online and see it, say to me what u see wrong!! As you see below i have mess a little up things.Here u are:
    Code:
    Solution* selected_columns;
      Solution* n_covered;
      Solution* is_covered;
    
      double k[5000];
      while (!aSol -> is_complete()) {
    	  for (int i = 0; i < instance -> n_cols ; i++) {
    			  if(aSol -> is_added[i]){
    				  k[i] = -1;}
    			  
    			  else{	
    				  for (int j = 0; j < (instance->covers)[i].size(); j++) {
                                                             int aRow = (instance->covers)[i][j];
                                                                             if (!aSol -> is_covered[aRow]) {
    							                   n_covered++;
    						               }
    						  
    				  }
    		          k[i] = ((instance->covers[i].size()) - (instance -> covered_by[j][i].size()))/(instance -> cost[i]);
    	  
    			  }  
    	  }
              aSol -> add_column(GetMax(k,instance->n_cols));
      }
    
      
       random_shuffle (aSol -> selected_columns.begin(), aSol -> selected_columns.end() );
    
       erase ( aSol -> selected_columns.size() / 2 );
    i get 2 errors(also for erase,but this will look after) for the line
    Code:
     k[i] = ((instance->covers[i].size()) - (instance -> covered_by[j][i].size()))/(instance -> cost[i]);
    1) request for member 'size' ......
    2)name lookup of 'j' changed for new ISO 'for' scoping

    and one error for the line
    Code:
    for (int j = 0; j < (instance->covers)[i].size(); j++) {
    1)using obsolete binding at 'j'

    Maybe i didn't understand that well.Also i don't know what do these errors mean.. :-(
    Last edited by joan; 12-08-2006 at 06:12 AM.

  13. #43
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    Ok..i think the mistake is that the term
    Code:
     (instance -> covered_by[j][i].size())
    indicates the number of columns that cover the j row.So i cannot make this..It has no sense.

    I will try to find the right term

  14. #44
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    Look at this code. Compiling it i get no error(well it's sth). Except for the errors i get for the erase function. I don't really understand if it works. Please, if you can, tell me so. Please..
    here it is:
    Code:
    Solution* aSol = new Solution(instance);
      
      //SC_instance* covers;
      Solution* selected_columns;
      Solution* n_covered;
      Solution* is_covered;
    
      double k[5000];
      while (!aSol -> is_complete()) {
    	  for (int i = 0; i < instance -> n_cols ; i++) {
    			  if(aSol -> is_added[i]){
    				  k[i] = -1;}
    			  
    			  else{	
    				  for (int j = 0; j < (instance->covers)[i].size(); j++) {
                           int aRow = (instance->covers)[i][j];
                              if (!aSol -> is_covered[aRow]) {
    							  n_covered++;
    							  //is_covered[aRow] = true;
    						  }
    						  
    				  
    		          k[i] = ((instance->covers[i].size()) - (instance -> covers[j].size()))/(instance -> cost[i]);
    				  }
    			  }  
    	  }
              aSol -> add_column(GetMax(k,instance->n_cols));
      }
    
      
       random_shuffle (aSol -> selected_columns.begin(), aSol -> selected_columns.end() );
    
       erase ( aSol -> selected_columns.size() / 2 );

  15. #45
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    Daved, if you are online at some point, please check this code. How does it seem to you?

    I have to give this project on Monday. I have finished with the rest of the code ( erase and repeat again for the half of the columns)..I still have doubts about why u say i shouldn't shuffle the set before i erase the half of it.

    Anyway, if u can please have a look

    Thanx a lot for everything

Page 3 of 5 FirstFirst 12345 LastLast
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, 11:45 AM
  3. Is Kazaa being greedy?
    By minesweeper in forum A Brief History of Cprogramming.com
    Replies: 29
    Last Post: 11-05-2002, 03:39 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21