一个算法有关问题，也算数学有关问题。关于得到一个序列中两两互斥组合最多的方法
请教大家一个算法问题，也算数学问题。关于得到一个序列中两两互斥组合最多的方法
详细要求是这样的：
有一个序列 a, b, c, d, e, f, g
用一下矩阵表示 0表示不互斥， 1表示互斥
a b c d e f g
a 0 1 0 1 0 1 0
b ...................
要求：
得到一个序列组合，这个组合中所有元素两两互斥， 并且这个组合中符合要求的数是最多的
这个问题看似简单，耗费了我很多时间了，请大家不要简单的说遍历，时间复杂度会很高。这或许是个数学问题，希望遇到这个问题的同学能帮忙解疑一下
------解决方案--------------------
感觉可以转化为图论中的知识吧：描述互斥的矩阵是对称矩阵，互斥表示结点之间有连接，不互斥表示没有连接。
------解决方案--------------------
同意 1 楼的看法.即:按照下面办法构造图G:
1) 序列中每个点对应图的一个顶点;
2) 对于序列中任意两个点 u 和 v,若它们互斥,就在 u 和 v 之间构造一条边;
这样,楼主的问题就成了:
给定一个图 G=(V,E),如何求它的最大完全子图.
而实际上,仅仅判断一个 G 是否含一个大小是 k 的完全子图都是 NP 完全的,不要说求它的最大完全子图了.
所以,楼主,就现在的计算机理论水平而言,该问题没有找到多项式解.
也许等若干年(也许上百年),有人证明 NP=P,就有多项式解了.
也许等若干年(也许上百年),有人证明 NP<>P,我们就可以理直气壮地说:该问题在确定性图录机模型下没有多项式解.这样,楼主也不要费神了. :-)
------解决方案--------------------
拆点+最大流应该可以（求二分图的最大匹配），详细资料LZ先搜索一下
------解决方案--------------------
------解决方案--------------------
------解决方案--------------------
不好意思，理解题目有误，以为是分为x，y2部分，所有x和y都互斥。
一个集合里面两两互斥的话就是np的了。如果数据规模不大的话，可以用dlx试试。
详细要求是这样的：
有一个序列 a, b, c, d, e, f, g
用一下矩阵表示 0表示不互斥， 1表示互斥
a b c d e f g
a 0 1 0 1 0 1 0
b ...................
要求：
得到一个序列组合，这个组合中所有元素两两互斥， 并且这个组合中符合要求的数是最多的
这个问题看似简单，耗费了我很多时间了，请大家不要简单的说遍历，时间复杂度会很高。这或许是个数学问题，希望遇到这个问题的同学能帮忙解疑一下
------解决方案--------------------
感觉可以转化为图论中的知识吧：描述互斥的矩阵是对称矩阵，互斥表示结点之间有连接，不互斥表示没有连接。
------解决方案--------------------
同意 1 楼的看法.即:按照下面办法构造图G:
1) 序列中每个点对应图的一个顶点;
2) 对于序列中任意两个点 u 和 v,若它们互斥,就在 u 和 v 之间构造一条边;
这样,楼主的问题就成了:
给定一个图 G=(V,E),如何求它的最大完全子图.
而实际上,仅仅判断一个 G 是否含一个大小是 k 的完全子图都是 NP 完全的,不要说求它的最大完全子图了.
所以,楼主,就现在的计算机理论水平而言,该问题没有找到多项式解.
也许等若干年(也许上百年),有人证明 NP=P,就有多项式解了.
也许等若干年(也许上百年),有人证明 NP<>P,我们就可以理直气壮地说:该问题在确定性图录机模型下没有多项式解.这样,楼主也不要费神了. :-)
------解决方案--------------------
拆点+最大流应该可以（求二分图的最大匹配），详细资料LZ先搜索一下
------解决方案--------------------
------解决方案--------------------
------解决方案--------------------
不好意思，理解题目有误，以为是分为x，y2部分，所有x和y都互斥。
一个集合里面两两互斥的话就是np的了。如果数据规模不大的话，可以用dlx试试。