组合计算中的难题，有计算（或用软件）求解方法吗？
本帖最后由 hujunhua 于 2011-11-6 21:44 编辑定义一个集的全体 k 元子集组成了它的 k 元幂集。|A|=a, 问最少需要A的多少个b元子集，使得它们的c元幂集之并等于A的c元幂集。由此定义了一个函数F(a, b, c), 例如F(9, 3, 2)=12, 试计算F(11, 6, 5)。（最好给出这些6元子集） 由于若F(9, 3, 2)=12，则((9),(2))=((3),(2))\times F(9, 3, 2), 这就是说，12个3元子集的2元幂集恰好合成了Range(9)的2元幂集，既无遗漏，也不重复。但是这对于一般情况应该是不成立的。
F(9, 3, 2)的计算，12个3元子集取以下3阶方阵中的行、列、左右对角线（泛对角线）恰好。
1，2，3
4，5，6
7，8，9 仿照上述方法，可得F(27, 3, 2)=117，并且也有((27),(2))=((3),(2))\times F(27, 3, 2)
将1~27个数排成一个3阶3维张量，就是3阶魔方玩具那个样子。取所有27个直行（3个轴向），各层泛对角线54条，空间对角线（两两不同层面的3个阵元）36条，共计117个3元子集，它们的2元幂集恰好合成Range(27)的2元幂集，不重不漏。
依此类推，可得F(3^n, 3, 2)=((3^n),(2))//3, 排成3阶n维张量。 我要求的是F(11, 6, 5)或F(11, 7, 5)
假如F(11, 6, 5)难求，它的较小的上界是多少呢？大家帮忙找找，看谁的上界最小，说不定就是F(11, 6, 5)
PS:有人算出F(11, 8, 5)=17 允许重叠的全覆盖问题
十字双向循环链表组建01稀疏矩阵，搜索算法用dfs+适当剪枝，不知是否可行 允许重叠的全覆盖问题
十字双向循环链表组建01稀疏矩阵，搜索算法用dfs+适当剪枝，不知是否可行
dbsdx 发表于 2011-11-10 15:26 http://bbs.emath.ac.cn/images/common/back.gif
用此方法试试求F(11, 6, 5)=？
页:
[1]