無限/（動態）Universe字母數字元素集中的子集計算

給定字母數字元素的無限集合/ Universe（U）和（U）的子集的族（F）。無限/（動態）Universe字母數字元素集中的子集計算

在（F）中計算/分組所有相關子集，其中所有元素被覆蓋或更少，請參閱示例。

宇宙不是真的無限大，而是非常大，大約有59億個元素，並且在不斷增長。家庭（F）子集也不是一成不變的，大約有130萬個元素，並且也在增長。

實施例：

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編碼子集。但我不確定計算。

來源

2011-04-07 OneFineDayOli

定義「相關」。定義「成長」。請決定是否解決非常大或無限的案例。 – 2011-04-07 17:55:23

宇宙的永久生長需要考慮，它的增長速度與解決方案不太相關。因爲日期是永久增長的，所以將宇宙視爲無限的會更容易。但也許我也很錯。 – OneFineDayOli 2011-04-07 18:21:35

它似乎基於「相關」子集是包含至少一個公共元素的子集的示例。在該示例中，F4具有兩個共享元素，0x9b3746e9（與F1共享）以及0xab70de17和0x9b3746e9與F2共享。括號中的數字表示共享元素的數量（F2（2）= 2與F2的共享元素）。假設這個解釋：

這顯然不是一個NP完成的問題，但一個簡單的索引情況。在哈希表中， U（59×10 6 ）的每一個元素鏈接到的包含它們的子集一個列表（例如 0x9b3746e9 - > {F1，F2，F4}）。當找到給定子集的相關子集時，遍歷子集中U的元素，並查找每個元素的散列表。通過列表重複，並找到與相關的子集。這是一個快速的操作，沒有什麼 NP-complete。

但是，另一個問題的解釋是，這是一個SET COVER組合優化問題的實例。這確實是NP完全的。

來源

2011-04-07 18:11:19

您提到的解決方案最初已實施。爲了節省迭代週期，子集得到加權。但我仍在尋找一種編碼解決方案，以完全克服子集的迭代。謝謝！ – OneFineDayOli 2011-04-07 19:00:58

無限/（動態）Universe字母數字元素集中的子集計算

回答

相關問題