我正在尝试解决一个优化问题，但是首先我必须找到n个元素的所有可能组合的数量，但要考虑一些冲突。一个可能的示例可能是：
元素：{1,2,3,4}冲突：{1,2}，{3,4}
术语“冲突”表示不能将属于同一冲突集的数字分配到相同的组合中。同样，冲突集并不总是不相交的，并且每个冲突集中的元素始终是两个。
到目前为止，我仅发现如何计算所有可能的组合，即2 ^ n。
谢谢你。
可以将冲突集建模为图形中的边。您需要图形中独立顶点集的数量
图G的独立顶点集是这些顶点的子集，因此子集中的两个顶点都不代表G的边缘-http: //mathworld.wolfram.com/IndependentVertexSet.html
上面的链接还引用了一种称为独立多项式的东西，可以用来对这些东西进行计数-尽管这仅在冲突图具有良好结构的情况下才有用。确定独立集合数的一般问题已知为＃P-complete（有关此复杂度类的定义，请参见https://en.wikipedia.org/wiki/Sharp-P-complete），因此几乎没有机会您的问题有一个简单的答案。在某些情况下，已应用马尔可夫链技术来近似此数字。参见http://www.researchgate.net/publication/221590282_roxly_Counting_Up_To_Four_(Extended_Abstract）
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句