How to find the minimum set of columns in a matrix to ensure every row has at least one nonzero value

Question

Dan K 2016-5-4

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/282565-how-to-find-the-minimum-set-of-columns-in-a-matrix-to-ensure-every-row-has-at-least-one-nonzero-valu

评论： Star Strider 2016-5-4

Hi. I'm hoping somebody knows of an elegant way to do this. I have an array of logical values MxN. I'm trying to find the minimum set of columns of that matrix such that every row has at least one true value.

A = rand(100,100)>0.5

The best I've got so far is to choose one column to start with, and then iteratively go through and find the column which has the highest impact on my end goal and include that. But I know that this doesn't ensure the best solution.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Star Strider 2016-5-4

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/282565-how-to-find-the-minimum-set-of-columns-in-a-matrix-to-ensure-every-row-has-at-least-one-nonzero-valu#answer_220796

If you’re looking column-wise to see what columns have one true value in every row (the way I interpret your question), then sum the matrix and look for column sums that equal ‘M’. All rows in that column would have to be true.

2 个评论
显示无隐藏无

Dan K 2016-5-4

在 MATLAB Online 中打开

Thanks,

Unfortunately that's not what I'm trying to achieve. I can easily test to see if there exists a column where every row is true. What I'm trying to do is find the minimum collection of columns such that:

all(sum(A(:,[column_indices]),2) > 0) is true