iterated greedy!!

This is a discussion on iterated greedy!! within the C++ Programming forums, part of the General Programming Boards category; >> This i don't really understand This is what I was trying to explain earlier. You cannot add a column ...

  1. #16
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> This i don't really understand
    This is what I was trying to explain earlier. You cannot add a column to the solution more than once, right? So in your example, in your first step you see that column 1 has the highest value for k. So you add column 1 to the solution. The next time through, you don't want to add column 1 to the solution again, so you should not calculate k for it. It should be ignored in the calculation.

  2. #17
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    >>You needthe column index that has the largest value, not the actual value, right?
    For example if k[1] is the biggest i will add column 1 to the set.

    >>Ok, so you should probably be passing k to the GetMax function, not k[j], right?
    Yes, you are right.

    Look at the code above.I hope that i have understand :-)
    Code:
    while (!aSol->is_complete()) {
      for (i=0; i< instance->n_cols; i++) {     
             k[i] = (covers[i].size() - i) / c[i];// i think this is wrong
    
       //If current column has not already been added to the solution:  I really don't know how to    do this. I have to write new code, define is_added for example boolean funtion??
    
    }
             GetMax(k, covers[i].size() ); // not counting columns already added to the solution??
             aSol->add_column(i);
          
    }
    I think i'm more confused.... You can see that i'm really a beginner and it is quite difficult.And this is only a part...If u can me a hint more..Already u have help me very much

  3. #18
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    I think you are actually close, and it seems you are understanding pretty well.

    >> k[i] = (covers[i].size() - i) / c[i];// i think this is wrong
    Ok, now I realize why this is wrong. The 'i' that I colored red is not the i from the loop. You need a new variable. When I was suggesting the two loops, the red 'i' was from the outer loop, but now that we removed the outer loop, we need a new variable to replace the red 'i'.

    Here is where I am confused. In your first post, and later in your example, you said that the ????? in the formula stands for the rows that have been covered. But in your example your first step was:
    Code:
    k_1 = 2/1    k_2 = 2/3    k_3 = 1/2
    So k_1 was largest. Now in the second step you say that you subtract the rows that have been covered. Does that mean your matrix looks like this:
    Code:
     1   0   0
         0   1   1
         1   1   0
    Or like this:
    Code:
     1 0   0
         0 1   1
         1 1   0
    where green is covered and ignored and black is not. If you meant the first one, I guess it is much more difficult, and I am sorry I was confused. I will wait for you to tell me which one before I confuse things more about this issue. You should remove the i and we'll try again to solve your original problem.



    While you are still trying to figure out the ?????, another thing to work on would be to fix GetMax so that it returns the column, not the nBiggest value. You will need a new variable in that function to remember what the column index is for biggest value.

    Then you need to use the return value of the GetMax function and pass that value to the add_column function, because the result of GetMax will be the column you want to add to the solution. I hope that makes sense.

  4. #19
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    Daved, from what i understand that u said it is the first case!!

    >>But in your example your first step was:

    Exactly, in the first step the ????? is 0 because no row is covered yet.

    That's why in the second step k_2 is 1/3 the column 2 covers 2 rows( the second and the third ) but the third is ALREADY COVERED BY the column1 so we don't calucalate it to find k.

    Does that make sense?? I hope i have cleared thing now
    Last edited by joan; 12-07-2006 at 05:07 AM.

  5. #20
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    Yeah it makes sense. I was thinking that you were subtracting 1 because one column had been covered, but you had been subtracting 1 because of the 2 rows that were covered, only one was covered by the current column. Either way your example was working. But it doesn't matter now. I understand.

    Have you gotten anywhere on fixing GetMax?

  6. #21
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    Yes. I have modified the code as follows:
    Code:
    int GetMax( int nIn[], int nMax ){
    
       assert(nMax > 0);
       int MaxIndex = 0;
       for ( int i = 1; i < nMax; i++){
    	   if (nIn[i] > nIn[MaxIndex]){
             MaxIndex = i;
    	   }
       }
             
       return MaxIndex ;
       
    }
    which gives me the index of the greatest value. It works for a simple programme.

    And then i use it like this in the following code(This is as far i get by now):
    Code:
    Solution* aSol = new Solution(instance);
      
      SC_instance* covers;
      Solution* selected_columns;
      int k[instance->n_cols];
      while (!aSol -> is_complete()) {
    	  for (int i = 0; i < instance -> n_cols ; i++) {
    		  //If column i has not already been added to the solution
    
    		  
    		   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() );
    .

    Then i must randomly delete let's say the half of the columns and repeat for the half of te set the procedure. But one at the time.!!!

    What do u think??

  7. #22
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    GetMax looks good. Even better than how I was thinking of doing it.

    Question: Can the values ever be negative? The reason I ask is because GetMax looks through all the values in k, even the ones for columns that have already been covered. So If negative numbers are not allowed, you can set the k[i] value to 0.0 or -1.0 when i is a column that has been covered. That way GetMax will never select that column, because -1 will never be the max.

    Another small change: You have declared k as an array of integers. That should be an array of double. In programming, 1/3 is 0 if you are working with integers. 2/3 is also 0. There are no decimal or fractional parts with integers. So your k values will be truncated which would be bad. So If you change k to an array of double (and change GetMax to take an array of double) then you will not get that error and 1/3 will be 0.3333 and 2/3 will be 0.6667 and you will be able to find the correct max.


    So you still have to:

    a) Update the k array to be an array of double.
    b) Identify if a column has already been covered so you don't calculate k for that column.
    c) Figure out how to calculate ?????.
    d) remove half of the columns of the solution we obtain and repeat the first step, this time for a partial solution and not for the empty set we had at the beginning.

    For a) see above.
    For b), perhaps an extra map (or set) that stores the indexes of the columns you have already added to the solution.
    Obviously c) is the hard part (which is what you asked about in the beginning). Sorry. I haven't had time to really come up with anything. Hopefully you have been thinking about it as well.
    For d) I think more work needs to be done for that. The random_shuffle and then erase the second half technique would work, but would shuffle the columns, and I'm not sure you want to change the order of the remaining columns.
    Last edited by Daved; 12-07-2006 at 12:05 PM.

  8. #23
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    So, there are 3 things left.

    1) the ?????? term
    2)how to express >> //If column i has not already been added to the solution
    3)remove half of the columns of the solution we obtain and repeat the first step, this time for
    a partial solution and not for the empty set we had at the beginning.

    If you have any idea for these, u would help me VERY much..I'm totally lost

  9. #24
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    See my edited post above.

  10. #25
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    if i change k into double there are 2 errors

    Code:
    1)
    k[i] = (instance->covers[i].size())/(instance-> cost[i]);  : error: invalid types 'double[int]' for array subscript
    
    2)
    aSol -> add_column(GetMax(k,instance->n_cols));  error: cannot convert 'double' to 'double*' for argument '1' to 'int' GetMax(double*, int)'
    What am i doing wrong?? Things getting worse.
    i also changed
    Code:
    double GetMax( double nIn[], int nMax ){
    
       assert(nMax > 0);
       int MaxIndex = 0;
       for ( int i = 1; i < nMax; i++){
    	   if (nIn[i] > nIn[MaxIndex]){
             MaxIndex = i;
    	   }
       }
             
       return MaxIndex ;
       
    }

  11. #26
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    Try and understand my reasoning for suggesting the change. Switch everything back to int, and then re-read what I wrote (the full explanation) and see if you understand what I'm saying. If you understand it, then you should be able to make the change correctly. If you are having trouble understanding what I meant, ask specific questions about it here.

  12. #27
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    >>you can set the k[i] value to 0.0 or -1.0 when i is a column that has been covered
    The rows are covered by the columns, not the columns.I don't know if it was a mistake or u didn't understand.Anyway i understand what u are trying to say for changing k to double and it is correct, but really i don't know how.All i did so far after the changes i showed u is to declare
    Code:
     double k[4000];
    and it comes up a warning like the above.And i don't want to change any member of any other class, because i have been given them.I haven't write them.
    I understand why u don't want to give me directly a code but...anyway
    Last edited by joan; 12-07-2006 at 12:44 PM.

  13. #28
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> you can set the k[i] value to 0.0 or -1.0 when i is a column that has been covered
    Sorry. I meant:

    "you can set the k[i] value to 0.0 or -1.0 when i is a column that has been added to the solution."

    >> double k[4000];
    This seems fine. What warning does it give? The error you posted above looks like you used double k; instead of double k[4000];.

    In GetMax you changed the nIn array to a double array. That is good, because that is the array that represents the values in k. So why did you change the return value? What is the return value supposed to represent?

  14. #29
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    the warning is:
    Code:
    aSol -> add_column(GetMax(k,instance->n_cols));   warning: passing 'double' for converting 1 of void Solution::add_column(int)'
    The code of the solution is
    Code:
    void Solution::add_column(int i) {
    
      
      selected_columns.push_back(i);
      obj_value = obj_value + (instance->cost)[i];
      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;
           is_added[i] = true;
    }
    }
    }
    For the second question i did that: as u see i added the map is_added when we add a column.I also inculded it to the header file as
    Code:
     map<int,bool> is_added;
    A little change.I didn't want to do, cause these are ready given.Maybe things get worse

    And then into the main programme as:
    Code:
    Solution* aSol = new Solution(instance);
    double k[5000];
      while (!aSol -> is_complete()) {
    	  for (int i = 0; i < instance -> n_cols ; i++) {
    		  if (!aSol -> is_added[i]){
    
    		  
    		   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() );
    How do you see that?

    what do u mean i changed the return value? the return value represents the corresponding index of the biggest element(column in this case) of the set with the columns we add
    Last edited by joan; 12-07-2006 at 01:18 PM.

  15. #30
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    Hey, ireally want to thank you.This is very important subject for me. Without your advises i dont know...and i like it like this..not giving me a code directly..

    thanx

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