从矩阵中选择点的算法
这似乎是一个简单的问题，但我却陷入了这个问题。问题是我有一个大小为 X x Y 的矩阵。 (i,j) 处可能有一些点。然而，并非所有位置(i，j)都应该具有点(即存在＜XY点)。我应该如何选择这些点的最大子集，以便所选子集中没有点具有相同的 i（行号）或 j（列号）
This seems to be a simple problem but I am stuck at this problem. The problem is that I have a matrix of size X x Y. There may be some points at (i,j). It is, however, not necessary that all locations (i,j) should have a point (i.e. there are < XY points). How should I can select the biggest subset of these points such that no points in the selected subset has same i (row number) or j (column number)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这是最大匹配问题，可以多次解决。给定问题的一个实例，构建一个包含节点 a1, …, aX, b1, …, b 的二分图>Y，并且对于所有有点的 (i,j) ，边 aibj 。取最大匹配中边对应的点。
This is the maximum matching problem, which is poly-time solvable. Given an instance of your problem, construct a bipartite graph with nodes a1, …, aX, b1, …, bY, and edges aibj for all (i,j) where there's a point. Take the points corresponding to the edges in a maximum matching.
构造图。点是图的顶点。每个顶点都与同一行和同一列中的所有顶点（图的边）连接。您的问题是选择最大独立顶点集（没有公共边）。
Independent_set
这个问题相当于补图中的最大派系问题，所以 Bron-可以使用Kerbosch算法。
http://en.wikipedia.org/wiki/Clique_problem#Finding_maximum_cliques_in_ Arbitary_graphs
http://en.wikipedia.org/wiki/Complement_graph
Bron-Kerbosch 算法
Construct graph. Points are vertices of graph. Every vertice is connected with all vertices in the same row and same column - edges of graph. Your problem is to select maximum independent set of vertices (without common edges).
Independent_set
This problem is equivalent to to maximum clique problem in complement graph, so Bron-Kerbosch algorithm could be used.
http://en.wikipedia.org/wiki/Clique_problem#Finding_maximum_cliques_in_arbitrary_graphs
http://en.wikipedia.org/wiki/Complement_graph
Bron-Kerbosch algorithm