Timeline for Algorithm to select sets of objects while maximizing number of objects covered
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 17, 2018 at 2:05 | comment | added | Erik Eidt | With that in mind, I might tease apart groups of matches that don't conflict, so you can apply the above algorithm only to intertwined conflicting sets rather than independent groups. That will help minimize the search spaces sizes, useful since these algorithms will get worse with larger sizes. | |
| Jan 17, 2018 at 2:01 | comment | added | Erik Eidt | However, you should treat matches like S4 that have no conflicts as special, and just assume them in your final solution rather than encoding them into the search space. This will shrink the space that has to be searched since you'll only have conflicts in that space. Then add back the given no-conflict matches at the end. | |
| Jan 15, 2018 at 16:51 | comment | added | Erik Eidt | Yes, this will expand to accomodate such. If there are no conflicts between S4 and the others, then S4 will be available (meaning the respective Candidate[index] = true), for all solutions involving S4 (though not all solutions involve S4). Not all candidates involve S4, however, you will find that any solution that involves S4 does have a higher score than the otherwise same solution that doesn't. So the max will have S4 in it. | |
| Jan 15, 2018 at 16:50 | vote | accept | Zohaib | ||
| Jan 15, 2018 at 16:47 | history | edited | Erik Eidt | CC BY-SA 3.0 |
added 476 characters in body
|
| Jan 15, 2018 at 16:42 | comment | added | Erik Eidt | Not sure if this is your question, but, whereas there is a Set of Match#'s in the Value of intermediate data structure(#2), by contrast, each Candidate# represents a Set of Match#'s (here by its Key, not in the Value, which is just a yay or nay). So Candidate# 101 is the set S1 & S3, where as Candidate # 111 is S1, S2, S3. | |
| Jan 15, 2018 at 16:39 | comment | added | Zohaib | In any case, I can make changes to accommodate the requirement to selecting multiple sets. Thanks a lot for your time and efforts. Highly appreciate that. | |
| Jan 15, 2018 at 16:38 | comment | added | Zohaib | Is my understanding correct that finally we select a set with highest score. Which means there will be one answer. (1 set will be selected). And do you think, same algorithm will work, if we add another Set such that S4:{A2, B1} ? Now Set 4 contains elements which do not appear in any other set. | |
| Jan 15, 2018 at 16:36 | comment | added | Zohaib | Hi Erik, apologies for not making my question clear. Although, I get it now. It looks great. Thanks a million. And your last comment helped me to understand some other points also. | |
| Jan 15, 2018 at 16:34 | comment | added | Erik Eidt | Let's say there's two more matches (4. and 5.). Now the Match#'s bit vectors are 5 bits. A1: S1, S3 is 00101. So again, we have to rule out all Candidates where S1 & S3 are together, which is all Candidates that match the pattern xx1x1. This means ruling out Candidate#'s: 00101, 00111, 01101, 01111, 11101, 11111. This is what algorithm with & and == above does. | |
| Jan 15, 2018 at 16:32 | comment | added | Erik Eidt | Ok, at the high level, since A1 has S1 and S3, that means that S1 and S3 are mutually exclusive solutions by your business logic. So, we cannot consider any solution that has both S1 and S3 together. At the bit level, any Candidiate# that matches 1x1 must then be ruled out. That means ruling out both 101 and 111. | |
| Jan 15, 2018 at 16:14 | comment | added | Zohaib | Hi Erik, Thanks a lot for your time. Algorithm seems promising. I am having a bit difficulty in understanding some parts. For example, first iteration of Step 3 may be: A1: S1, S3 masking of S1 = 1 masking of S3 = 100 we take OR of these 2 values and that is: 101 which means consider solution of taking S1 and S3. Now what does "Reject all Candidates at that mask" means? Once again, thanks a lot. It was really helpful. | |
| Jan 13, 2018 at 23:24 | history | edited | Erik Eidt | CC BY-SA 3.0 |
added 62 characters in body
|
| Jan 13, 2018 at 21:46 | history | edited | Erik Eidt | CC BY-SA 3.0 |
deleted 289 characters in body
|
| Jan 13, 2018 at 21:22 | history | edited | Erik Eidt | CC BY-SA 3.0 |
deleted 174 characters in body
|
| Jan 13, 2018 at 21:02 | history | answered | Erik Eidt | CC BY-SA 3.0 |