组合计算中的难题，有计算（或用软件）求解方法吗？

AAAAA · 发表于 2011-11-6 16:13:48

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

本帖最后由 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元子集）

hujunhua · 发表于 2011-11-6 23:04:47

由于若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

hujunhua · 发表于 2011-11-7 00:08:23

仿照上述方法，可得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维张量。

AAAAA · 发表于 2011-11-8 22:24:34

我要求的是F(11, 6, 5)或F(11, 7, 5)
假如F(11, 6, 5)难求，它的较小的上界是多少呢？大家帮忙找找，看谁的上界最小，说不定就是F(11, 6, 5)
PS:有人算出F(11, 8, 5)=17

dbsdx · 发表于 2011-11-10 15:26:51

允许重叠的全覆盖问题
十字双向循环链表组建01稀疏矩阵，搜索算法用dfs+适当剪枝，不知是否可行

AAAAA · 发表于 2011-11-12 14:26:51

允许重叠的全覆盖问题
十字双向循环链表组建01稀疏矩阵，搜索算法用dfs+适当剪枝，不知是否可行
dbsdx 发表于 2011-11-10 15:26

用此方法试试求F(11, 6, 5)=？

账号		自动登录	找回密码
密码			欢迎注册

[提问] 组合计算中的难题，有计算（或用软件）求解方法吗？

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。