iterated greedy!!

This is a discussion on iterated greedy!! within the C++ Programming forums, part of the General Programming Boards category; Ok, ithink i have to be more specific. In my previous thread there is a description of the problem.Suppose the ...

  1. #1
    Registered User
    Join Date
    Nov 2006
    Posts
    58

    Question iterated greedy!!

    Ok, ithink i have to be more specific. In my previous thread there is a description of the problem.Suppose the code:

    the first step is:
    Code:
    for (i=0; i< instance->n_cols; i++) { 
    k[i] = (covers[i].size() / c[i]
    }
    The second step:

    Code:
    for (i=1; i< instance->n_cols; i++) {    
          
          k[i] = (covers[i].size() - ?????) / c[i]
    }
    vectors to use(members of a class) :
    Code:
    map<int,vector<int> > covered_by;// columns that cover a row
    map<int,vector<int> > covers; //  rows that covers a column
    map<int,bool> is_covered; // if a row is covered

    What i'm looking for is that (?????) term which indicates the number of rows that have been covered( and there are also covered by this column) and how can i determine the # of steps. Then i have to pick up the max of k[i] and add the corresponding column to a set. I hope that i'm a bit more clear now.

    Thanx!
    Last edited by joan; 12-06-2006 at 12:40 PM.

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,338
    How do you determine the ????? value? Does it increase every time? Can you give a small example of actual values step by step and show what each piece of data would be at each step?

  3. #3
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    Ok.. Here a small example:

    Suppose the matrix :

    Code:
         1   0   0
         0   1   1
         1   1   0
    The first column(from the left) has cost 1.The second 3 and the third 2. Then we can see that the first column covers rows 1 and 3. the second column covers rows 2 and 3, and the third column covers only the row 2. So as it is defined
    Code:
     k_1 = 2/1    k_2 = 2/3    k_3 = 1/2.
    We pick the column with the biggest k (in this case the column 1) and we put it in a set S={1}.
    Code:
    In the second step we have the columns 2 and 3.  We do the same:
    
    k_2 = 1/3(subtract the row that has already been covered)   k_3 = 1/2. We pick the column again with the biggest k and put it in the S, so we have S={1,3}. And we finish.All the rows are covered.
    This is a very simple example. Just to see how it works

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,338
    Can you just keep a counter variable and increment it every time you cover a row?

  5. #5
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    The previous code i had posted was wrong.This one is right.
    How will i use this counter? In the k[] expression??

    I hope that u have understand how the algorithm works.At least this part

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,338
    I would do a nested for loop. The outer loop runs from 0 to less than the number of columns. Each time through the outer loop you find the column with the biggest k out of whatever columns are left. To do that, you set the new value for k for all columns that are left (this is what happens in the inner loop). While you do it you remember which one had the highest value. When the inner loop finishes, you mark the one with the highest k as being set so it won't be looked at the next time the inner loop is run.

    So the ????? in that situation will just be the index of the outer loop, since the outer loop is removing columns one at a time. What you have to do is add code to remember which k is the highest each time the entire inner loop is completed, and then mark that column so that it won't be included the next time through. I'm guessing that is what the is_covered map is for.

  7. #7
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    First Daved thanx for the help,because i'm really desperate. But as a beginer in c++ i haven't really understand very well.Also my english is not very good(i'm spanish).Could u write me one or two lines.?
    I have written a GetMax() function which calculates the max number of a given vector.As i have understand the outer loop will be
    Code:
     for (i=0; i< instance->n_cols; i++)
    the inner loop how it will be??. From what u said k will be like
    Code:
     k[i] = (covers[i].size() - i) / c[i]
    ??

    thanx again

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,338
    >> the inner loop how it will be
    I think you had it in your code in the first post before you edited it. It will run through all of the columns. Make sure you give it a different index name other than i so there is no confusion. So if you used j, then you are correct, the inside of the inner loop would include the line:
    Code:
    k[j] = (covers[j].size() - i) / c[j];
    However, you only want to do that if k[j] has not been officially set yet. So you should check your is_covered map to see if the value for j in the map is true. If it is, then I think you should skip that line of code. In your example, you skip column 1 in the second step because it had the biggest k in the first step, that is basically what you have to do here.

    I don't want to give you all of the code because I don't want to do any part of your project for you, but I will continue to try to explain what I think you should be doing. Just be clear about what you understand and what you don't.

  9. #9
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    What do you mean by skip that line?? which line? i didn't skip it. I just put it in the set S which will be the solution.

    k[i] or k[j] what ever, is a measure to choose the best column to put in the S.

    Maybe i was not very clear before.

    The inner loop will run from j=0 until the number of rows,no? And if yes it will be wrong, because k refers to the columns.

    I think..i'm not sure

  10. #10
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    ok..i didn't see that u had write columns for the inner loop.
    Sorry!!

    But still k is not the set. and i cannot skip that line..it is the basic criterion to choose the best column

  11. #11
    Registered User
    Join Date
    Jan 2005
    Posts
    7,338
    >> What do you mean by skip that line?? which line? i didn't skip it. I just put it in the set S which will be the solution.

    Exactly. In your example, you put column 1 in the set S in the first step. Then in the second step, you said, "In the second step we have the columns 2 and 3. We do the same". You don't use column 1 in the second step because it has already been put into S. That is what I mean by skip. In step 2, column 1 cannot have the biggest k because you already used it for the first step.

    It would be helpful if you posted your entire loop as is, without cutting it up or editing it. Just copy and paste the entire piece of code that you have right now that runs these loops. That will make it easier for me to understand what you have done and how you are doing it.

  12. #12
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    Ok..But i haven't write all the algorithm yet. I'm working in this part..After your advise it would be:
    Code:
    Solution* aSol = new Solution(instance);// it is just a solution
    // i initialize all the values to zero and the solution also ( the solution would be the set )
    
    while (!aSol->is_complete()) {
      for (i=0; i< instance->n_cols; i++) {
         for (j=0; j< instance->n_cols; i++){
             k[j] = (covers[j].size() - i) / c[j];
             GetMax(k[j], covers[j].size() );
             aSol->add_column(j);
          }
        }
    }
    It would be sth like that

  13. #13
    Registered User
    Join Date
    Jan 2005
    Posts
    7,338
    Ok, first, my suggestion for the outer for loop was meant to do exactly what your code while (!aSol->is_complete()) does. You didn't post that originally so I suggested you add the for loop, but since you already have that in there you only need one. So you can remove the outer for loop now.

    >> for (j=0; j< instance->n_cols; i++){
    Second, in that line above you forgot to change the i++ to j++. I don't care whether you switch it back to i or to j, just make sure they are all correct. I might suggest this instead just to be clearer:
    Code:
    for (current_col=0; current_col< instance->n_cols; current_col++){
    Third, what does the GetMax function do exactly? Can you post it? I think that you are not using it correctly.

    In that code, you are calling add_column for every column in the inner loop. I think you only want to add 1 column, the one with the biggest k. So my pseudocode might be:

    - 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

    Does that make sense?

  14. #14
    Registered User
    Join Date
    Nov 2006
    Posts
    58
    the code of GetMax is:
    Code:
    int GetMax( int nIn[], int nMax){
    
       int nBiggest = nIn[0] ;
       for ( int i = 1; i < nMax; i++)
          if (nBiggest > nIn[i])
             nBiggest = nIn[i] ;
    
       return nBiggest ;
    }
    >>Second, in that line above you forgot to change the i++ to j++.

    In the inner loop you say? I think i changed it.

    So you suggest to take out the outer loop. Ok, the pseudo-code makes sense to me.But in this case k how it would be?

    Yes u are right. I should write add_column outside of the loop.It was mistake

    >>Find the column with the largest value in k, not counting columns already added to the solution.
    This i don't really understand
    Last edited by joan; 12-06-2006 at 06:05 PM.

  15. #15
    Registered User
    Join Date
    Jan 2005
    Posts
    7,338
    Ok, so you should probably be passing k to the GetMax function, not k[j], right? That would make sense if you call GetMax outside the for loop, then use whatever column had the max as the column you pass to add_column.

    One issue that you might have is that GetMax is returning the largest value. You needthe column index that has the largest value, not the actual value, right?

    Post your latest code as you make changes so we can make sure we understand each other.

Page 1 of 5 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