set-cover

3熱度

1回答

例如，集合覆蓋決策問題已知是一個NP完全問題。這個問題的輸入是宇宙U，U的子集S和一個整數k（）。我很困惑的一件事是，如果讓k = 1，那麼通過簡單地檢查S中的每個元素，顯然問題可以在時間| S |中解決。更一般地，當k是常數，問題可以用| S |的多項式時間來解決。在這樣的方式，時間複雜度成倍成爲僅高當k也增加| S |像| S |/2，| S |/3 ...... 所以我這裏還有我的問題：

0熱度

1回答

在Python中優化Itertools結果

我在Python中調用itertools（請參見下文）。在此代碼中，snp_dic是一個包含整數鍵並設置爲值的字典。這裏的目標是找到值的聯合的最小列表，其組合等於set_union。（這相當於爲您感興趣的人們解決流行的NP-hard圖論問題集覆蓋的全局最優）！下面的算法工作，但這裏的目標是優化。我看到的最明顯的優化與itertools有關。假設對於長度r，在snp_dic的union = se

3熱度

1回答

貪婪集覆蓋算法建*由*刪除*集

我試圖用貪婪算法實現設置覆蓋問題的解決方案。它經典的貪心近似算法是 input: collection C of sets over universe U , costs: C→R ≥0 output: set cover S 1. Let S←∅. 2. Repeat until S covers all elements: 3. Add a set s to S, where s∈

0熱度

1回答

用熊貓做貪婪套裝的最快方法是什麼？

這個問題與貪婪集封面問題不完全相同，但他們有相同的想法。給定一個數據幀熊貓DF1與一列DF [「S」]一組DF2的鍵字組成的： import numpy as np import pandas as pd >>> df = pd.DataFrame(np.array([set([1,3,5]), set([1,3,5,6]), set([2,3,4,12]), set([1,3,7]), s

0熱度

1回答

如何通過使用最常用單詞的列表來排序，以儘可能找到使用最獨特單詞的高效組合？

我有從谷歌的公開可用的ngram數據派生的最常用詞彙的列表。我： 6800頻繁2克 4800頻繁3克 2500頻繁4克 1100頻繁5克一個例子2 NGRAM會是這樣的：「狗」「一書「」三把椅子「等一個例子5 ngram woul d是這樣的：「曾幾何時有」「很久以前，有」「這是一個黑暗和」等我也有2,000頻繁出現的詞彙列表。 1）我想找出來自我的各種列表的最少數量的ngr

2熱度

1回答

當集合數量太多，例如2^n集合時，集合覆蓋中是否有任何appproximate算法？

我最近正在研究一個我認爲是集合覆蓋問題的分支的問題。但是，我的問題集的數量大到2^n。我發現的近似算法似乎只在沒有太多組時纔有效。我想知道存在一個適合2^n集合的算法嗎？謝謝您的回答！

5熱度

2回答

Set Cover的查詢

美好的一天，我想爲Set Cover Problem實現T-SQL查詢，但一直無法找到有關如何在SQL中執行此操作的任何提示。就我而言，我的表只是有兩列（IDnumber和Mut），我想找到的IDNumber最小數量讓每一個Mut之一。我真的想要每Mut獲得三個IDnumbers，但我想我最好從一個開始，因爲這可能會更容易。 DECLARE @myTable TABLE ( IDnumb

1熱度

1回答

設置封面：生成測試實例

我期待着用遺傳算法解決Set Cover Problem。我一直在尋找一些好的測試例子，但沒有取得任何大的成功。我正在尋找的是一些實例，形式如下：集U = {1,2，...，n}和它的子集S = {{1,2}，{4 }，{3,4,5}}，其中S的聯合爲U. 當然，這是一個小例子，因爲我希望找到一些更大的實例。那麼，有沒有人有任何關於這種類型的實例的好來源，或者可能是一種生成它們的方法嗎？後來

4熱度

1回答

最小設置覆蓋率

我想解決以下排序的最小設置覆蓋率問題。所有列表只包含1和0。我說一個列表A覆蓋列表B如果你能正好插入x符號使從AB。考慮所有2^n個1和0的長度爲n的列表並設置x = n/3。我會計算一個涵蓋它們全部的長度爲的最小組列表。這是我開始的一種天真的方法。對於長度爲的每一個可能的列表，我使用這個函數（由DSM編寫）創建一組我可以從中創建的所有列表。 from itertools impor

-2熱度

1回答

查找最小集合覆蓋的最快算法

找到最小集合覆蓋的最省時和最正確的算法是什麼？我不需要代碼本身。我想要一個解釋或僞代碼如何工作。對於一個例子，我們有 Set S = {1,2,3,..,12} Subsets S1 = {1,2,3,4,5,6}, S2 = {5,6,7,8,9}, S3 = {1,4,7,10}, S4={2,5,7,8,11} S5 = {3,6,9,12}, S6 = {10,11} 的分