无限/（动态）宇宙字母数字元素集中的子集计算
给定字母数字元素的无限集合/宇宙 (U) 和 (U) 子集的族 (F)。
计算/分组 (F) 中的所有相关子集，其中所有元素都被覆盖或更少，请参见示例。
宇宙并不是真正无限的，但非常大，大约有 5900 万个元素，并且还在不断增长。族 (F) 子集也不是恒定的，大约有 1300 万个元素，并且还在不断增长。
示例：
U = {9b3745e9,ab70de17,1c410139,44038bbf,9c610bb, ...,N}
F1 = {9b3745e9,07ee0220}
F2 = {9b3745e9,ab70de17,99b5d738}
F3 = {99b5d738,07ee0220}
F4 = {9b3745e9,ab70de17,1c410139}
F4计算()={F2(2),F1( 1)}
当然，你可以通过残酷的迭代来做到这一点，但随着时间的推移，它不是最佳解决方案（NP 完全问题）。
有什么想法可以更有效地解决这个问题吗？对子集进行编码，同时使用大于 Universe 的元素/向量密码本，例如 70Mil 或 100Mil。但我不确定计算。
Given a infinite set/Universe (U) of alphanumeric elements and a family (F) of subsets of (U).
Calculate/Group all related subsets in (F), where all elements are covered or less, see example.
The Universe is not really infinite, but very large, approximately 59Mil elements and growing. Family (F) subsets, are not constant either, approximately 13Mil elements and growing as well.
Example:
U = {9b3745e9,ab70de17,1c410139,44038bbf,9c610bb,...,N}
F1 = {9b3745e9,07ee0220}
F2 = {9b3745e9,ab70de17,99b5d738}
F3 = {99b5d738,07ee0220}
F4 = {9b3745e9,ab70de17,1c410139}
F4calculate()={F2(2),F1(1)}
Of cause you can do it on brutal iteration, but over time it is not the optimal solution (NP-complete problem).
Any ideas how this can be solved more efficient? Encoding subsets, while using a element/vector Codebook that is larger than Universe, for instance 70Mil or 100Mil. But I'm not sure about calculation.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
根据该示例，“相关”子集似乎是包含至少一个公共元素的子集。在示例中，F4 有两个共享元素：0x9b3746e9（与 F1 共享）以及与 F2 共享的 0xab70de17 和 0x9b3746e9。括号中的数字表示共享元素的数量（F2(2) = 2 个与 F2 共享的元素）。假设这样的解释：
然而，对该问题的另一种解释是，这是 SET COVER 组合优化问题的一个实例。这确实是NP完全的。
It seems based on the example that "related" subsets are subsets that contain at least one common element. In the example, F4 has two shared elements, 0x9b3746e9 (shared with F1) and 0xab70de17 and 0x9b3746e9 shared with F2. The numbers in parentheses denote the number of shared elements (F2(2) = 2 shared elements with F2). Assuming this intepretation:
However another interpretation of the question is that this is an instance of SET COVER combinatorial optimization problem. This is indeed NP-complete.