iterated greedy!!

This is a discussion on iterated greedy!! within the C++ Programming forums, part of the General Programming Boards category; >> I still have doubts about why u say i shouldn't shuffle the set before i erase the half of ...

  1. #46
    Registered User
    Join Date
    Jan 2005
    Posts
    7,338
    >> I still have doubts about why u say i shouldn't shuffle the set before i erase the half of it.
    I'm not saying you should not shuffle. I am asking you a question that you have not yet answered. If you can answer the question, then I can try to give my opinion about whether random_shuffle is a good idea or not. If it is working for you now and you are ok with it, then that is fine. If it is not working for you, then answer this question: "Is it ok that the order of the data inside aSol->selected_columns changes? Are the columns in aSol->selected_columns supposed to be in a specific order?"

    Now, for your posted code, it is very hard to read mostly because the indentation is all messed up. It will help you to fix the indentation (if it looks that bad on your editor), and it will help me too.

    The only big thing I see wrong in that code is the k[i] = part. You need to re-do that entire equation. I think you implemented the n_covered count correctly. That is good. But you need to figure out how to use that in the calculation of k[i]. You also need to move the calculation of k[i] out of the for (int j = 0... loop, it should be done after you finish calculating n_covered.

    Does that make sense? I really think it would have helped if you had tried to follow my suggestions earlier, but I understand that each person does things in their own way. Hopefully this will help you understand the few small changes you have left to do.

  2. #47
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    Hi Daved..
    For your first question: I asked my profesor and he told me that it would be no problem removing some columns of the set( half of them would be nice) randomly.That means that the columns in the set not supposed to be in a specific order.(the order depends on the value of -> which column has the best and so we order them)
    So, i wrote this code that( for the moment, i don't know if it is correct because i don't know how to use random_shuffle and erase)
    Code:
    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  );
    I tried really to make a function as you advised me, but i couldn't.So i pick this way.I know it's not the best(easier).

    For the second thing.If i take k[i] out of the for(j = 0...) loop that is:
    Code:
    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));
      }
    i get 2 errors
    for the line
    Code:
     for (int j = 0; j < (instance->covers)[i].size(); j++) {
    error: using absolete binding at 'j'
    and for the line:
    Code:
    k[i] = ((instance->covers[i].size()) - (instance -> covers[j].size()))/(instance -> cost[i]);
    error:name lookup of 'j' changed for new ISO 'for' scoping

    I really don't understand what do these 2 errors mean. If i use somehow the n_covered count into the k[i] expression it will be solved??
    Last edited by joan; 12-09-2006 at 12:50 PM.

  3. #48
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,047
    Since you declared the variable j in the for loop initialization section, it should only be visible in the for loop itself. However, some old compilers made the variable visible throughout the remainder of the block, which is what your code is assuming. Your compiler is complaining about this, and rightly so.

    The solution: declare j before the for loop so that it's visible after the for loop.
    Code:
    int j;
    for(j = 0; /* ... */; /* ... */) {
    
    }
    /* ... */ covers[j] /* ... */;
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #49
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    Yes dwks..that works
    Thanx

  5. #50
    Registered User
    Join Date
    Jan 2005
    Posts
    7,338
    Code:
    k[i] = ((instance->covers[i].size()) - (instance -> covers[j].size()))/(instance -> cost[i]);
    Unfortunately, this line of code is wrong. The fix isn't to put j outside the loop, the fix is to fix that line of code. It shouldn't be using j at all.

    Have you figured out how to use the value of n_covered in the equation to calculate k[i]?


    As for the random_shuffle part, that is fine. "removing some columns of the set( half of them would be nice) randomly" is not the same as randomly shuffling the order of the columns, but if you think this is ok then I won't worry about it.

  6. #51
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    No Daved..this is the part i cannot write..In theory i know how it works(ok it's not that difficult)

    But i cannot express the term: "The rows that covers the current column - the rows that have been already covered and at the same time are covered by the current column"

    i know that simply write
    Code:
    k[i] = ((instance->covers[i].size()) - (n_covered) /(instance -> cost[i]);
    would be wrong. If you can give any hint( not tell me direct the code) i would thank very much.
    The last two days i'm working on this subject.( as i told u i'm quite a beginner in programming and although for some people this is easy, for me not)

    and when you say>>It shouldn't be using j at all, you mean that i should eliminate totally the for ( j = 0;......) loop??

    By the way, n_covered is already defined( as i just used it) like this:
    Code:
    void Solution::add_column(int i) {
    
      
      selected_columns.push_back(i);
      obj_value = obj_value + (instance->cost)[i];
      is_added[i] = true;
      for (int j = 0; j < (instance->covers)[i].size(); j++) {
        int aRow = (instance->covers)[i][j];
        if (!is_covered[aRow]) {
          n_covered++;
          is_covered[aRow] = true;
    }
    and also in the header file Solution.h
    Last edited by joan; 12-09-2006 at 01:59 PM.

  7. #52
    Registered User
    Join Date
    Jan 2005
    Posts
    7,338
    That's closer.

    What does n_covered represent? Feel free to use spanish to explain it if that is easier.

    >> when you say>>It shouldn't be using j at all, you mean that i should eliminate totally the for ( j = 0;......) loop??
    No. The for (int j = 0; ....) loop was good, it is exactly what I think should work to calculate n_covered. I just mean that you should not use j in the k[i] = ... line of code.

  8. #53
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    As you see in the definition of the Solution, n_covered is a count that it is increasing when a row is not covered. But still as i told u i cannot express in programming language the term
    >>the rows that have been already covered and at the same time are covered by the current column"
    Ok the previous to be correct from compilation view would be:
    Code:
    k[i] = ((instance->covers[i].size()) - (aSol -> n_covered) /(instance -> cost[i]));
    Last edited by joan; 12-09-2006 at 02:33 PM.

  9. #54
    Registered User
    Join Date
    Jan 2005
    Posts
    7,338
    My response was before I saw your edit.

    I do not think you should be using the same n_covered as you have inside add_column.

    The variable you call n_covered that you are using in post #47 should be an int variable that starts at 0 just before the for (int j = 0....) loop. It should be counting:

    "the rows that have not been already covered and at the same time are covered by the current column".

    That is exactly what it is doing in the code in post #47:
    Code:
    for (int j = 0; j < (instance->covers)[i].size(); j++) { // (1)
        int aRow = (instance->covers)[i][j];
        if (!aSol -> is_covered[aRow]) {// (2)
            n_covered++; // (3)
    That code goes for each row that the current column covers (1). It checks to see if the row is covered by a column already added to the solution (2). If it is not, then it increments n_covered (3).

    That is exactly what you want. Now you just have to use that value in the calculation of k.

  10. #55
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    If i understood well ( i'm not so sure) then it must be like this:
    Code:
    while (!aSol -> is_complete()) {
            for (int i = 0; i < instance -> n_cols ; i++) {
                if(aSol -> is_added[i]){
    				  k[i] = -1;}
    			  
    			  else{
    				  int not_covered = 0;
    				  for (int j = 0; j < (instance->covers)[i].size(); j++) {
                           int aRow = (instance->covers)[i][j];
                              if (!aSol -> is_covered[aRow]) {
    							  not_covered++;
    							  //is_covered[aRow] = true;
    						  }
    						  
    				  }
    		          k[i] = (not_covered) /(instance -> cost[i]);
    				  
    			  }  
    	  }
              aSol -> add_column(GetMax(k,instance->n_cols));
    		}
    Last edited by joan; 12-09-2006 at 03:11 PM.

  11. #56
    Registered User
    Join Date
    Jan 2005
    Posts
    7,338
    I just deleted my previous message.

    I think you've got it. And I am especially glad that you got it without having to read that message. Well done.

    Now go see if it works.

  12. #57
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    >>the number of rows covered by the current column but not by any other column added to the solution" divided by the cost. Isn't that right?
    Exactly..

    so by using
    Code:
    k[i] = (not_covered) /(instance -> cost[i]);
    we get what we want,no??

  13. #58
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    Ok. i'll try in action!!

    Just want to really really thank one more time..
    If it wasn't you to guide me, i simply wouldn't have done it :-)

    No sabia que hablas espanol

  14. #59
    Registered User
    Join Date
    Jan 2005
    Posts
    7,338
    >> Just want to really really thank one more time.
    I'm glad to help.

    >> No sabia que hablas espanol
    I don't, at least I haven't tried to in years. I just wanted you to try to explain it in your native language as a tool to help you understand, even if I didn't understand what you wrote. Writing or speaking what I am trying to do in English usually helps me understand it better so I can do it right, so I was thinking the same might work for you.

  15. #60
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    Hi everyone.
    I don't know how many of you have read this thread (apart from Daved) there are TOO many posts.Anyway, i have a problem( the last one).This last code:
    Code:
    int not_covered;
      for (int n=1; n <= NumberRuns; 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));
        }
       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  );
    gives me a first solution.Not the optimal but quite close to it.BUT it cannot compute another one because of this
    Code:
    aSol -> selected_columns.erase ( aSol -> selected_columns.begin(),aSol -> selected_columns.begin() + aSol -> selected_columns.size()/2  );
    . What this line do, is erase the columns of the solution,WITHOUT erasing the rows that they cover.That's why it cannot compute another solution. I want to erase the half of the columns and the rows that they cover. I thought of writing a function like this one:
    Code:
    void Solution::add_column(int i) {
    
      
      selected_columns.push_back(i);
      obj_value = obj_value + (instance->cost)[i];
      is_added[i] = true;
      for (int j = 0; j < (instance->covers)[i].size(); j++) {
        int aRow = (instance->covers)[i][j];
        if (!is_covered[aRow]) {
          n_covered++;
          is_covered[aRow] = true;
         }
      }
    }
    which will be called let's say rmv_column and it will do the opposite of add_column and then run it in a for loop for the half of the columns of the solution.But i don't know how it woud be the
    Code:
     selected_columns.push_back(i);
    part and if i should use also the erase function i already have and how..Or if you could suggest me another way,easier..This is the only thing it is left to do.
    Please any hint would be really really helpful..
    Last edited by joan; 12-11-2006 at 07:50 AM.

Page 4 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