ITERATED GREEDY ALGORITHM. Help!!

This is a discussion on ITERATED GREEDY ALGORITHM. Help!! within the C++ Programming forums, part of the General Programming Boards category; Ok guys, i'm really stuck here.I have to write a greedy algorithm to solve the set covering problem.(i.e given a ...

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

    ITERATED GREEDY ALGORITHM. Help!!

    Ok guys, i'm really stuck here.I have to write a greedy algorithm to solve the set covering problem.(i.e given a matrix nxn i have to find the best solution, which is a set of columns that covers all the rows). Anyway, istart from the empty solution and then i pick randomly a column. I have two vectors :

    map<int,vector<int> > covers; which gives me the rows that are covered by a column.For example covers[0].size() -> number of rows covered by column 0.

    map<int,vector<int> > covered_by; which gives me the columns that cover a row in the same way as above.

    and the add_column(int i) function

    Now, every column has a cost c. The best column to add to the set is te one that has max #rows(that covers)/cost c.

    What i have to do is in a loop running all the columns add the best ones by the above criterion and make the set but in every step i must subtract from the numerator the #rows that are already covered.

    Well, it doesn't seem very difficult but i'm really really stuck>i have tried everything.If anyone has an idea(the loop would be perfect)..please..It's very important.

    Thanx
    Last edited by joan; 12-05-2006 at 11:47 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 01:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 06:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

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