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.

Improve this question
$\endgroup$
4
  • $\begingroup$ I think you are asking about the en.wikipedia.org/wiki/Set_cover_problem ? $\endgroup$
    – j.c.
    Commented 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$
    – Gerry Myerson
    Commented 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
    Commented 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$
    – Gerry Myerson
    Commented Feb 17, 2014 at 1:29

2 Answers 2

Reset to default
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

Improve this answer
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .