Finding minimal number of expressions (a minimum spanning tree-like problem)

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.

• I think you are asking about the en.wikipedia.org/wiki/Set_cover_problem ? – j.c. Feb 14 '14 at 9:54
• Of course there is a deterministic algorithm --- it's a finite problem, you can just check every subset & keep the smallest one that works. – Gerry Myerson Feb 14 '14 at 10:14
• 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. – losu Feb 15 '14 at 2:27
• "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. – Gerry Myerson Feb 17 '14 at 1:29

2 Answers

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

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.