查找中的R

非interescting線從一個矩陣的最小數目我有一組線其中一些相互交叉的。我可以生成一個攔截矩陣。查找中的R

1 2 3 4 5 6 
1 0 1 0 1 0 0 
2 1 0 1 1 0 0 
3 0 1 0 0 1 0 
4 1 1 0 0 0 1 
5 0 0 1 0 0 0 
6 0 0 0 1 0 0

其中1 =相交併0 =不itersect

例如線1個與相交線2和4

我想產生的集線在沒有的最小數量線在該組內相交。

對於這個例子，我能想出最好是含有三組：

線2，5，6條

線1,3

線4

I」在R中編程這個，但我真的需要一個數學/概念的答案來解決這個問題。

2016-11-03 falcs

您可以在診斷元素更改爲默認值。然後做'應用（df，1，function（x）which（x == 0））''。 –

爲什麼你的解決方案中沒有其他的單身人士（4人以外）？例如，只有第1行的集合也有（平凡）集合內沒有行相交。此外，矩陣爲0的任何線對也是解決方案的一部分。另外，（1,5,6）。 – aichao

@aichao我給的解決方案只是一個例子，我敢肯定還有其他的，但我無法找到一個不到3套。對於我的任務來說，只要不相交併且儘可能少，這些集合的組合就不重要了。 – falcs

如果考慮線爲圖表和交集關係作爲邊緣節點，那麼你要每個頂點的一組分配，使得兩個相鄰頂點不在（即你的矩陣是鄰接矩陣）同組。

這等同於頂點着色問題。在Wikipedia page上可以找到許多有關此問題的算法。尋找最佳着色的問題是NP難題。如果你對近似有好處，你可以使用時間複雜度爲O（V D）的貪婪方法，其中V是頂點數，D是最大頂點度。

2016-11-03 12:34:03

回答