Thread: iterated greedy!!

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?

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

Can you just keep a counter variable and increment it every time you cover a row?

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

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.

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

>> 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.

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

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

>> 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.

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

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?

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.