0
$\begingroup$

Although the title is similar to this one

Finding minimal or canonical expressions for Boolean truth tables

that topic should be about something else.

Given a vector consisting of "n" slots, the objective is to choose the minimum number of vectors that can "fill" these slots. For example,

For n = 10,

Vec 1: 0 0 1 1 0 0 1 1 0 0

Vec 2: 0 0 0 0 1 0 0 0 0 0

Vec 3: 1 1 0 0 1 1 0 0 1 1

So Vec 1 and Vec 3 will be chosen.

There can exist no solutions to fill all the "n" slots and in that case, we want to fill as many as possible.

The Quine–McCluskey algorithm is also not applicable because the objective function is different.

My computer friend suggests me about "Genetic algorithm" but I wonder whether there exists any deterministic algorithm to solve this problem.

$\endgroup$
4
  • $\begingroup$ I think you are asking about the en.wikipedia.org/wiki/Set_cover_problem ? $\endgroup$
    – j.c.
    Feb 14, 2014 at 9:54
  • $\begingroup$ Of course there is a deterministic algorithm --- it's a finite problem, you can just check every subset & keep the smallest one that works. $\endgroup$ Feb 14, 2014 at 10:14
  • $\begingroup$ j.c.'s answer is exact, Gerry Myerson's describes it in a precise way. I want to accept j.c.'s., but I can't see such a button to let me do so. $\endgroup$
    – losu
    Feb 15, 2014 at 2:27
  • $\begingroup$ "answer" is a technical term on this website, and is distinguished from "comment". j.c. and I left comments, not answers; you can accept answers, but there is no button for accepting comments. $\endgroup$ Feb 17, 2014 at 1:29

2 Answers 2

1
$\begingroup$

To exhaustively test all the combinations when the size is small enough to handle. This problem belongs to Set cover problem. Details can be found in http://en.wikipedia.org/wiki/Set_cover_problem

$\endgroup$
1
$\begingroup$

In general though, if $n$ gets too large, you'd want to use a greedy heuristic where at each step you pick the set that covers the most number of "unfilled" spots. That is in a sense the best possible algorithm that we know of.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.