k元子集的最短路径

wayne · 发表于 2012-6-9 10:35:17

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

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

×

由集合 S {1,2,3,....,N} 的一部分具有k个元素的子集构成了集合为A，A中的元素最多有2个共同的元素。

从集合A的每一个元素中各提取一个元素，其并集构成集合B，
如何才能使得集合B的元素个数最少？

=============================
例如集合 {1,2,3,....,15,16} 的四元子集构成集合A：
{{1, 2, 5, 6}, {1, 3, 9, 11}, {1, 4, 13, 16}, {2, 3, 6, 7}, {2, 4, 10,12}, {2, 5, 7, 10}, {2, 8, 9, 15}, {3, 4, 7, 8}, {3, 5, 12, 14}, {3, 6, 8, 11}, {5, 6, 9, 10}, {5, 7, 13, 15}, {6, 7, 10, 11}, {6, 8, 14, 16}, {6, 9, 11, 14}, {7, 8, 11, 12}, {7, 10, 12, 15}, {9, 10, 13, 14}, {10, 11, 14, 15}, {11, 12, 15, 16}}
具有最少元素的集合B可以是：
{5, 6, 8, 10, 11, 13},
{2, 7, 10, 11, 12, 16},
{1, 7, 9, 10, 11, 14}，
等等

hujunhua · 发表于 2012-6-9 15:09:43

一部分啊，理论上处理没有可能。继续贪心

mathe · 发表于 2012-6-10 07:09:33

http://en.wikipedia.org/wiki/Hitting_set

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

[提问] k元子集的最短路径

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